NFA to DFA Conversion: The Subset Construction Step by Step

A DFA can remember one thing only: where it is. An NFA can be in several places at once. The subset construction bridges that gap by letting the DFA remember the set of all states in which the NFA could currently be. It is the standard way to show that nondeterminism adds no power to a finite automaton, and it works on any nondeterministic finite automaton.

How does the subset construction turn an NFA into a DFA?

Each state of the new DFA is a set of NFA states. The construction builds only the sets that can actually be reached, which keeps the result small, instead of creating all possible subsets.

1. Create the first DFA state: the set that contains only the NFA start state, written {q₀}.
2. Take a DFA state that has not been processed yet, which is a set S of NFA states.
3. For each input symbol x, collect the targets of all NFA moves on x from every state in S. The union of these targets is the set the DFA moves to on x.
4. If that set is new, add it to the list of unprocessed states.
5. Repeat from step 2 until no unprocessed state remains.
6. Mark every set that contains at least one NFA accepting state as accepting.

The process ends because there are only finitely many subsets of a finite state set. An empty target set is a legitimate DFA state: it stands for "the NFA has no run left", it loops to itself on every symbol, and it never accepts. Whenever a state and a symbol have no NFA move at all, the DFA can use this dead state as the target.

How are the DFA states, start state and accepting states defined?

The construction goes back to Rabin and Scott's 1959 paper on finite automata and their decision problems, where the states of the new automaton are all subsets of the old state set. Written out, with T for the NFA transition function and F for its accepting states, the definition has three parts.

The accepting condition expresses the rule for the NFA: a string is accepted if some run ends in an accepting state, and a set contains such a state exactly when at least one of the runs it represents does. In the original paper an automaton may have a set of start states, and the DFA then starts in the set of all of them. With a single start state this is the set {q₀}.

Why the result is correct follows from one invariant. After the DFA has read a string w, its current state is exactly the set of NFA states that some run on w can reach. The invariant holds before any symbol is read, because the start set is {q₀}, and each transition of the DFA computes the next such set from the previous one. At the end of the string the DFA accepts exactly when that set contains an accepting NFA state, which is the NFA acceptance condition.

How do epsilon moves change the conversion?

Epsilon moves are transitions that consume no input. The conversion handles them with the epsilon-closure of a state, which is the set of states reachable from it through epsilon moves alone. A set of states has the closure of all its members.

There are three common ways to include it:

• Remove the epsilon moves from the whole automaton first, which gives an ordinary NFA, then run the subset construction.
• Compute the closure for each NFA state separately, store it, and use it while building sets.
• Apply the closure to each set as it is formed. The transition becomes the closure of the usual target set, and the start state of the DFA is the closure of {q₀}.

All three give a DFA for the same language. A four-state example on Wikipedia, for instance, starts in the set {1, 2, 3}, and only five of the sixteen possible subsets are reachable. The set method that Chalmers lecture notes use is the third one.

Worked example: the second-to-last symbol is 1

The NFA has states 0, 1 and 2 and accepts strings over {0, 1} whose second-to-last symbol is 1. State 0 loops on both symbols and also moves to state 1 on a 1. State 1 moves to state 2 on either symbol, and state 2 is accepting. The NFA is allowed to guess on a 1 in state 0 that this symbol is the second to last.

The construction proceeds in four rounds.

1. Start with {0}. On 0 it goes to {0}. On 1 it goes to {0, 1}, which is new.
2. For {0, 1}: on 0, state 0 gives {0} and state 1 gives {2}, so the result is {0, 2}. On 1, state 0 gives {0, 1} and state 1 gives {2}, so the result is {0, 1, 2}. Both sets are new.
3. For {0, 2}: on 0 it goes to {0}, because state 2 has no moves, and on 1 it goes to {0, 1}. Nothing is new.
4. For {0, 1, 2}: on 0 it goes to {0, 2}, and on 1 it goes to {0, 1, 2}. Nothing is new.

The accepting sets are those that contain state 2: {0, 2} and {0, 1, 2}. The result is a DFA with four states and eight transitions. To see it work, read 010. From {0}, the 0 keeps the set at {0}, the 1 moves it to {0, 1}, and the final 0 moves it to {0, 2}. That set is accepting, and indeed the second-to-last symbol of 010 is 1.

Why can the DFA need 2ⁿ states?

A set of n NFA states has 2ⁿ subsets, so the DFA never needs more than 2ⁿ states, and for some NFAs it needs exactly that many. The question is how close real examples get.

The family behind these rows is the language of strings whose n-th symbol from the end is 1. It needs an NFA with n + 1 states, while every DFA for it needs at least 2ⁿ states, according to lecture notes from Columbia University. The example above has n = 2, so three NFA states lead to 2² = 4 DFA states. The bound for three NFA states would be 8, and only 4 are reached, because every reachable set contains state 0.

NFA or DFA: which one should you use?

Both machines describe the same languages, so the choice is practical. The NFA is the compact way to specify a language, and the DFA is the form that executes directly. A regular grammar is a third way to describe the same class. The conversion costs time and, in the worst case, exponential size, which is why it is applied when a deterministic machine is really needed.

The same step appears on the way from patterns to programs. A regular expression can be translated into an NFA by induction on its structure, which is the idea behind the construction usually credited to Thompson, and the subset construction then turns that NFA into a DFA that a program can run symbol by symbol.

How do you check that the DFA is correct?

Send chosen strings through both machines and compare the answers. Useful probes are the empty string and the shortest strings that should and should not be accepted. In the example, 11 and 010 are accepted, and 001 is rejected because its second-to-last symbol is 0.

Running every string over {0, 1} up to length 12, 8,191 in total, through the NFA, the DFA and the plain rule gives identical answers. A test over strings up to a given length finds mistakes but does not prove equality for all strings; the proof is the argument of the construction itself. The reach of both machines ends with the regular languages, and the pumping lemma explains how to show that a language lies beyond them. The overview of formal languages shows where regular languages fit.