Editing Nondeterministic finite automaton (section)

==Equivalence to DFA==

A [[deterministic finite automaton]] (DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state. Thus, it is clear that every [[formal language]] that can be recognized by a DFA can be recognized by an NFA.

Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the [[powerset construction]].

This result shows that NFAs, despite their additional flexibility, are unable to recognize languages that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has ''n'' states, the resulting DFA may have up to 2<sup>''n''</sup> states, which sometimes makes the construction impractical for large NFAs.