Subset Construction: NFA to DFA
Thompson's construction
gave us a machine that recognises a regular expression — but a nondeterministic one, riddled
with \varepsilon-moves and states that offer two arrows on the same symbol. A
scanner cannot afford to "guess": it must read each character once and step to exactly one next state.
The subset construction (also called the powerset construction) is the
algorithm that removes every trace of nondeterminism, turning any NFA into an equivalent
DFA that accepts precisely the same language.
The idea is deceptively simple and genuinely beautiful. If an NFA, faced with a string, could be in any
of several states at once, then just track the whole set of states it could be in. That set —
a subset of the NFA's states — becomes a single state of the DFA. Because a machine with
n states has only 2^n subsets, the process must
terminate; and because each DFA state records exactly the cloud of NFA states reachable so far, the two
machines accept the same strings. Nondeterminism was never extra power — only extra
convenience, and the subset construction is the receipt that proves it.
Two operations do all the work
The construction is built from two set-valued helpers. Both take you from "where could I be" to "where
could I be next", and everything else is bookkeeping.
-
\varepsilon\text{-closure}(T) — the set of NFA states
reachable from any state in T using
\varepsilon-transitions alone (including the states of
T themselves). It answers: "sitting on this set of states, where can I
drift to for free, before reading any input?"
-
\text{move}(T, a) — the set of NFA states reachable from
some state in T by a single a-transition. It
answers: "if I read the symbol a now, which states could I land on?"
One DFA transition on symbol a from DFA-state
T is then just their composition:
\delta(T, a) \;=\; \varepsilon\text{-closure}\big(\text{move}(T, a)\big).
Read a symbol (\text{move}), then take every free
\varepsilon-ride you can (\varepsilon\text{-closure}).
The DFA's start state is \varepsilon\text{-closure}(\{s_0\}) — the free rides
available before you have read anything at all.
The algorithm
The subset construction is a worklist algorithm. Keep a collection of DFA states you
have discovered but not yet processed; for each, compute its transition on every input symbol,
registering any brand-new subset as a new DFA state to process later. When the worklist empties, every
reachable subset has been found and the DFA is complete.
initial ← ε-closure({ s0 }) // the DFA start state
Dstates ← { initial } (unmarked)
while some T in Dstates is unmarked:
mark T
for each input symbol a:
U ← ε-closure( move(T, a) )
if U is not already in Dstates:
add U to Dstates (unmarked)
Dtran[T, a] ← U
// A DFA state is ACCEPTING iff its subset contains any NFA accepting state.
Two rules finish the job. A subset that contains at least one NFA accepting state becomes an
accepting DFA state. And the empty set \varnothing — what you get
when \text{move} finds no transitions — is a perfectly legal, non-accepting
dead state that loops to itself on every symbol; it is the DFA's way of saying "this
prefix can no longer be completed".
A worked example: (a\mid b)^{*}abb
Take the canonical NFA for (a\mid b)^{*}abb — the Dragon Book's running
example. Its states are numbered 0 to 10, with
0 the start and 10 the sole accepting state,
threaded with \varepsilon-moves around the star. Applying the subset
construction collapses those eleven fuzzy states into just five crisp DFA states.
Reveal the machine step by step:
Each DFA state is a subset of NFA states — for instance A =
\varepsilon\text{-closure}(\{0\}) = \{0,1,2,4,7\}, the start. Reading an
a from A lands on B = \{1,2,3,4,6,7,8\};
reading a b lands on C = \{1,2,4,5,6,7\}.
Only E contains NFA-state 10, so only E is accepting
(double circle). Notice the machine is now fully deterministic: exactly one arrow leaves every
state on every symbol, no \varepsilon-moves anywhere.
The construction, in code
Because \varepsilon\text{-closure} and \text{move}
are just set operations, the whole algorithm is short. Below, an NFA is a map from
state → symbol → list of states (with "eps" for
\varepsilon). We convert a small NFA for
a(a\mid b)^{*} and print its DFA transition table.
type NFA = {
start: number;
accept: number[];
// trans[state][symbol] = list of target states; "eps" = ε-move
trans: Record<number, Record<string, number[]>>;
};
// ε-closure of a set of NFA states.
function epsClosure(nfa: NFA, states: number[]): number[] {
const stack = [...states];
const closure = new Set(states);
while (stack.length) {
const s = stack.pop()!;
for (const t of nfa.trans[s]?.["eps"] ?? []) {
if (!closure.has(t)) { closure.add(t); stack.push(t); }
}
}
return [...closure].sort((x, y) => x - y);
}
// move(T, a): states reachable from T by one a-transition.
function move(nfa: NFA, states: number[], sym: string): number[] {
const out = new Set<number>();
for (const s of states) for (const t of nfa.trans[s]?.[sym] ?? []) out.add(t);
return [...out];
}
// Subset construction. Returns the DFA states (as NFA-subsets) and its table.
function subsetConstruction(nfa: NFA, alphabet: string[]) {
const key = (set: number[]) => set.join(",");
const start = epsClosure(nfa, [nfa.start]);
const dstates = [start];
const seen = new Map<string, number>([[key(start), 0]]);
const table: Record<string, number>[] = [];
for (let i = 0; i < dstates.length; i++) { // worklist grows as we discover states
const T = dstates[i];
const row: Record<string, number> = {};
for (const a of alphabet) {
const U = epsClosure(nfa, move(nfa, T, a));
if (U.length === 0) { row[a] = -1; continue; } // dead state
let id = seen.get(key(U));
if (id === undefined) { id = dstates.length; seen.set(key(U), id); dstates.push(U); }
row[a] = id;
}
table.push(row);
}
const accepting = dstates.map((set) => set.some((s) => nfa.accept.includes(s)));
return { dstates, table, accepting };
}
// NFA for a(a|b)* : 0 --a--> 1, 1 loops on a,b (via ε to a small (a|b) block, simplified here).
const nfa: NFA = {
start: 0,
accept: [1],
trans: {
0: { a: [1] },
1: { a: [1], b: [1] }, // (a|b)* self-loop, already ε-free for brevity
},
};
const { dstates, table, accepting } = subsetConstruction(nfa, ["a", "b"]);
dstates.forEach((set, i) => {
const mark = accepting[i] ? " (accepting)" : "";
console.log(`D${i} = {${set.join(",")}}${mark} --a--> D${table[i]["a"]} --b--> D${table[i]["b"]}`);
});
Run it: D0 = {0} goes to D1 = {1} on a and to the
dead state (-1) on b, while the accepting D1 loops
to itself on both symbols — exactly the DFA for "an a followed by any run of
as and bs".
In the worst case, yes — that 2^n is not just a loose bound. The classic
witness is the language "strings over \{a,b\} whose
n-th symbol from the end is an a". A tiny
(n+1)-state NFA recognises it by nondeterministically "guessing" the right
position, but any DFA must remember the last n symbols — and there are
2^n distinct things to remember, so it needs at least
2^n states. In practice, though, the DFAs that arise from real
lexical specifications are almost always small: the blow-up needs a very deliberately adversarial
regular expression, which programming-language tokens never are. This is why table-driven scanners like
lex are viable at all.
The single most common bug when hand-running the subset construction is forgetting an
\varepsilon\text{-closure}. Two places demand it. First, the
start state is \varepsilon\text{-closure}(\{s_0\}), not
just \{s_0\} — you may be able to drift somewhere for free before reading a
thing. Second, every transition is
\varepsilon\text{-closure}(\text{move}(T,a)): after the
\text{move} you must take the free rides again. Skip either and you will
build a machine that rejects strings it should accept. A useful sanity check: if your NFA has no
\varepsilon-moves at all, then \varepsilon\text{-closure}(T)=T
and the construction degenerates to plain "gather the targets" — but that is the exception, not the
rule.