Why ask for the smallest?
By now you can build a DFA for almost any regular pattern, and you have a whole toolbox — the product construction, complement, the subset construction — that happily spits out machines. The trouble is that those machines are often bloated. The product of two 5-state DFAs has 25 states even when the real language needs only 6. Two people solving the same problem hand you two different state diagrams. So a natural question nags: among all the DFAs that recognize one particular language, is there a best one, and can we find it?
The answer is a quiet little miracle. For every regular language there is one and only one smallest DFA — fewest states possible — and it is unique down to nothing but the renaming of its states. Two correct DFAs for the same language always minimize to the very same diagram. That object is the unique minimal DFA. The previous guide already promised this from the theory side; this guide hands you the algorithm that actually computes it, and explains why the result is forced rather than a lucky choice.
When are two states really the same?
Minimization rests on one sharp question: given two states p and q of a DFA, is keeping them apart actually doing any work? Imagine standing in state p versus standing in state q and then reading the rest of the input. If for every possible continuation string the two states agree on the final verdict — both accept or both reject, every single time — then p and q are doing identical jobs. Nothing the machine can ever observe afterward tells them apart. Such a pair is indistinguishable, and a machine that keeps them separate is wasting a state.
The opposite is the lever we use. Two states are distinguishable if there exists at least one continuation string that ends differently from the two — one leads to acceptance, the other to rejection. That witness string is the proof that p and q are genuinely different roles and must stay apart. This is the exact same notion as string indistinguishability from the previous guide, just moved one level up: there we compared two strings by their futures; here we compare two states by their futures. The bridge is simple — a string's future is just the future of whichever state the machine sits in after reading it.
The table-filling algorithm, step by step
Here is the classic recipe, called the table-filling or mark-and-propagate algorithm. The idea is to start pessimistic about almost nothing and let distinguishability spread outward like a stain. You mark a pair the moment you can prove it is distinguishable, and you keep marking until no new marks appear. Whatever stays unmarked when the dust settles is a genuinely indistinguishable pair, safe to merge.
- Clean up first. Remove every unreachable state (no input ever drives the start state to it) — it cannot affect the language. Make sure the DFA is total, adding a dead trap state if some transition was missing.
- Make a table with one cell for every unordered pair of states {p, q}. Mark every pair where exactly one of the two is an accept state — these are distinguishable by epsilon. Leave the rest blank for now.
- Now propagate. For each still-blank pair {p, q} and each symbol x in the alphabet, look at where they go: delta(p, x) and delta(q, x). If THAT destination pair is already marked, then {p, q} is distinguishable too (the witness is x followed by the destination's witness) — so mark {p, q}.
- Sweep through the whole table again and again. Every full sweep either adds at least one new mark or adds none. Stop the first time a sweep adds nothing — the marks have reached a fixed point.
- Merge. Every pair left unmarked is indistinguishable; gather the states into clumps where all members are mutually unmarked. Each clump becomes one state of the minimal DFA, with transitions and accept-status inherited from any member (they all agree).
DFA L = "strings of a,b whose length is even" (built clumsily with 4 states)
start q0 (accept, len 0)
q0 --a,b--> q1 q1 --a,b--> q2
q2 --a,b--> q3 q3 --a,b--> q0
accepting: q0, q2 (even length) non-accepting: q1, q3
TABLE (mark = distinguishable). Step 2: split accept vs non-accept.
q1 q2 q3
q0 X . X X = differ on epsilon (accept vs not)
q1 X . . = still blank
q2 X
Step 3 propagate on a (or b): is {q0,q2} distinguishable?
q0 -a-> q1 , q2 -a-> q3 . Pair {q1,q3} is blank -> no new mark yet.
is {q1,q3} distinguishable? q1 -a-> q2 , q3 -a-> q0 . {q2,q0} blank -> no mark.
Step 4: a full sweep adds NOTHING new. Fixed point reached.
Unmarked pairs: {q0,q2} and {q1,q3}. Merge:
A = {q0,q2} (accept) , B = {q1,q3} (reject)
A --a,b--> B , B --a,b--> A ==> minimal DFA has 2 states, not 4.Why the result is forced and unique
It would be a hollow victory if the algorithm just happened to make things small. The deep point is that the answer it produces is forced by the language itself, and this is where the Myhill-Nerode theorem from the last guide pays off. That theorem said: a language is regular exactly when its strings fall into finitely many distinguishable classes, and the count of those classes is the index of the language. The states of the minimal DFA are nothing other than those classes. The language hands you the classes; the machine has no freedom to invent fewer or more.
So minimization and Myhill-Nerode are two views of one fact. The theorem counts the classes abstractly (group strings by their future behavior); the table-filling algorithm computes the same classes mechanically by collapsing indistinguishable states. Because the number of classes is a property of the language, every DFA for that language — bloated or lean — must have at least that many states, and the minimal one hits the floor exactly. You cannot go below the index; the index is the hard lower bound on states, which is also why a clever Myhill-Nerode argument can prove a language needs many states or, when the classes are infinite, that it is not regular at all.
Uniqueness falls right out. Two minimal DFAs for the same language each have exactly index-many states, and you can match them up class by class: the class of strings reaching state p in one matches the class reaching some state p' in the other, transitions and accept-marks line up perfectly. That matching is an isomorphism — a faithful relabeling. So there really is just one minimal machine, and 'the smallest DFA' is a thing you can point at, not merely a thing you hope for.
Reading the cost, and the honest caveats
How expensive is finding the smallest DFA? The table-filling method touches every pair of states across repeated sweeps, which costs on the order of n^2 work for n states (each sweep is roughly n^2 cells, and you need at most n sweeps, but the careful bound is O(n^2) overall with the right bookkeeping). There is a faster, cleverer method due to Hopcroft that runs in about O(n log n) by refining partitions instead of scanning pairs. Either way, minimization is genuinely efficient — polynomial time — which is a pleasant contrast with how hard the same question becomes for nondeterministic machines.
Now the honest fine print. First, the cleanliness depends on starting from a DFA: you must determinize an NFA (via the subset construction) before minimizing, and that step can itself blow up exponentially — minimization is cheap, but reaching a DFA may not be. Second, the minimal NFA is a different and much nastier problem with no unique answer, so do not assume the DFA story transfers. Third, skipping step 1 quietly breaks everything: forget to delete unreachable states and you may 'minimize' to a machine that is not actually minimal.
And keep two old warnings in view. Minimizing never changes the language — fewer states, same accepted strings — and the result stays inside the regular family; a smaller machine is not a more powerful one. Smallest also still does not mean tiny: the minimal DFA for 'the n-th symbol from the end is a 1' provably needs 2^n states, because each of the 2^n possible last-n windows is its own indistinguishable class. The minimal DFA is the smallest honest machine, not a magic compressor — and exactly which languages force exponentially many classes is the kind of question the next rung, on context-free languages, picks up by handing the machine a stack.