Minimizing a DFA means finding the DFA with the fewest states that accepts exactly the same language. Every method does it in the same three steps:
- Remove the states you can't reach from the start state.
- Find which of the remaining states are equivalent: two states are equivalent when, for every input string, either both end in an accepting state or neither does.
- Merge each group of equivalent states into one state and redraw the transitions.
Step 2 is where the methods differ. This guide runs all three that courses teach on one example, so you can compare them line by line: the equivalence method (partition refinement, often written Π₀, Π₁, Π₂…), the table-filling method (Myhill–Nerode), and Hopcroft's algorithm. They always find the same groups. Every partition and table below was produced by the code behind the DFA Minimizer, which opens with this same example, so you can follow along in the tool.
The example DFA
This is the 8-state example from Hopcroft and Ullman's textbook. The alphabet is {0, 1}, A is the start state and C is the only accepting state.
| State | on 0 | on 1 |
|---|---|---|
| → A | B | F |
| B | G | C |
| * C | A | C |
| D | C | G |
| E | H | F |
| F | C | G |
| G | G | E |
| H | G | C |
Step 1: remove unreachable states
Search from A, following every transition: A reaches B and F; B reaches G and C; F reaches C and G; G reaches E; E reaches H. Nothing ever goes into D, so D is unreachable and is deleted.
This step matters even though D can't change the language. The equivalence methods only merge states that behave the same; an unreachable state that doesn't behave like any other state would survive as a useless extra state, and the result would not be minimal. (Here D happens to have exactly the same row as F, but you shouldn't rely on that.)
Seven states remain: A, B, C, E, F, G, H.
Step 2a: the equivalence method (Π₀, Π₁, Π₂…)
Start with two groups, accepting and non-accepting. Then repeat: for each state, look at which group each symbol sends it to. States in the same group that are sent to different groups must be split. Stop when a round splits nothing.
| Round | Groups |
|---|---|
| Π₀ | {C}, {A, B, E, F, G, H} |
| Π₁ | {C}, {A, E, G}, {B, H}, {F} |
| Π₂ | {C}, {A, E}, {G}, {B, H}, {F} |
| Π₃ | no change, so stop |
Π₀ to Π₁. Inside {A, B, E, F, G, H}, look at where 0 and 1 go:
- A → (B, F): both in the big group. E → (H, F) and G → (G, E): the same pattern.
- B → (G, C) and H → (G, C): 1 goes to {C}.
- F → (C, G): 0 goes to {C}.
So the big group breaks into {A, E, G}, {B, H} and {F}.
Π₁ to Π₂. Inside {A, E, G}: A goes on 0 to B, in {B, H}; E goes on 0 to H, also in {B, H}; but G goes on 0 to G, in {A, E, G}. G is split off. {B, H} stays together, because both go to G on 0 and C on 1.
Π₂ to Π₃. Nothing splits, so the final groups are {A, E}, {B, H}, {C}, {F}, {G}.
Step 2b: the table-filling method (Myhill–Nerode)
Draw a staircase table with one cell for every pair of states. Mark a pair when some string tells the two states apart:
- Round 0: mark every pair where one state accepts and the other doesn't (every pair with C).
- Round 1, 2, …: mark the pair (p, q) if some symbol sends p and q to a pair that is already marked.
- Stop when a round marks nothing. The unmarked pairs are equivalent.
Here each cell shows the round in which it was marked, and ≡ means never marked:
| A | B | C | E | F | G | |
|---|---|---|---|---|---|---|
| B | 1 | |||||
| C | 0 | 0 | ||||
| E | ≡ | 1 | 0 | |||
| F | 1 | 1 | 0 | 1 | ||
| G | 2 | 1 | 0 | 2 | 1 | |
| H | 1 | ≡ | 0 | 1 | 1 | 1 |
Two cells worked out:
- (A, B), round 1: on 1, A goes to F and B goes to C. (C, F) was marked in round 0, so (A, B) is marked.
- (A, G), round 2: on 0, A goes to B and G stays at G. (B, G) was only marked in round 1, so (A, G) can't be marked until round 2. That matches the equivalence method, where G left {A, E, G} in the second round.
Round 3 marks nothing. The unmarked cells are (A, E) and (B, H): the same two merges as before.
Step 2c: Hopcroft's algorithm
Hopcroft's algorithm refines the same partition, but it doesn't recheck every group every round. It keeps a waiting list of splitters. For a splitter group S and a symbol a, it finds the set X of states that move into S on a, then splits every group that has some states in X and some not.
- Start with the groups {C} and {A, B, E, F, G, H}, and put the smaller one, {C}, on the waiting list.
- Take a splitter S off the list. For each symbol a, find X, the states that go into S on a, and split every group that X cuts in two.
- When a group splits: if it was on the waiting list, put both halves on instead. If it wasn't, add only the smaller half.
- Stop when the waiting list is empty.
On the example (taking splitters first in, first out):
| Step | Splitter | Symbol | States moving into it | Split | Waiting list after |
|---|---|---|---|---|---|
| 1 | {C} | 0 | F | {A, B, E, F, G, H} → {F} and {A, B, E, G, H} | {F} |
| 2 | {C} | 1 | B, C, H | {A, B, E, G, H} → {B, H} and {A, E, G} | {F}, {B, H} |
| 3 | {F} | 0 | none | none | {B, H} |
| 4 | {F} | 1 | A, E | {A, E, G} → {A, E} and {G} | {B, H}, {G} |
| 5 | {B, H} | 0 | A, E | none | {G} |
| 6 | {B, H} | 1 | none | none | {G} |
| 7 | {G} | 0 | B, G, H | none | empty |
| 8 | {G} | 1 | F | none | empty |
Same final groups: {A, E}, {B, H}, {C}, {F}, {G}.
Rule 3 is the clever part. If the old group isn't waiting, splitting by it has already been accounted for. A state moves into the bigger half exactly when it moves into the old group but not into the smaller half, so splitting by the smaller half gives the bigger half's split for free. That is why Hopcroft's algorithm runs in O(k·n log n) time for n states and k symbols, against O(k·n²) for the round-by-round equivalence method on the worst inputs. On exam-sized DFAs the difference doesn't matter, and most exams ask for the equivalence or table-filling working; Hopcroft's matters for software that minimizes DFAs with thousands of states, such as regex engines and lexer generators.
Step 3: build the minimal DFA
Each group becomes one state. Its transitions are those of any member (they agree, which is what equivalent means). The group containing the old start state is the new start; groups containing an accepting state accept.
| State | on 0 | on 1 |
|---|---|---|
| → {A, E} | {B, H} | F |
| {B, H} | G | C |
| * C | {A, E} | C |
| F | C | G |
| G | G | {A, E} |
Eight states became five. The minimal DFA for a language is unique apart from the names of the states, so any correct method gives this same machine.
Common questions
Why remove unreachable states before running Hopcroft's algorithm? The partition methods only find which reachable behaviour is the same; they never delete a state. An unreachable state that isn't equivalent to any other state would stay in the answer, so the DFA would not be minimal. Removing unreachable states first takes one breadth-first search from the start state.
What about a DFA with missing transitions? A missing transition means the string is rejected, so add a dead (trap) state that every missing transition goes to and that loops to itself on every symbol, then minimize. If the dead state ends up alone in its group you can leave it out of the drawing again. The DFA Minimizer does both automatically and marks the added state ⊥.
What is the equivalence theorem in DFA minimization? It is the round-by-round method above: two states are k-equivalent if no string of length k or less tells them apart. Π₀ groups 0-equivalent states (accepting or not), each round goes from k to k + 1, and when Πₖ₊₁ equals Πₖ the groups are the equivalent states.
Do the table-filling method and Hopcroft's algorithm always agree? Yes. Both compute the same equivalence (the Myhill–Nerode relation, restricted to reachable states), so they always give the same groups. The DFA Minimizer runs the equivalence and table-filling methods on every input and shows both; its tests also compare Hopcroft's algorithm with them on hundreds of random DFAs.
Can I minimize an NFA the same way? No. Convert it to a DFA first with the subset construction, then minimize the DFA. Finding a smallest NFA is a much harder problem, with no known efficient general algorithm. The NFA to DFA converter and DFA Minimizer do the two steps, and the regex to NFA converter runs the whole pipeline from a regular expression to the minimal DFA.