The idea: merge states no string can tell apart
A DFA often has more states than it needs. The subset construction turns the regex (a|b)*abb into a DFA with 5 states, A to E, but A and C behave exactly alike: from either one, every input string ends in accept, or in reject, the same way. Two such states are equivalent, and they can be merged into one without changing which strings the DFA accepts. DFA minimization finds all equivalent states and merges them. The result is the minimal DFA: the fewest states any DFA for the language can have.
Pick a DFA and press Minimize. Each colour is one block of states that the algorithm has not yet told apart. The table on the right shows, row by row, which block each edge leads to. Press Run to send a string through the original and the minimal DFA side by side.
Distinguishing strings
A string w distinguishes states p and q if reading w from p ends in an accepting state and reading w from q does not, or the other way round. The empty string distinguishes every accepting state from every non-accepting one. In the (a|b)*abb DFA, b distinguishes D from A: from D, b reaches E and accepts; from A, b reaches C and rejects. bb distinguishes B from A. No string distinguishes A from C, because both go to B on a and to C on b.
Two states are equivalent exactly when no string distinguishes them. The algorithm never tests strings one by one (there are infinitely many). It finds the distinguishing strings as a side effect of splitting blocks, and the canvas names the string behind every split.
Step 1: drop unreachable states
A state that no path from the start state reaches can never affect the answer, so it goes first. A breadth-first search from the start state along every edge finds the reachable ones. In the even-a's DFA no edge leads into q5, so q5 is dropped before anything else (Demo: even a's, drop q5, then 6 → 2).
Step 2: refine the partition, round by round
This is Moore's algorithm, also called partition refinement. It keeps a partition of the states into blocks, starting from the coarsest guess and splitting blocks until the guess is right.
- P0: two blocks, the non-accepting states (block 1) and the accepting states (block 2).
- One round: give each state the signature (its block, the block its a-edge reaches, the block its b-edge reaches). States of one block with different signatures split into separate blocks.
- Repeat until a round splits nothing. Then each block is one state of the minimal DFA.
In the (a|b)*abb DFA, round 1 splits D from {A,B,C}: only D's b-edge reaches the accepting block. Round 2 splits B: its b-edge now reaches D's new block, while A and C still go to {A,B,C}. Round 3 splits nothing, so A and C stay together and merge (Demo: (a|b)*abb, A and C merge (5 → 4)). When a block keeps its number after a split, it keeps its colour, so you can follow it from the table to the minimal DFA.
| DFA | states | rounds | minimal | what merges |
|---|---|---|---|---|
| (a|b)*abb | 5 | 3 | 4 | A and C |
| even number of a's | 6 | 1 | 2 | q5 dropped; {q0,q2,q3} and {q1,q4} |
| length mod 4 | 4 | 3 | 4 | nothing: already minimal |
The length-mod-4 DFA shows the other outcome: every block ends with one state, so no two states were equivalent and the DFA was already minimal (Demo: length mod 4 is already minimal). It also shows that rounds can be needed one after another: s3 splits off with the string a, then s2 with aa.
Why it works, and why the answer is unique
Two invariants hold. First, the algorithm never separates equivalent states: if p and q are equivalent, their a-targets and b-targets are equivalent too, so by induction they always have equal signatures. Second, when it stops, any two states in one block go to the same blocks on every symbol and agree on accepting, so they agree on every string. So at the end, same block means equivalent.
The Myhill–Nerode theorem says more: every regular language has exactly one minimal DFA, up to renaming states. So minimizing two different DFAs for the same language gives the same machine. This is how tools check whether two regexes or two DFAs describe the same language: minimize both and compare (Demo: babb runs the same in both DFAs shows the minimal DFA answering like the original).
The table-filling view
The same idea is often taught as a table of all pairs of states. Mark every pair with one accepting and one non-accepting state. Then repeatedly mark a pair (p, q) if, on some symbol, it leads to a pair that is already marked. Pairs never marked are equivalent. Each mark is a distinguishing string, and the order of the marks is the order of the rounds above.
Hopcroft's algorithm and running time
Moore's algorithm does O(n) work per state per round and can need up to n rounds, so it is O(n² · |Σ|) in the worst case, although real DFAs usually settle in a few rounds. Hopcroft's algorithm splits by the same rule but processes only "splitter" blocks, always skipping the larger half of a split. That gives O(n log n · |Σ|), the bound used by lexer generators and regex libraries. Brzozowski's algorithm takes a different route: reverse the DFA, determinize it, reverse and determinize again.
The DFA being minimized often comes from Regex to NFA to DFA; a DFA is the same machine as the hardware in Finite State Machines, where fewer states means fewer flip-flops. One level up, Pushdown Automaton shows a language no DFA can recognize at all.
What the page leaves out
Partial DFAs (with missing edges, add a dead state first), larger alphabets, Hopcroft's and Brzozowski's algorithms in detail, minimizing NFAs (hard: PSPACE-complete in general, and the minimal NFA is not unique), and the formal Myhill–Nerode proof with equivalence classes of strings.