- Determinism(DFA) is a subset of nondeterminism(NFA).
- For each letter in DFA, it could only be on only one arrow.
- NFA may have on the arrow，means one or many arrows may exit from this state(zero).
- If a string in a branch is accepted, then NFA accepts the input string.
Formal Def of NFA
A nondeterministic finite automation is a 5-tuple(), where:
- is a Finite set of states
- is a finite alphabet
- is the transition function
- is the start state
- is the set of accept states
Formal Def of computation for an NFA:
Let N=() be an NFA and a string over the alphabet . Then we say that N asscepts if we can write as , where each is a member of and a sequence of states exists in with the following three conditions:
Equivalence of NFAs & DFAs
Two machines are equivalent if they recognize the same language.
Every nondeterministic finite automation has an equivalent deterministic finite automation.