Nondeterminism is one of the most fruitful ideas in the theory of computation, and the best place to meet it is finite automata. A nondeterministic automaton, or NFA, can have several possible moves at the same moment, or none at all. It looks like a more powerful model than the DFA; in fact it recognizes exactly the same languages. Understanding why is an excellent exercise in reasoning.
What changes compared with a DFA
An NFA is still a 5-tuple (Q, Σ, δ, q₀, F), but the transition function has a different shape:
δ: Q × (Σ ∪ {ε}) → P(Q)
where P(Q) is the power set of Q. There are three differences:
- from one state, reading a symbol, the machine can go to several states at once;
- it can go to no state: that branch of the computation dies;
- there are ε-transitions, moves that happen without reading any symbol.
An NFA accepts a string if there exists at least one computation path that, after consuming the whole input, ends in an accepting state. Failing paths do not count.
Two ways to picture nondeterminism
The first is to imagine the machine always "guessing" the right choice. The second, more concrete, is to imagine that at every fork the machine duplicates itself and follows all branches in parallel: the string is accepted if at least one copy reaches the goal.
The second view leads straight to deterministic simulation: instead of following one copy at a time, we keep track of the set of states the machine could be in at that moment.
An example: "the third symbol from the end is 1"
Consider the language of strings over {0, 1} whose third-to-last symbol is 1. An NFA recognizes it with four states:
- q0: reads any symbol and stays in q0; on reading 1 it can also "bet" that this is the third-to-last symbol and move to q1;
- q1: on any symbol goes to q2;
- q2: on any symbol goes to q3;
- q3: accepting state with no outgoing transitions.
The automaton is very easy to write because it exploits guessing. A DFA for the same language must remember the last three symbols read, so it needs 2³ = 8 states. In general, for "the n-th symbol from the end is 1" the NFA has n + 1 states, while every equivalent DFA needs at least 2ⁿ.
The subset construction
The equivalence theorem states that for every NFA there is a DFA recognizing the same language. The proof is constructive and is called the subset construction.
First we need the notion of ε-closure: the ε-closure of a set of states S is the set of states reachable from S using only ε-transitions, including those in S.
The DFA is built as follows:
- Each DFA state is a subset of the NFA's states.
- The DFA start state is the ε-closure of {q₀}.
- From state S, reading symbol a, the DFA moves to the ε-closure of the union of δ(q, a) for every q in S.
- A DFA state is accepting if it contains at least one accepting NFA state.
- Only reachable states are generated, starting from the initial one and exploring outward.
Step 5 matters in practice: in theory there are 2^|Q| possible states, but the ones actually reachable are often far fewer.
Following the construction on a small case
Take an NFA over {a, b} with states p, q, r, where p is the start state and r is accepting, and transitions: from p on a to {p, q}, from p on b to {p}, from q on b to {r}. It recognizes strings ending in "ab".
- Start state: {p}.
- {p} on a → {p, q}; {p} on b → {p}.
- {p, q} on a → {p, q}; {p, q} on b → {p, r}.
- {p, r} on a → {p, q}; {p, r} on b → {p}.
We get three reachable states, and the only accepting one is {p, r}, because it contains r. The resulting DFA is correct and already minimal.
Why nondeterminism is useful
If NFAs and DFAs are equivalent, why study NFAs? For three concrete reasons:
- Compactness: as we saw, an NFA can be exponentially smaller.
- Composition: union, concatenation and iteration of languages are immediate with ε-transitions. This is the standard route for turning a regular expression into an automaton (Thompson's construction).
- Conceptual bridge: the same pattern, "there exists an accepting path", returns in nondeterministic Turing machines and in the definition of the class NP. There, however, we do not know whether nondeterminism can be removed at only polynomial cost: that is, in essence, the P vs NP question.
In short
- An NFA can have several transitions, no transition or ε-transitions, and accepts if at least one computation branch accepts.
- NFAs and DFAs recognize exactly the same class: the regular languages.
- The subset construction turns an NFA into a DFA by using sets of states as states.
- The cost can be exponential: for some languages every equivalent DFA has at least 2ⁿ states.
- Nondeterminism simplifies constructions and anticipates central ideas of complexity theory.
