Two different automata can recognize the same language. One may have three states, the other thirty. Among all equivalent DFAs there is one with the minimum number of states, and it is unique up to renaming the states. This fact, together with the Myhill-Nerode theorem that explains it, is one of the most elegant results in automata theory, and it has immediate practical consequences: smaller automata use less memory and are easy to compare.
Indistinguishable states
Given a DFA, two states p and q are indistinguishable if for every string w the automaton, starting from p and reading w, accepts exactly when, starting from q and reading w, it accepts. In other words, no experiment on the future input can separate them.
If instead some string w leads one of them to an accepting state and the other not, the two states are distinguishable, and w is a witness string.
Indistinguishable states are redundant: they can be merged into one state without changing the language. Minimizing means precisely:
- removing states unreachable from the start state;
- merging all indistinguishable states with one another.
The partition refinement algorithm
The most common method for finding indistinguishable states works by successive refinement.
- Start with two blocks: accepting and non-accepting states. They are certainly distinguished by the empty string.
- Examine each block: two states in the same block stay together only if, for every symbol, their transitions lead to states in the same block.
- If a block contains states that go to different blocks, split it.
- Repeat until no block splits any more.
The final blocks are the states of the minimal DFA. Transitions are inherited from any representative of the block, because by construction all its members behave the same way.
A worked example
Consider a DFA over {a, b} with states 1, 2, 3, 4, 5, where 1 is the start state and 4 and 5 are accepting. The transitions are:
| State | a | b |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 4 | 3 |
| 3 | 2 | 3 |
| 4 | 5 | 3 |
| 5 | 5 | 3 |
Initial partition: {1, 2, 3} and {4, 5}.
Examine {1, 2, 3}. On a, state 1 goes to 2 (first block), state 2 goes to 4 (second block), state 3 goes to 2 (first block). State 2 splits off: we get {1, 3}, {2}, {4, 5}.
Examine {1, 3}: on a both go to 2, on b both go to 3. They stay together. Examine {4, 5}: on a both go to 5, on b both go to 3. They stay together.
No block splits further. The minimal DFA has three states: A = {1, 3}, B = {2}, C = {4, 5}. It recognizes strings ending in "aa", and it is clear that three states are enough: "no trailing a", "one trailing a", "at least two trailing a's".
The Myhill-Nerode theorem
The theorem moves the discussion from automata to languages. Given a language L, two strings x and y are equivalent with respect to L if for every string z: xz ∈ L if and only if yz ∈ L. It is an equivalence relation, and it counts how many "different situations" the language forces us to tell apart.
The theorem states:
L is regular if and only if this relation has finitely many equivalence classes. In that case the number of classes is exactly the number of states of the minimal DFA for L.
The link with the algorithm is direct: each state of the minimal DFA corresponds to a class of strings the language cannot tell apart.
Using Myhill-Nerode for non-regularity
The theorem gives a technique that is often cleaner than the pumping lemma. It is enough to find an infinite set of pairwise distinguishable strings.
For L = {aⁿbⁿ : n ≥ 0}, consider the strings a, aa, aaa, … Given aⁱ and aʲ with i ≠ j, the string z = bⁱ distinguishes them: aⁱbⁱ is in L, aʲbⁱ is not. There are infinitely many classes, so L is not regular. No alternating quantifiers and no decompositions to analyse.
Why minimization matters in practice
- Equivalence: to know whether two DFAs recognize the same language, minimize both and check that they are identical up to renaming states.
- Efficiency: automatically generated lexical analyzers often go through a minimization phase, because the subset construction can produce many redundant states.
- Understanding: the minimal DFA reveals the essential structure of the language, that is how much information about the past really has to be kept.
In short
- Two states are indistinguishable if no future string separates them; merging them does not change the language.
- The algorithm starts from accepting and non-accepting states and splits blocks until transitions are consistent.
- The minimal DFA is unique up to renaming states.
- Myhill-Nerode: L is regular if and only if the classes of indistinguishable strings are finite.
- Finding infinitely many pairwise distinguishable strings is a clean way to prove non-regularity.
