NFA → DFA by Subset Construction

An NFA is allowed to be vague. From one state, on one symbol, it may have several arrows out, or none at all. It accepts a string if some path through it ends in an accepting state — a definition that is easy to write down and impossible to execute directly, because a real machine cannot try every path at once.

The good news is that nondeterminism buys no extra power at all. Every NFA has an equivalent DFA. Subset construction is the proof, and it is a construction rather than an argument — it hands you the machine.

Alphabet (Σ)

The finite set of symbols the machine may read. For everything on this page, Σ = {a, b}.

String and language

A string is a finite sequence of symbols from Σ. A language is a set of strings — usually infinite. A machine does not compute a value; it answers one yes/no question about membership in a language.

State

The machine's entire memory. Not part of it — all of it. If two different inputs leave the machine in the same state, it can never again tell them apart.

Transition function (δ)

Where to go given the current state and the next symbol. For a DFA it is a function: exactly one answer, always. For an NFA it returns a set, possibly empty.

Accepting state

Drawn as a double circle. A string is accepted if the machine is in one of these when the input runs out — not if it merely passed through one on the way.

Trap or dead state

A non-accepting state with every symbol looping back to itself. Once you fall in you can never get out, so the answer is already no. Diagrams usually omit it and leave the arrow missing instead.

1. 1The DFA's start state is the set containing the NFA's start state (plus anything reachable from it on ε-moves — its ε-closure).
2. 2Take an unprocessed subset S and a symbol x. Collect every NFA state reachable from any member of S on x, then take the ε-closure of that. Call the result T.
3. 3If T is new, add it as a DFA state. Either way, draw the arrow S --x--> T.
4. 4Repeat until every subset you have created has an outgoing arrow for every symbol.
5. 5A subset is accepting exactly when it contains at least one accepting NFA state.

Only subsets you actually reach get built. The theoretical worst case is 2ⁿ states, but in practice most subsets are unreachable — here 3 of the 8 possible subsets show up.

The DFA that appears on the right of the animation is the same three-state machine as the DFA execution topic, with the subsets renamed:

That correspondence is worth dwelling on. The three states of the hand-built DFA looked like a clever choice; here the same three fall out of a mechanical procedure that involved no insight whatsoever.

The NFA's start state has a self-loop on both symbols, so the machine can always choose to stay there. That option never goes away, which is why n0 appears in all three subsets — and it is exactly the mechanism that lets an NFA say "...ending in ab" without knowing in advance where the string ends.