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 |2|
states. (Usually far fewer states will be needed.)

Copyright © 1996 by David Matuszek

Last modified Jan 31, 1996