next up previous
Next: Conversion of NFA to Up: Nondeterministic Finite Automata (NFA) Previous: Extension to a Set

Equivalence of DFA and NFA

Th: Let L be a set accepted by an NFA. Then there exists a DFA that accepts L.

Read the proof pp. 105-106: The equivalent DFA Keeps track of all the states that the NFA could be in.



Sushil Prasad
Tue Jul 7 12:26:32 EDT 1998