Minimization of DFA
Learn to shrink any DFA to its smallest equivalent form using the table-filling algorithm — one worked example from 6 states down to 3, explained step by step.
Why Minimize a DFA?
When we construct a DFA — especially from an NFA via subset construction — the result often contains redundant states: states that are never visited, or states that behave identically for every possible future input.
DFA minimization removes all such redundancy, giving the smallest DFA that still accepts the exact same language.
| Without Minimization | With Minimization |
|---|---|
| Extra states from NFA conversion | Only the essential states remain |
| Slower simulation in a lexer | Fastest possible simulation |
| Hard to compare two DFAs directly | Unique canonical form — compare structurally |
The minimal DFA for any regular language is unique (up to renaming of states). No matter what DFA you start with — large, redundant, built from NFA conversion — minimization always produces the same canonical result.
The Big Picture
Minimization fits into the compiler pipeline right after NFA-to-DFA conversion:
The Core Idea: Equivalent States
Two states p and q are equivalent if no input string can distinguish them — reading any string from either state always produces the same accept/reject outcome:
If p ≡ q, they can be merged into one state without changing the language.
Conversely, p and q are distinguishable if there exists some string w (called a distinguishing string) where one accepts and the other rejects:
The Key Observation — Base Case
The simplest distinguishing string is ε (the empty string):
- If p is an accepting state and q is not (or vice versa) → they behave differently right now → immediately distinguishable.
- If both are accepting, or both are non-accepting → they agree on ε, but may still differ on longer strings.
This base case seeds the algorithm. Everything else is discovered by propagation.
Propagating Distinguishability
Here is the key insight that makes the algorithm work:
If reading symbol a from state p leads to state r, and reading a from state q leads to state s, and we already know r ≠ s (distinguishable) — then p ≠ q must also be true.
Why? Because the string a·w (where w distinguishes r from s) also distinguishes p from q. Distinguishability propagates backwards through transitions.
The DFA We Will Minimize
Language: aba — all strings over {a, b} with exactly one 'b'
Accepted: "b", "ab", "ba", "aba", "aab", "abaa", "aaab", ... Rejected: "a", "bb", "bab", "aabb", "", ...
The Original (Over-Built) DFA
This DFA was built by someone who tracked the parity of 'a's seen — which turns out to be completely irrelevant to the language aba. This unnecessary tracking creates redundant states.
| State | Meaning | Accepting? |
|---|---|---|
| A | No 'b' seen yet; even number of 'a's so far | No |
| B | No 'b' seen yet; odd number of 'a's so far | No |
| C | Saw 'b' — came from state A (even a's before b) | Yes |
| D | Saw 'b' — came from state B (odd a's before b) | Yes |
| E | Saw exactly one 'b' and then at least one 'a' | Yes |
| F | Dead state — saw more than one 'b' | No |
Transition table:
| State | a | b | Start? | Accept? |
|---|---|---|---|---|
| A | B | C | → | |
| B | A | D | ||
| C | E | F | ✓ | |
| D | E | F | ✓ | |
| E | E | F | ✓ | |
| F | F | F |
DFA diagram:
Can you spot the redundancy?
- States C, D, and E all have identical transitions (both go to E on 'a', both go to F on 'b') and are all accepting → they should collapse into one.
- States A and B mirror each other (A goes to B on 'a', B goes back to A on 'a') and both lead to an accepting state on 'b' → they should collapse into one.
Let's prove this formally with the table-filling algorithm.
Before We Start — Remove Unreachable States
Before applying the table-filling algorithm, remove any states that cannot be reached from the start state. Unreachable states can never participate in any computation.
Check reachability (BFS from A):
| Order | State dequeued | Neighbours added / noted |
|---|---|---|
| 1 | A | B, C (enqueue B, C) |
| 2 | B | A (seen); D (enqueue D) |
| 3 | C | E, F (enqueue E, F) |
| 4 | D | E, F (already in queue or seen) |
| 5 | E | E, F (already seen) |
| 6 | F | F, F (self-loops only) |
Reachable set: { A, B, C, D, E, F } — all six states.
All states are reachable. Nothing to remove — proceed with all 6.
Step 1 — Build the Table and Mark Base Pairs
Create a distinguishability table: one row per unordered pair of distinct states (lexicographic order is easy to check in exams).
With 6 states, we have C(6,2) = 15 pairs total. The distinguishability table lists every unordered pair once (lexicographic order). A blank cell means “not yet known to be distinguishable”; ✗ means distinguishable.
Distinguishability table — empty template (all pairs):
| Pair | Mark |
|---|---|
| {A, B} | |
| {A, C} | |
| {A, D} | |
| {A, E} | |
| {A, F} | |
| {B, C} | |
| {B, D} | |
| {B, E} | |
| {B, F} | |
| {C, D} | |
| {C, E} | |
| {C, F} | |
| {D, E} | |
| {D, F} | |
| {E, F} |
Initial Marking — Base Case
Rule: Mark any pair {p, q} where exactly one is an accepting state. These are distinguishable by ε — one accepts immediately, the other doesn't.
| States | |
|---|---|
| Accepting | { C, D, E } |
| Non-accepting | { A, B, F } |
Pairs marked in the base step (one accepting, one not):
| Pair | Reason (short) |
|---|---|
| {A, C} | A non-acc., C acc. |
| {A, D} | A non-acc., D acc. |
| {A, E} | A non-acc., E acc. |
| {B, C} | B non-acc., C acc. |
| {B, D} | B non-acc., D acc. |
| {B, E} | B non-acc., E acc. |
| {C, F} | C acc., F non-acc. |
| {D, F} | D acc., F non-acc. |
| {E, F} | E acc., F non-acc. |
Distinguishability table after initial marking (✗ = distinguishable, blank = still unknown):
| Pair | Mark |
|---|---|
| {A, B} | |
| {A, C} | ✗ |
| {A, D} | ✗ |
| {A, E} | ✗ |
| {A, F} | |
| {B, C} | ✗ |
| {B, D} | ✗ |
| {B, E} | ✗ |
| {B, F} | |
| {C, D} | |
| {C, E} | |
| {C, F} | ✗ |
| {D, E} | |
| {D, F} | ✗ |
| {E, F} | ✗ |
9 pairs marked, 6 pairs remain blank — these might be equivalent: {A, B}, {A, F}, {B, F}, {C, D}, {C, E}, {D, E}.
Step 2 — Propagate Distinguishability
Now check every blank pair. For each blank pair {p, q} and each symbol a ∈ {a, b}:
| Step | Action |
|---|---|
| 1 | Let r = δ(p, a) and s = δ(q, a). |
| 2 | If the pair {r, s} is already marked in the table, then mark {p, q}. |
We check all 6 blank pairs below. Steps are shown in dependency order.
Check {A, F}
| Symbol | δ(A, ·) | δ(F, ·) | Resulting Pair | Already Marked? |
|---|---|---|---|---|
| a | B | F | {B, F} | No |
| b | C | F | {C, F} | Yes ✗ |
→ {C, F} is marked. MARK {A, F} ✗
Intuition: reading 'b' from A reaches the accepting state C, but from F stays in the dead state F. They diverge — so A ≠ F.
Check {B, F}
| Symbol | δ(B, ·) | δ(F, ·) | Resulting Pair | Already Marked? |
|---|---|---|---|---|
| a | A | F | {A, F} | Yes ✗ (just marked) |
| b | D | F | {D, F} | Yes ✗ |
→ {A, F} is now marked. MARK {B, F} ✗
Check {C, D}
| Symbol | δ(C, ·) | δ(D, ·) | Resulting Pair | Already Marked? |
|---|---|---|---|---|
| a | E | E | {E, E} — same state | Skip |
| b | F | F | {F, F} — same state | Skip |
Both transitions lead to the same destination state — there's no pair to check. {C, D} stays blank.
Check {C, E}
| Symbol | δ(C, ·) | δ(E, ·) | Resulting Pair | Already Marked? |
|---|---|---|---|---|
| a | E | E | {E, E} — same state | Skip |
| b | F | F | {F, F} — same state | Skip |
{C, E} stays blank.
Check {D, E}
| Symbol | δ(D, ·) | δ(E, ·) | Resulting Pair | Already Marked? |
|---|---|---|---|---|
| a | E | E | {E, E} — same state | Skip |
| b | F | F | {F, F} — same state | Skip |
{D, E} stays blank.
Check {A, B}
| Symbol | δ(A, ·) | δ(B, ·) | Resulting Pair | Already Marked? |
|---|---|---|---|---|
| a | B | A | {A, B} — same pair being checked | Skip |
| b | C | D | {C, D} | No — blank |
{C, D} is still blank — can't use it to mark {A, B}. {A, B} stays blank.
Do Another Pass?
After marking {A, F} and {B, F}, do any other pairs now become markable? The only blank pair that might still pick up a mark is {A, B}:
| Symbol | δ(A, ·) | δ(B, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| a | B | A | {A, B} | No (same pair under check) |
| b | C | D | {C, D} | No — still blank |
No new marks possible. Algorithm terminates.
Final distinguishability table (algorithm finished)
| Pair | Mark |
|---|---|
| {A, B} | |
| {A, C} | ✗ |
| {A, D} | ✗ |
| {A, E} | ✗ |
| {A, F} | ✗ |
| {B, C} | ✗ |
| {B, D} | ✗ |
| {B, E} | ✗ |
| {B, F} | ✗ |
| {C, D} | |
| {C, E} | |
| {C, F} | ✗ |
| {D, E} | |
| {D, F} | ✗ |
| {E, F} | ✗ |
The four blank pairs are pairwise equivalent:
| Blank pair | Meaning |
|---|---|
| {A, B} | A ≡ B |
| {C, D} | C ≡ D |
| {C, E} | C ≡ E |
| {D, E} | D ≡ E |
Since {C, D}, {C, E}, and {D, E} are all blank, states C, D, and E form one equivalence class.
Step 3 — Merge Equivalent States and Build the Minimal DFA
Read off the equivalence classes from the blank pairs. Each class becomes one state in the minimal DFA.
| Equivalence class | States merged | New state name |
|---|---|---|
| 1 | { A, B } | [AB] |
| 2 | { C, D, E } | [CDE] |
| 3 | { F } | [F] |
Compute New Transitions
For each new state, pick any representative and look up its transitions. (All members of an equivalence class have the same transitions — that's what makes them equivalent. We verify this below.)
Transitions of [AB] — from representative A, then checked on B:
| Symbol | δ(A, ·) | Maps to class | δ(B, ·) | Maps to class | δ on [AB] |
|---|---|---|---|---|---|
| a | B | [AB] | A | [AB] | [AB] |
| b | C | [CDE] | D | [CDE] | [CDE] |
Transitions of [CDE] — from C, D, and E:
| Symbol | δ(C, ·) | class | δ(D, ·) | class | δ(E, ·) | class | δ on [CDE] |
|---|---|---|---|---|---|---|---|
| a | E | [CDE] | E | [CDE] | E | [CDE] | [CDE] |
| b | F | [F] | F | [F] | F | [F] | [F] |
Transitions of [F]:
| Symbol | δ(F, ·) | class | δ on [F] |
|---|---|---|---|
| a | F | [F] | [F] |
| b | F | [F] | [F] |
Minimal DFA — Transition Table
| State | a | b | Start? | Accept? |
|---|---|---|---|---|
| [AB] | [AB] | [CDE] | → | |
| [CDE] | [CDE] | [F] | ✓ | |
| [F] | [F] | [F] |
| Role in minimal DFA | State | Reason |
|---|---|---|
| Start | [AB] | Original start A lies in class [AB]. |
| Accepting | [CDE] | Class contains C, D, and E, all accepting in the original DFA. |
Minimal DFA — Diagram
6 states → 3 states. Same language. Zero compromise.
Verify the Minimal DFA on Sample Strings
| String | Trace (high level) | Final state | Result |
|---|---|---|---|
| b | [AB] →b→ [CDE] | [CDE] | Accepted ✓ |
| ab | [AB] →a→ [AB] →b→ [CDE] | [CDE] | Accepted ✓ |
| ba | [AB] →b→ [CDE] →a→ [CDE] | [CDE] | Accepted ✓ |
| aba | [AB] →a→ [AB] →b→ [CDE] →a→ [CDE] | [CDE] | Accepted ✓ |
| aab | [AB] →a→ [AB] →a→ [AB] →b→ [CDE] | [CDE] | Accepted ✓ |
| ε | [AB] | [AB] | Rejected ✗ |
| a | [AB] →a→ [AB] | [AB] | Rejected ✗ |
| bb | [AB] →b→ [CDE] →b→ [F] | [F] | Rejected ✗ |
| bab | [AB] →b→ [CDE] →a→ [CDE] →b→ [F] | [F] | Rejected ✗ |
| aabb | [AB] →a→ [AB] →a→ [AB] →b→ [CDE] →b→ [F] | [F] | Rejected ✗ |
All correct — the language aba is preserved exactly.
Algorithm Summary and Key Properties
The Full Algorithm — Recap
| Input / output | |
|---|---|
| Input | DFA M = (Q, Σ, δ, q₀, F) |
| Output | A minimal DFA for the same language |
| Step | Name | What you do |
|---|---|---|
| 0 | Remove unreachable states | Run BFS/DFS from q₀; discard states never reached. |
| 1 | Build pair table; base marks | List every unordered pair {p, q}. Mark {p, q} if exactly one of p, q is in F (distinguishable by ε). |
| 2 | Propagate | Repeat until nothing changes: for each unmarked {p, q} and each a ∈ Σ, let r = δ(p, a), s = δ(q, a); if {r, s} is marked, mark {p, q}. |
| 3 | Merge | Every unmarked pair at the end denotes equivalent states. Group into classes; one minimal state per class. Start = class of q₀; accept = any class that contains a state from F. |
What Happened in Our Example
| Original State(s) | Merged Into | Reason |
|---|---|---|
| A, B | [AB] | Both "no 'b' seen yet" — parity of 'a's is irrelevant |
| C, D, E | [CDE] | All "exactly one 'b' seen" — history before 'b' is irrelevant |
| F | [F] | Only dead state, nothing to merge with |
The 6-state DFA had redundancy baked in from tracking unnecessary information. Minimization strips that away, exposing the true 3-state structure.
Uniqueness of the Minimal DFA
For any regular language L, there is exactly one minimal DFA (up to renaming of states). This is guaranteed by the Myhill-Nerode theorem.
Practical consequence: To check whether two DFAs accept the same language, minimize both and compare. If the minimized DFAs are identical (same structure, just different state names), the languages are equal.
When is a DFA Already Minimal?
A DFA is already minimal if and only if:
- All states are reachable from the start state.
- No two distinct states are equivalent — the table-filling algorithm marks every single pair.
Dead States in Minimization
All dead states (trap states) are equivalent to each other. A dead state d satisfies:
| Property | Condition |
|---|---|
| Non-accepting | d ∉ F |
| Trap | δ(d, a) = d for every a ∈ Σ |
If a DFA has multiple dead states, minimization always merges them into one. This is the one case where you get a free reduction without the algorithm needing to find it explicitly — they're all non-accepting and loop on everything, so they're trivially equivalent.
Practice questions
Try the table-filling method yourself on a fresh DFA, then compare with the worked answer below.
Question 1
Minimize the following DFA using the table-filling algorithm.
Given: M = (Q, Σ, δ, q₀, F) where
- Q = {q₀, q₁, q₂, q₃, q₄}
- Σ = {0, 1}
- Start state: q₀
- Final states: F = {q₄}
Transition table:
| State | on 0 | on 1 |
|---|---|---|
| q₀ | q₁ | q₃ |
| q₁ | q₂ | q₄ |
| q₂ | q₁ | q₄ |
| q₃ | q₂ | q₄ |
| q₄ | q₄ | q₄ |
State diagram:
Answer
Written in short exam-style steps.
Step 1 — Remove unreachable states
I start from q₀ and list one-step transitions to see reachability.
| From state | on 0 → | on 1 → |
|---|---|---|
| q₀ | q₁ | q₃ |
| q₁ | q₂ | q₄ |
| q₂ | q₁ | q₄ |
| q₃ | q₂ | q₄ |
| q₄ | q₄ | q₄ |
From q₀ I can reach q₁, q₂, q₃, q₄ (directly or in a few steps). So every state is reachable. I do not delete any state.
Step 2 — Build the pair table (only i < j)
States in order: q₀, q₁, q₂, q₃, q₄. There are C(5,2) = 10 unordered pairs. The table below lists every pair once (lexicographic order).
Distinguishability table — before any marking:
| Pair | Mark |
|---|---|
| {q₀, q₁} | |
| {q₀, q₂} | |
| {q₀, q₃} | |
| {q₀, q₄} | |
| {q₁, q₂} | |
| {q₁, q₃} | |
| {q₁, q₄} | |
| {q₂, q₃} | |
| {q₂, q₄} | |
| {q₃, q₄} |
Step 3 — Base marking (accept vs non-accept)
Only q₄ is accepting. Any pair where exactly one state is final must be marked (distinguishable by the empty string ε).
Pairs marked in the base step:
| Pair | Reason |
|---|---|
| {q₀, q₄} | q₀ non-final, q₄ final |
| {q₁, q₄} | q₁ non-final, q₄ final |
| {q₂, q₄} | q₂ non-final, q₄ final |
| {q₃, q₄} | q₃ non-final, q₄ final |
Distinguishability table after base marking:
| Pair | Mark |
|---|---|
| {q₀, q₁} | |
| {q₀, q₂} | |
| {q₀, q₃} | |
| {q₀, q₄} | ✗ |
| {q₁, q₂} | |
| {q₁, q₃} | |
| {q₁, q₄} | ✗ |
| {q₂, q₃} | |
| {q₂, q₄} | ✗ |
| {q₃, q₄} | ✗ |
Step 4 — Propagation (first pass)
Rule: For a blank pair {p, q}, if for some symbol a ∈ {0, 1} the pair {δ(p, a), δ(q, a)} is already marked, then I mark {p, q}.
For each blank pair I fill a small table: columns are symbol, δ(first state, symbol), δ(second state, symbol), the unordered pair of successors, and whether that pair is already marked in the table.
Pair {q₀, q₁}
| Symbol | δ(q₀, ·) | δ(q₁, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₁ | q₂ | {q₁, q₂} | No |
| 1 | q₃ | q₄ | {q₃, q₄} | Yes ✗ |
Because {q₃, q₄} is marked, I mark {q₀, q₁}.
Pair {q₀, q₂}
| Symbol | δ(q₀, ·) | δ(q₂, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₁ | q₁ | {q₁, q₁} — same state | — |
| 1 | q₃ | q₄ | {q₃, q₄} | Yes ✗ |
So I mark {q₀, q₂}.
Pair {q₀, q₃}
| Symbol | δ(q₀, ·) | δ(q₃, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₁ | q₂ | {q₁, q₂} | No |
| 1 | q₃ | q₄ | {q₃, q₄} | Yes ✗ |
So I mark {q₀, q₃}.
Pair {q₁, q₂}
| Symbol | δ(q₁, ·) | δ(q₂, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₂ | q₁ | {q₁, q₂} — same pair under check | No |
| 1 | q₄ | q₄ | same state | — |
No successor pair is marked → leave {q₁, q₂} blank in this pass.
Pair {q₁, q₃}
| Symbol | δ(q₁, ·) | δ(q₃, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₂ | q₂ | same state | — |
| 1 | q₄ | q₄ | same state | — |
Leave {q₁, q₃} blank.
Pair {q₂, q₃}
| Symbol | δ(q₂, ·) | δ(q₃, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₁ | q₂ | {q₁, q₂} | No |
| 1 | q₄ | q₄ | same state | — |
Leave {q₂, q₃} blank.
Summary of first pass: marked {q₀, q₁}, {q₀, q₂}, {q₀, q₃}. Still blank among non-final pairs: {q₁, q₂}, {q₁, q₃}, {q₂, q₃}.
Distinguishability table after the first propagation pass:
| Pair | Mark |
|---|---|
| {q₀, q₁} | ✗ |
| {q₀, q₂} | ✗ |
| {q₀, q₃} | ✗ |
| {q₀, q₄} | ✗ |
| {q₁, q₂} | |
| {q₁, q₃} | |
| {q₁, q₄} | ✗ |
| {q₂, q₃} | |
| {q₂, q₄} | ✗ |
| {q₃, q₄} | ✗ |
Step 5 — Second pass (nothing new)
I run the same table check again for every pair that is still blank: {q₁, q₂}, {q₁, q₃}, {q₂, q₃}. (No new marks appeared in pass 1 that would change these rows, but I still verify symbol by symbol.)
Pair {q₁, q₂} — pass 2
| Symbol | δ(q₁, ·) | δ(q₂, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₂ | q₁ | {q₁, q₂} | No |
| 1 | q₄ | q₄ | same state | — |
Pair {q₁, q₃} — pass 2
| Symbol | δ(q₁, ·) | δ(q₃, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₂ | q₂ | same state | — |
| 1 | q₄ | q₄ | same state | — |
Pair {q₂, q₃} — pass 2
| Symbol | δ(q₂, ·) | δ(q₃, ·) | Successor pair | Already marked? |
|---|---|---|---|---|
| 0 | q₁ | q₂ | {q₁, q₂} | No |
| 1 | q₄ | q₄ | same state | — |
In every row, either the successors coincide, or the successor pair is {q₁, q₂}, which is still not marked. So no new cell is marked and the algorithm stops.
Distinguishability table — final (same as end of pass 1):
| Pair | Mark |
|---|---|
| {q₀, q₁} | ✗ |
| {q₀, q₂} | ✗ |
| {q₀, q₃} | ✗ |
| {q₀, q₄} | ✗ |
| {q₁, q₂} | |
| {q₁, q₃} | |
| {q₁, q₄} | ✗ |
| {q₂, q₃} | |
| {q₂, q₄} | ✗ |
| {q₃, q₄} | ✗ |
Step 6 — Read equivalence classes
All unmarked pairs are equivalent. From the final table:
- q₁ ≡ q₂ ≡ q₃ (they are pairwise unmarked).
- q₀ is not equivalent to q₁, q₂, or q₃ (each of those pairs is marked).
- q₄ forms its own class (final state, separated from the rest).
Equivalence classes:
| Class | Member states | Accepting class? |
|---|---|---|
| A | { q₀ } | No |
| B | { q₁, q₂, q₃ } | No |
| C | { q₄ } | Yes |
Number of states in the minimal DFA = 3.
Step 7 — Build the minimal DFA
I rename classes to states S₀, S₁, S₂ for clarity:
- S₀ = {q₀} — start
- S₁ = {q₁, q₂, q₃}
- S₂ = {q₄} — accepting
I compute transitions using any representative from each class (all representatives agree).
From S₀ (use q₀):
- δ(q₀, 0) = q₁ ∈ S₁ → δ′(S₀, 0) = S₁
- δ(q₀, 1) = q₃ ∈ S₁ → δ′(S₀, 1) = S₁
From S₁ (check q₁, q₂, q₃ — they must match):
| Representative | on 0 → | class | on 1 → | class |
|---|---|---|---|---|
| q₁ | q₂ | S₁ | q₄ | S₂ |
| q₂ | q₁ | S₁ | q₄ | S₂ |
| q₃ | q₂ | S₁ | q₄ | S₂ |
So δ′(S₁, 0) = S₁, δ′(S₁, 1) = S₂.
From S₂ (use q₄):
- Both symbols loop in q₄ ∈ S₂ → δ′(S₂, 0) = δ′(S₂, 1) = S₂.
Minimal transition table:
| State | on 0 | on 1 | Accept? |
|---|---|---|---|
| → S₀ | S₁ | S₁ | No |
| S₁ | S₁ | S₂ | No |
| S₂ | S₂ | S₂ | Yes |
Minimal diagram:
Step 8 — Quick sanity check (optional)
The original machine accepts a string iff it eventually enters q₄. From q₀, the first symbol always moves to q₁ or q₃ (both in S₁). From S₁, we reach S₂ exactly when we read a 1. So the language is “every binary string that contains at least one 1”. The minimal DFA above matches that behaviour.