Nondeterminism is a useful concept that has had great impact on the theory of computation. In a deterministic computation, every step follows in a unique way from the preceding step. When the machine is in a given state and reads the next input symbol, we know what the next state will be—it is determined.
In a nondeterministic machine, several choices may exist for the next state at any point. Nondeterminism is a generalization of determinism, so every deterministic finite automaton is automatically a nondeterministic finite automaton (NFA).
The key differences between a deterministic finite automaton (DFA) and an NFA are:
- In a DFA, each state has exactly one transition for each symbol in the alphabet
- In an NFA, a state may have zero, one, or many transitions for each symbol
- NFAs can have ε-transitions (transitions without consuming an input symbol)
How NFAs Compute
When an NFA runs on an input string and comes to a state with multiple ways to proceed, the machine splits into multiple copies of itself and follows all the possibilities in parallel.
Think of it as exploring all possible paths simultaneously. If any one of these paths leads to an accept state at the end of the input, the NFA accepts the string.