1.4DFA minimisation and Myhill–Nerode
The idea
Minimisation merges states that can never be told apart. Two states are equivalent if every string behaves the same from both.
Think of it like this: Two employees who always give the same answer to every question are interchangeable; keep one.
Why it exists
The minimal DFA is unique, and its number of states is the true measure of how much a language has to remember.
How it works
- Remove unreachable states first.
- Round 0: split into final and non-final.
- Split any group whose members go to different groups on some symbol.
- Repeat until nothing changes. The groups are the states of the minimal DFA.
Worked example: The 6-state "ends in b" DFA
Round 0 gives {1,2,5} and {3,4,6}. Both groups already behave uniformly, so the answer is 2 states (last symbol was b or not).
Now play with it
- →Choose the redundant DFA and step through the rounds.
- →Then choose the 8-state DFA and see that nothing merges.
| State | on a | on b | Final? |
|---|---|---|---|
| 1 | 2 | 3 | no |
| 2 | 5 | 4 | no |
| 3 | 2 | 6 | yes |
| 4 | 5 | 3 | yes |
| 5 | 2 | 4 | no |
| 6 | 5 | 6 | yes |
This 6-state DFA accepts "strings ending in b".
- Round 0: split final vs non-final: {1,2,5} {3,4,6}
- No further split: 2 equivalence classes = 2 states in the minimal DFA
Check yourself
After minimisation, how many states does the 6-state "ends in b" DFA have?
Exam notes (the dense version)
Two states are equivalent if no string leads one to a final state and the other to a non-final state. Delete unreachable states, then merge equivalent ones (partition refinement). The minimal DFA is unique, and its state count equals the number of Myhill–Nerode classes.
Previous year questions: Finite Automata (DFA, NFA, ε-NFA) (6)
PYQs are grouped by topic, so this is the full set for Finite Automata (DFA, NFA, ε-NFA); try the ones that match this subtopic. Open all 6 on the topic page.