Two DFAs can accept exactly the same language and still look completely different: one might have 4 states, another 8, with several states that "do the same job". In NFA to DFA Conversion (Subset Construction), subset construction gave us an 8-state DFA for a language that needs only 5. A designer working by hand can also easily add states that are not needed.
DFA minimization finds the DFA with the fewest possible states for a given regular language. The idea is simple: find states that can never be told apart by any future input, and merge them.
DFA minimization converts a DFA into an equivalent DFA with the minimum number of states, by removing unreachable states and merging all groups of equivalent (indistinguishable) states. For every regular language this minimal DFA is unique, up to renaming of states.
In this chapter we will define equivalent states, minimise a DFA with the partition (equivalence) method and with the table-filling method, and connect it all to the Myhill–Nerode theorem, which also tells us how many states a language really needs. All tables were computed by a program, and the minimised DFAs were checked against the originals on every string up to length 14.
When Are Two States "the Same"?
Picture two states p and q. Start one copy of the machine in p and another in q, and feed both the same remaining input w. If, for every possible w, both copies agree (both accept or both reject), then nothing in the future can tell p and q apart. They are interchangeable.
States p and q are equivalent (p ≡ q) if for every string w ∈ Σ*, δ̂(p, w) ∈ F exactly when δ̂(q, w) ∈ F. Otherwise they are distinguishable, and any string w on which they disagree is a distinguishing string.
Two quick consequences:
Taking w = ε, a final and a non-final state are always distinguishable. This is the starting point of both algorithms.
If p and q are distinguishable by w, and r –a→ p, s –a→ q, then r and s are distinguishable by aw. Distinguishability propagates backwards along arrows. Both algorithms exploit this.
Equivalence ≡ is an equivalence relation (reflexive, symmetric, transitive), so it splits the states into groups. The minimal DFA has one state per group.
k-equivalence
Checking "every string" directly is impossible, so we build up by length:
p ≡0 q if both are final or both are non-final (they agree on ε).
p ≡k q if they agree on every string of length ≤ k. Equivalently: p ≡k−1 q, and for every symbol a, δ(p, a) ≡k−1 δ(q, a).
Each round can only split groups, never merge them. With n states there can be at most n groups, so after at most n − 2 refinement rounds the partition stops changing. When Pk = Pk+1, we have found ≡.
Step 0: Remove Unreachable States
A state that cannot be reached from the start state on any input contributes nothing to the language. Remove it first by a simple graph search from q0.
This matters: the equivalence algorithms only merge equivalent states. An unreachable state that is not equivalent to anything would survive and leave the DFA non-minimal.
Running Example
Σ = {0, 1}, start state A, final states C, F, G:
State | 0 | 1 |
|---|---|---|
→ A | F | G |
B | B | B |
* C | G | A |
D | C | G |
E | E | B |
* F | G | D |
* G | C | E |
H | A | B |
Step 0 (reachability). From A we reach F and G; from F, D; from G, C and E; from E, B. So the reachable states are A, B, C, D, E, F, G. No arrow enters H, so H is unreachable. Delete it.
Method 1: Partition (Equivalence) Method
Also called the equivalence-class method or Moore's algorithm.
P0 = { non-final states, final states }
repeat:
for each group G in the current partition:
for each state q in G, write its "signature":
the group of δ(q, a) for every symbol a
split G so that states with the same signature stay together
until the partition does not changeP0
P0 = { A, B, D, E } { C, F, G }
group I group IIP1
For each state, look up which P0 group its 0-successor and 1-successor are in:
State | On 0 → (group) | On 1 → (group) | Signature |
|---|---|---|---|
A | F (II) | G (II) | (II, II) |
B | B (I) | B (I) | (I, I) |
D | C (II) | G (II) | (II, II) |
E | E (I) | B (I) | (I, I) |
C | G (II) | A (I) | (II, I) |
F | G (II) | D (I) | (II, I) |
G | C (II) | E (I) | (II, I) |
Group I splits by signature into {A, D} and {B, E}. Group II stays together (all three have (II, I)).
P1 = { A, D } { B, E } { C, F, G }P2
Now use the P1 groups, numbered 1 = {A, D}, 2 = {B, E}, 3 = {C, F, G}:
State | On 0 → (group) | On 1 → (group) | Signature |
|---|---|---|---|
A | F (3) | G (3) | (3, 3) |
D | C (3) | G (3) | (3, 3) |
B | B (2) | B (2) | (2, 2) |
E | E (2) | B (2) | (2, 2) |
C | G (3) | A (1) | (3, 1) |
F | G (3) | D (1) | (3, 1) |
G | C (3) | E (2) | (3, 2) |
G now differs from C and F: on input 1, C and F go to group 1 but G goes to group 2.
P2 = { A, D } { B, E } { C, F } { G }P3
Check again with the P2 groups. A → (F, G) and D → (C, G): both go to ({C, F}, {G}). B and E both stay in {B, E}. C → (G, A) and F → (G, D): both go to ({G}, {A, D}). Nothing splits, so P3 = P2 and we stop.
Building the minimal DFA
Each group becomes one state. The start state is the group containing A; a group is final if its states are final (all states in a group are either all final or all non-final, because we started from that split). Transitions are taken from any member of the group:
Minimal state | 0 | 1 |
|---|---|---|
→ [AD] | [CF] | [G] |
[BE] | [BE] | [BE] |
* [CF] | [G] | [AD] |
* [G] | [CF] | [BE] |
──► [AD] ──0──► ((CF)) ──0──► ((G)) ──1──► [BE] ⟲ 0,1
remaining arrows:
[AD] ──1──► ((G))
((CF)) ──1──► [AD]
((G)) ──0──► ((CF))8 states became 4. Notice that [BE] is a dead state: B and E were two separate traps in the original DFA, and minimization merged them, as it always merges all dead states into one.
Method 2: Table-Filling (Pair-Marking) Method
This method, the one presented in Hopcroft–Ullman style textbooks (and closely tied to the Myhill–Nerode theorem below), works on pairs of states instead of groups.
1. Draw a triangular table with one cell for every unordered pair {p, q}.
2. Mark every pair where one state is final and the other is not.
3. Repeat until no new marks appear:
for every unmarked pair {p, q} and every symbol a:
if {δ(p,a), δ(q,a)} is marked, mark {p, q}.
4. Unmarked pairs are equivalent. Merge them.We work on the 7 reachable states. Below, each cell shows the round in which the pair was marked (0 = final vs non-final), and "=" for pairs never marked:
A B C D E F
B 1
C 0 0
D = 1 0
E 1 = 0 1
F 0 0 = 0 0
G 0 0 2 0 0 2How the marks were made:
Round 0: every pair with one state from {C, F, G} and one from {A, B, D, E}: 12 pairs.
Round 1: {A, B}: on 0 they go to {F, B}, already marked. {A, E}: on 0 → {F, E}, marked. {B, D}: on 0 → {B, C}, marked. {D, E}: on 0 → {C, E}, marked.
Round 2: {C, G}: on 1 → {A, E}, marked in round 1. {F, G}: on 1 → {D, E}, marked in round 1.
Round 3: check the remaining unmarked pairs {A, D}, {B, E}, {C, F}. {A, D} → {F, C} on 0 and {G, G} on 1; {B, E} → {B, E} on 0 and {B, B} on 1; {C, F} → {G, G} on 0 and {A, D} on 1. None leads to a marked pair, so nothing changes and we stop.
Unmarked pairs: {A, D}, {B, E}, {C, F}. G is not equivalent to anything. Same answer as the partition method: [AD], [BE], [CF], [G].
The round numbers carry meaning: a pair marked in round k is distinguished by a string of length k. For example {C, G} (round 2) is distinguished by a 2-symbol string starting with 1: C –1→ A –0→ F (final), but G –1→ E –0→ E (non-final). So "10" separates them.
Partition method vs table-filling method
Aspect | Partition method | Table-filling method |
|---|---|---|
Works on | Groups of states | Pairs of states |
Starts from | {non-final}, {final} | All (final, non-final) pairs marked |
Step | Split groups by signature | Mark a pair if some symbol leads to a marked pair |
Hand work | Usually faster for exams | More cells (n(n−1)/2) but very mechanical |
Bonus information | Gives the groups directly | Shows which pairs are distinguishable and how early |
Result | Identical: the same equivalence classes | |
For large automata, Hopcroft's algorithm refines partitions cleverly and runs in O(|Σ| · n log n) time; the simple methods above are O(|Σ| · n2) per pass or worse, which is fine by hand.
Example 2: Minimising a Subset-Construction DFA
For "strings over {a, b} containing abb", subset construction from a 4-state NFA gives this 6-state DFA:
State | a | b |
|---|---|---|
→ S0 | S1 | S0 |
S1 | S1 | S2 |
S2 | S1 | S3 |
* S3 | S4 | S3 |
* S4 | S4 | S5 |
* S5 | S4 | S3 |
P0 = {S0, S1, S2} {S3, S4, S5}
P1: S0 → (I, I) S1 → (I, I) S2 → (I, II) finals all → (II, II)
= {S0, S1} {S2} {S3, S4, S5}
P2: S0 → ({S0,S1}, {S0,S1}) S1 → ({S0,S1}, {S2}) → split
= {S0} {S1} {S2} {S3, S4, S5}
P3: no change.The three final states merge into one ("abb already seen"), giving the familiar 4-state minimal DFA: S0 = "no progress", S1 = "seen a", S2 = "seen ab", [S3 S4 S5] = "seen abb".
The Myhill–Nerode Theorem
Minimization has a beautiful theory behind it. For a language L, call two strings x and y L-equivalent (x ≡L y) if no suffix can tell them apart:
x ≡_L y ⟺ for every z ∈ Σ*: xz ∈ L exactly when yz ∈ LMyhill–Nerode theorem: L is regular if and only if ≡L has finitely many equivalence classes. Moreover, the number of classes equals the number of states of the minimal DFA for L, and that minimal DFA is unique up to renaming of states.
Why it is useful:
Lower bounds. If you find k strings that are pairwise distinguishable (for each pair, some suffix separates them), every DFA for L needs at least k states. For "the 3rd symbol from the end is 1", the 8 strings of length 3 are pairwise distinguishable (if x and y differ in the i-th symbol from the end, append 3 − i more symbols so that this position becomes the 3rd from the end: one string is then accepted and the other is not), so 8 states are necessary.
Proving non-regularity. If you find infinitely many pairwise distinguishable strings, L is not regular. For L = {anbn}, the strings a, aa, aaa, … are pairwise distinguishable (aibi ∈ L but ajbi ∉ L for i ≠ j). This is an alternative to the method in Pumping Lemma for Regular Languages.
Checking DFA equivalence. Two DFAs accept the same language exactly when their minimal DFAs are identical after renaming.
Minimal State Counts Worth Remembering
Each number below was verified by counting Myhill–Nerode classes by program. "States" always includes the dead state when one is needed.
Language | Minimal DFA states |
|---|---|
Strings over {a, b} of length exactly n | n + 2 (e.g. 5 for n = 3) |
Length ≥ n | n + 1 (e.g. 4 for n = 3) |
Length ≤ n | n + 2 (e.g. 5 for n = 3) |
Starts with a fixed string of length n (e.g. ab) | n + 2 (4 for ab) |
Ends with / contains a fixed string of length n (e.g. abb, abab) | n + 1 (4 for abb, 5 for abab) |
n-th symbol from the end is 1 | 2n (16 for n = 4) |
#a ≡ 0 (mod 2) and #b ≡ 0 (mod 3) | 2 × 3 = 6 |
Binary numbers divisible by 5, with ε read as 0 | 5 |
Same, but ε must be rejected | 6 (a separate start state) |
Non-empty strings over {a, b} that start and end with the same symbol | 5 |
The "length exactly n", "length ≤ n" and "starts with" cases need a dead state; "length ≥ n" and "ends with / contains" do not. That is where the +1 differences come from.
Common Mistakes
Skipping Step 0. Unreachable states may survive the equivalence algorithms and make the answer non-minimal.
Merging states just because they have the same transitions in one round. You must iterate until the partition is stable.
Comparing successor states instead of successor groups. Two states with signatures (F, G) and (C, G) are still alike if F and C are in the same current group.
Starting with all states in one group. The first split is always final vs non-final.
Forgetting the dead state when counting minimal states. A complete DFA must have a move for every symbol.
Applying these algorithms to an NFA. They are for DFAs. Convert first. (Minimising NFAs exactly is computationally hard: it is PSPACE-complete.)
Thinking the minimal DFA depends on the method. It is unique up to state names.
Practice and GATE-Style Questions
Q1. A DFA over {0, 1} has states q0…q3 with δ(q, x) = (2q + x) mod 4, start q0, finals {q0, q2}. How many states does the minimal DFA have?
The machine computes the value mod 4, and the value is even exactly when the last bit is 0. So it accepts strings ending in 0, or ε. Partition: P0 = {q1, q3}, {q0, q2}. On 0 every state goes to q0 or q2 (final group); on 1 every state goes to q1 or q3. No split happens. 2 states.
Q2. What is the number of states in the minimal DFA accepting strings over {a, b} whose length is exactly 4?
6: states for lengths 0, 1, 2, 3, 4 read so far (the last one final), plus a dead state for length ≥ 5.
Q3. True or false: if two states p, q are both non-final and δ(p, a) = δ(q, a) for every symbol a, then p ≡ q.
True. They agree on ε (both reject), and after any first symbol they are in the very same state, so they agree on every longer string too.
Q4. Find a string that distinguishes [AD] from [CF] and one that distinguishes [CF] from [G] in the running example.
[AD] is non-final and [CF] is final, so ε distinguishes them. For [CF] vs [G]: on 1, [CF] → [AD], then 0 → [CF] (final); [G] → [BE] (dead) → [BE]. So 10 distinguishes them.
Q5. Using Myhill–Nerode, show that L = { w ∈ {a, b}* : #a(w) = #b(w) } is not regular.
Take the strings ai for i = 0, 1, 2, …. For i ≠ j, the suffix bi gives aibi ∈ L but ajbi ∉ L. So infinitely many strings are pairwise distinguishable, ≡L has infinitely many classes, and L is not regular.
Q6. Interview: why is the minimal DFA unique, while minimal NFAs are not?
The states of the minimal DFA correspond one-to-one to the Myhill–Nerode classes of L, which depend only on the language, and the transitions between classes are forced. An NFA state does not have to correspond to a single class (it can be part of several possible "guesses"), so different, non-isomorphic NFAs of the same minimum size can exist.
Summary
Two states are equivalent if no input string can make one accept and the other reject.
Minimization = remove unreachable states + merge equivalent states.
Partition method: start with {non-final}, {final}; split groups by the groups of their successors; repeat until stable.
Table-filling method: mark (final, non-final) pairs; mark a pair if a symbol leads to a marked pair; unmarked pairs are equivalent.
Both methods give the same result; all dead states merge into one.
Myhill–Nerode: L is regular iff it has finitely many classes; the minimal DFA has one state per class and is unique.
Pairwise distinguishable strings give lower bounds on DFA size and proofs of non-regularity.
If no future input can tell two states apart, they are the same state. Split by final vs non-final, keep splitting by where the arrows go, and stop when nothing changes.