NFA
Nondeterminisitic Finite Automata
- More than one edge on same input chracter.
- delta(q,a) = s. n(s) >=1
- Allow lambda transition without comsuming any input.
example)
example)
L = {w (={0,1}* | w ends with 01}
Rgular Expression
- Represent patterns of string of chracters
- Describe the individual tokens of the source language
- L(r) : The language generated by RE r
example)
- L(a) is the RE matches character a
- L(lambda) matches a string contains no character.
- L(PI) this set contains no element.
RE Operation
- Alternative : |
- Concat : without a meta-character, sequence.
- Repetition : *
- a|b* = a|(b)**
- a|bc* = a|b(c**)
- ab|c*d = ab|(c)**d
NFA to DFA
- move(s_i, a): the set of states which there is a transition from state s_i on input a.
lambda-closure(s) : the set of states reachable by lambda from s.
gg