NFA to DFA: The Subset Construction, Step by Step

The subset construction (also called the powerset construction) turns any NFA into an equivalent DFA. The idea: instead of a DFA state standing for "the NFA is in this one state," it stands for "the NFA could be in any of these states" — a whole subset of the original states at once. Since there are finitely many subsets of a finite set, the resulting machine is still a DFA.

The source NFA

The language here is "the second-to-last symbol of the string is 1" over {0, 1} — a good example precisely because a small NFA blows up into a noticeably larger DFA. The NFA guesses, on each 1, whether that symbol is the second-to-last one, then checks it's right by requiring exactly one more symbol before the string ends.

Running the construction

Start the DFA at the set containing just the NFA's start state, {n0}. For every reachable set and every input symbol, compute the union of where each state in the set can go on that symbol — that union is the next DFA state. Keep going until no new sets appear.

Four reachable subsets from a three-state NFA — the DFA is accepting exactly when its current set contains the NFA's accept state n2, since that means at least one guessed path is still alive and correct.

A⊢B⊢D⊢C⊢∈ F

Try 1101 on both machines: the NFA has to consider every guess at once, while the DFA just follows A → B → D → C, landing in C (accept, since the second-to-last symbol is indeed 0... check it against 0110 and 11 as well to see the pattern hold).

Your turn