[Overview] [Previous] [Next]

DFA = NFA

Two acceptors are equivalent if the accept the same language.

A DFA is just a special case of an NFA that happens not to have any null transitions or multiple transitions on the same symbol. So DFAs are not more powerful than NFAs.

For any NFA, we can construct an equivalent DFA (see below). So NFAs are not more powerful than DFAs. DFAs and NFAs define the same class of languages -- the regular languages.

To translate an NFA into a DFA, the trick is to label each state in the DFA with a set of states from the NFA. Each state in the DFA summarizes all the states that the NFA might be in. If the NFA contains |Q| states, the resultant DFA could contain as many as |2superscript Q| states. (Usually far fewer states will be needed.)


Copyright 1996 by David Matuszek
Last modified Jan 31, 1996