A deterministic finite automaton (DFA) and a nondeterministic finite automaton (NFA) are two ways to model computation with a finite number of states. They look different operationally, but they have the same expressive power: both recognize exactly the regular languages.
The major distinction is how transitions are specified. A DFA has exactly one next state for each state/input-symbol pair. An NFA can have zero, one or several possible next states and, in common definitions, may also use ε-transitions that consume no input.
At a glance
| Point | DFA | NFA |
|---|---|---|
| Transitions per symbol | Exactly one from each state | Zero, one or many |
| ε-transitions | Not used | May be allowed |
| Execution concept | Single active state at a time | Conceptually can track a set of possible states |
| Acceptance | The unique computation ends in an accepting state | At least one possible computation ends in an accepting state |
| Expressive power | Regular languages | Regular languages |
| Conversion | Already deterministic | Can be converted to an equivalent DFA by subset construction |
DFA
A finite automaton whose transition function maps each state and input symbol to exactly one next state.
NFA
A finite automaton whose transition relation can map a state/input to a set of possible states; many textbook definitions also permit ε-transitions.
Why NFAs are useful
NFAs are often easier to design from a regular expression or from an intuitive description of alternatives. If a pattern can continue in several possible ways, an NFA can represent those alternatives directly without immediately expanding them into many deterministic states.
This compactness is one reason theoretical constructions frequently introduce NFAs first.
Why DFAs are straightforward to execute
A DFA has no choice to resolve at runtime. Given the current state and next symbol, there is exactly one transition. That makes the conceptual execution algorithm simple: update one state for each input character.
An NFA implementation can simulate a set of active states or first convert the NFA to a DFA.
Subset construction
The standard NFA-to-DFA conversion treats each DFA state as a set of NFA states. The initial set includes the NFA start state and any ε-closure. For each input symbol, the construction computes all NFA states reachable from the current set.
The resulting DFA can have up to exponentially more states in the worst case, although practical automata are often smaller after minimization.
Frequently asked questions
Is an NFA more powerful than a DFA?
No. NFAs can be more concise, but both recognize exactly the regular languages.
Can a DFA have a missing transition?
In the formal definition the transition function is total. A diagram that omits transitions can be completed by adding a dead/sink state.
What does nondeterministic mean here?
It means the model can have several allowed next states; it does not mean randomness.
Are regular expressions equivalent to finite automata?
Yes in expressive power: regular expressions, DFAs and NFAs all describe regular languages.
Sources and further reading
KnowDifferences Editorial Team
Independent explanations with definitions, practical examples and references. Read our editorial approach.