DFA Minimization

The subset construction is faithful but wasteful. It manufactures one DFA state per reachable subset of NFA states, and it has no way of noticing when two of those subsets behave identically — so it routinely over-produces, leaving a DFA with redundant states that all do the same job. Every extra state is a bigger transition table, more cache pressure, a slower scanner. DFA minimization squeezes the machine down to the fewest possible states that still recognise the same language. The remarkable payoff, proved below, is that this minimal machine is unique: for a given regular language there is essentially one smallest DFA, and every correct DFA for that language is a "blown-up" copy of it.

When are two states really the same?

The whole method rests on one relation between states. Call two states p and q equivalent (indistinguishable) if, started from either one, every possible input string leads to the same accept/reject verdict. If no string can ever tell them apart, keeping both is pure redundancy — we can safely merge them into one.

States p and q are distinguishable if there exists some string w such that exactly one of \hat{\delta}(p, w) and \hat{\delta}(q, w) is an accepting state.
They are equivalent if no such distinguishing string exists — for all w, both land in accepting states or both land in non-accepting states.
Equivalence is an equivalence relation; its classes are the states of the minimal DFA. The number of classes equals the number of Myhill–Nerode equivalence classes of the language itself.

The base case writes itself: an accepting state and a non-accepting state are always distinguishable — the empty string \varepsilon already separates them (one accepts \varepsilon, the other does not). Every other distinction is built up from that seed.

Partition refinement, from the top down

Rather than test infinitely many strings, we discover the equivalence classes by partition refinement (the Hopcroft/Moore idea): start with the coarsest guess and keep splitting until nothing more can be split.

1. Start with TWO groups: { accepting states } and { non-accepting states }. (Include the DEAD state in the non-accepting group — don't forget it!) 2. Repeat until no group changes: For each group G and each input symbol a: look at where every state in G goes on a (which GROUP it lands in). If states in G disagree — some go to group X, others to group Y — SPLIT G accordingly into sub-groups that agree. 3. When stable, each remaining group is ONE state of the minimal DFA. Transitions carry over: a group goes, on a, to whatever group its members go to.

The invariant is that two states stay in the same group only while no input seen so far can distinguish them; each split is a freshly discovered distinguishing string, one symbol longer than the last. Because a partition of n states can be refined at most n-1 times, the process must terminate — and Hopcroft's clever choice of which group to split on gives the famous O(n \log n) running time.

A worked refinement

Take a five-state DFA over \{a, b\} with states A (start), B, C, D, E, where D and E are accepting. Its transition table:

State	on a	on b	accepting?
A (start)	B	C	no
B	B	D	no
C	B	C	no
D	B	E	yes
E	B	E	yes

Refine it, watching the groups split:

Round 0. Two groups by acceptance: G_1 = \{A, B, C\} (non-accepting), G_2 = \{D, E\} (accepting).
Round 1, split G_1. On b: A \to C \in G_1, C \to C \in G_1, but B \to D \in G_2. So B disagrees with A, C — split into \{A, C\} and \{B\}.
Round 1, check G_2. On both symbols D and E go to the same groups (a \to \{B\}, b \to G_2): they never split. \{D, E\} merges into one state.
Round 2, re-check \{A, C\}. On a both go to \{B\}; on b both stay in \{A, C\}. Stable — they are truly equivalent.

The dust settles on three classes: \{A, C\}, \{B\}, \{D, E\} — the five-state DFA minimises to three states, with D and E (and A with C) revealed as duplicates. The refinement below animates exactly this collapse.

Refinement in code

The algorithm is short: represent the partition as a map from state to group id, and repeatedly re-key each state by the tuple (its group, group it goes to on each symbol); if that produces more distinct keys than before, the partition refined — loop. Below, on the five-state DFA above.

type DFA = { states: string[]; alphabet: string[]; accept: Set<string>; trans: Record<string, Record<string, string>>; }; const dfa: DFA = { states: ["A", "B", "C", "D", "E"], alphabet: ["a", "b"], accept: new Set(["D", "E"]), trans: { A: { a: "B", b: "C" }, B: { a: "B", b: "D" }, C: { a: "B", b: "C" }, D: { a: "B", b: "E" }, E: { a: "B", b: "E" }, }, }; function minimize(dfa: DFA): Record<string, number> { // Round 0: accepting vs non-accepting. let group: Record<string, number> = {}; for (const s of dfa.states) group[s] = dfa.accept.has(s) ? 1 : 0; let count = 2; while (true) { // Re-key each state by (its group, target group on each symbol). const signature: Record<string, string> = {}; for (const s of dfa.states) { const parts = [group[s]]; for (const a of dfa.alphabet) parts.push(group[dfa.trans[s][a]]); signature[s] = parts.join("|"); } const ids = new Map<string, number>(); const next: Record<string, number> = {}; for (const s of dfa.states) { if (!ids.has(signature[s])) ids.set(signature[s], ids.size); next[s] = ids.get(signature[s])!; } if (ids.size === count) return group; // no new splits: stable group = next; count = ids.size; } } const g = minimize(dfa); const classes = new Map<number, string[]>(); for (const s of dfa.states) { if (!classes.has(g[s])) classes.set(g[s], []); classes.get(g[s])!.push(s); } console.log("minimal states:", classes.size); for (const [id, members] of classes) console.log(` class ${id}: {${members.join(",")}}`);

The output confirms the hand-refinement: three classes, with \{A, C\} and \{D, E\} each collapsed to a single minimal state. Swap in any DFA's table and the same loop minimises it.

The uniqueness guarantee

For every regular language L there is a DFA with the fewest states recognising L, and that minimal DFA is unique up to renaming of states (unique up to isomorphism).
Its states are in one-to-one correspondence with the Myhill–Nerode equivalence classes of L — the number of classes is a fixed property of the language, not of any particular machine.
Consequently, minimizing the DFAs of two regular expressions and comparing the results is a decision procedure for language equivalence: two DFAs accept the same language iff their minimal forms are isomorphic.

Uniqueness is what makes minimization more than an optimisation. It says the minimal DFA is a canonical form for a regular language — a fingerprint. That is why minimization underlies tools that check whether two patterns are equivalent, or whether one token class secretly overlaps another.

Because it tracks where the NFA could be, not what the future holds. Two different NFA state-subsets can face identical futures — every string from here on gives the same accept/reject pattern — yet the subset construction, seeing two different sets of NFA-state numbers, dutifully makes two DFA states. It has no lookahead into behaviour; it only knows the reachable configurations. Minimization is the second pass that finally asks the behavioural question the subset construction never could: "ignoring how we labelled these states, do any of them actually act the same?" The two algorithms are complementary — one guarantees a correct DFA, the other guarantees the smallest correct DFA.

Both mistakes here silently produce a wrong (over-merged) machine, which is worse than an over-large one:

Do not forget the dead state. A DFA must be complete — every state has a transition on every symbol — so before minimizing, add the non-accepting dead (trap) state and route all "missing" transitions to it. Skip it and states with a missing arrow look falsely equivalent, because you never compared the futures the missing input would have exposed. The dead state lives in the non-accepting group and often forms its own singleton class.
"Indistinguishable" is about where you go, not whether a symbol is defined. Two states are equivalent when, for every symbol, their targets fall in the same group — and this is recursive, groups splitting as finer distinctions emerge. States that merely share the same outgoing symbols, or even the same immediate target states, can still be distinguishable if those targets later diverge. Always chase equivalence all the way down to acceptance; never declare two states equal just because their transition rows "look similar".