DFA Minimization and Myhill-Nerode

Among all the tools in Theory of Computation, the Myhill-Nerode theorem is the sharpest knife. It gives you both a clean proof technique for non-regularity AND the exact size of the minimal DFA for any regular language — all from a single relation on strings.

Definition: For a language L over alphabet Σ, two strings x and y are L-equivalent, written x ≡_L y, if for every string z ∈ Σ*, xz ∈ L if and only if yz ∈ L. In other words, no suffix z can "tell them apart".

Definition: The index of L is the number of equivalence classes of ≡_L.

The intuition — strings that "look the same" to L

Imagine you are designing a DFA for L. After reading some prefix x, the only thing that matters for the future is what continuations z can take the machine to an accepting state. If two prefixes x and y agree on every possible suffix — meaning xz ∈ L ⟺ yz ∈ L for all z — then your DFA can sit in the same state after reading either prefix. Why? Because the state of a DFA is supposed to capture exactly what is needed about the past to decide the future.

So ≡_L is doing the work of "merging" prefixes that the language genuinely cannot distinguish. Conversely, if some suffix z accepts xz but rejects yz, then x and y MUST end up in different states, because one will need to accept and the other reject if z follows.

The theorem itself

Myhill-Nerode Theorem. L is regular if and only if ≡_L has finite index. Moreover, the index of ≡_L equals the number of states in the unique minimal DFA for L.

This is two facts wrapped together:

1. Regularity test: L is regular ⟺ finitely many equivalence classes.
2. Exact lower bound: If you can exhibit n pairwise distinguishable strings, the minimal DFA needs at least n states. If exactly n classes exist, the minimum is exactly n.

Why it matters: This is the only technique that gives you the EXACT minimal DFA size for arbitrary regular languages. The Pumping Lemma can only refute regularity (one direction) and tells you nothing about state counts. Myhill-Nerode is both proof and constructive bound.

Using it to prove non-regularity

To prove L is not regular, exhibit an infinite family of strings {x_1, x_2, x_3, ...} that are pairwise distinguishable. For each pair x_i, x_j with i ≠ j, you must produce a suffix z that separates them: either x_i z ∈ L while x_j z ∉ L, or vice versa.

Classic example: L = { aⁿbⁿ : n ≥ 0 }.
Take the family {ε, a, aa, aaa, ..., aⁿ, ...}. For any two distinct prefixes aⁱ and aʲ with i ≠ j, choose the suffix z = bⁱ. Then aⁱ · bⁱ = aⁱbⁱ ∈ L, but aʲ · bⁱ ∉ L because j ≠ i. Hence aⁱ ≢_L aʲ for every pair. Infinitely many classes ⟹ L is not regular.

Compare this with the Pumping Lemma proof of the same fact — Myhill-Nerode is usually cleaner because you do not have to wrestle with arbitrary decompositions; you just pick distinguishing suffixes.

Using it to compute minimal DFA size

To find the minimal DFA size for a known regular L, enumerate all equivalence classes of ≡_L. For example, take L = { w ∈ {a,b}* : w ends in ab }. Track the relevant history about the last two characters:

• Class 1: strings that do NOT end in a and do NOT end in ab. After such a prefix, you need both an a then a b.
• Class 2: strings ending in a (but not yet ab). One more b finishes.
• Class 3: strings ending in ab. Already accepting; if a comes next move to class 2, if b comes move to class 1.

Three classes ⟹ minimal DFA has exactly 3 states. You can draw the DFA directly: each class is a state; the start state is the class of ε; the accepting states are the classes containing strings in L.

How it connects to DFA minimization

The state-merging algorithms you learned (table-filling / partition refinement) are really computing ≡_L on the reachable states of a given DFA. Two states p and q can be merged if and only if for every input z, δ*(p, z) and δ*(q, z) agree on acceptance. That is precisely the DFA-state version of ≡_L. So the theorem and the algorithm are two faces of the same idea: the minimum DFA is the quotient of any DFA by this indistinguishability relation.

Real-world example: Lexical analysers (lex / flex) used by compilers convert regular expressions into DFAs. Why minimum DFAs? Because at compile time you may have thousands of token patterns, and each redundant state is memory and a branch in the table. The compilers literally implement a Myhill-Nerode-style minimisation pass.

Common misconception: "≡_L is a relation on states." It is not — it is a relation on strings (prefixes). The state-level cousin (sometimes written ≡_D) lives on the DFA's state set. Mixing the two leads to wrong proofs in GATE answers.

Common misconception 2: "If I exhibit k pairwise distinguishable strings, the language is not regular." Wrong — it only proves the minimal DFA needs at least k states. For non-regularity you need an INFINITE distinguishable family.

Question: Prove that L = { 0ⁿ1ⁿ : n ≥ 1 } is not regular using Myhill-Nerode.
Solution:
Step 1: Consider the infinite family {0¹, 0², 0³, ..., 0ⁱ, ...}.
Step 2: For i ≠ j, take z = 1ⁱ. Then 0ⁱ · 1ⁱ = 0ⁱ1ⁱ ∈ L, but 0ʲ · 1ⁱ ∉ L since j ≠ i.
Step 3: Every pair from the family is distinguishable, so ≡_L has infinitely many classes.
Conclusion: ≡_L has infinite index, so by Myhill-Nerode, L is not regular.

DFA minimization sounds intimidating but reduces to one core idea: states that behave identically from this point onward might as well be the same state. The table-filling algorithm — also called the partition refinement method — turns this idea into a mechanical procedure that almost always shows up on the GATE Computer Science paper, either as a one-mark "count the minimum states" question or as a two-mark trace.

Definition: A DFA (Deterministic Finite Automaton) is minimal when no smaller DFA accepts the same language. The minimal DFA is unique up to isomorphism — every correct minimization procedure must arrive at the same number of states.

Definition: Two states p and q are equivalent if, for every input string w, δ*(p, w) is accepting exactly when δ*(q, w) is accepting. Equivalent states can be merged.

The four-step recipe

The table-filling algorithm is essentially a marking game on a triangular table of state pairs. You progressively mark pairs that you can prove are distinguishable until no new marks appear. Whatever is still unmarked is equivalent and gets merged.

Step 1 — Remove unreachable states. Start from the start state, do a BFS or DFS through δ, and discard any state that is not reachable. This must be the very first step. If you skip it, your final count will be wrong and you may even merge an unreachable state with a useful one. GATE examiners love this trap — they hand you a DFA with a stray unreachable trap state to see if you remember.

Step 2 — Initialise the table. For every unordered pair (p, q) of distinct states, look at whether exactly one of the two is a final state. If yes, mark that pair: they are clearly distinguishable, because the empty string ε already distinguishes them (one accepts, the other does not). If both are final or both are non-final, leave the pair unmarked for now.

Step 3 — Repeat the refinement. Scan every still-unmarked pair (p, q). For each input symbol a in the alphabet Σ, compute δ(p, a) and δ(q, a). If the pair (δ(p, a), δ(q, a)) is already marked, then (p, q) is also distinguishable — the string a followed by whatever distinguishes the successors will distinguish p and q. Mark (p, q). Repeat the whole scan until a full pass adds no new marks. This fixed-point condition is when the algorithm halts.

Step 4 — Merge. Every pair that is still unmarked when the algorithm stops is equivalent. Pool equivalent states into single classes. The number of classes is the number of states in the minimal DFA. Build the transition function on classes using any representative member.

Why the procedure works

The marking propagates an idea backwards in time. Step 2 marks pairs distinguished by the empty string (length 0). Each refinement pass extends the marking to pairs distinguished by strings of one more character: if (δ(p, a), δ(q, a)) is distinguished by some string x of length k, then (p, q) is distinguished by the string ax of length k + 1. Because there are only finitely many pairs, the process must terminate — at most about n² rounds for n states. What remains unmarked are pairs that no string can distinguish, exactly the definition of equivalent states.

This idea is the constructive face of the Myhill-Nerode theorem, which proves that the minimum number of DFA states equals the number of equivalence classes of the language under the relation "two strings are equivalent if they extend the same way".

Hopcroft's optimisation

The naive table-filling runs in O(n² · |Σ|) per pass, with up to O(n²) passes. Hopcroft's algorithm is a smarter partition-refinement variant that uses worklists and the "process the smaller half" trick to drop the running time to O(n log n · |Σ|), where n is the number of states and |Σ| is the size of the alphabet. Hopcroft's bound is what makes DFA minimization practical in compiler-grade lexical analyzers like flex.

Why it matters

Minimisation is not academic. Every compiler converts regular expressions for tokens into NFAs, then to DFAs, and then minimises the DFA before generating code. A bigger DFA means slower scanning and a larger compiler binary. Network packet matchers, antivirus signature scanners, and the regex engines of grep and Java's java.util.regex all minimise their DFAs for speed. On GATE, you are expected to apply the recipe by hand on small DFAs (4 to 8 states), so practice the table format on paper.

Worked example

Question: Minimise the following DFA with states {A, B, C, D, E}, alphabet {0, 1}, start state A, final states {C, E}, and transitions:
δ(A, 0) = B, δ(A, 1) = C
δ(B, 0) = A, δ(B, 1) = D
δ(C, 0) = E, δ(C, 1) = F-style... assume δ(C, 0) = E, δ(C, 1) = C
δ(D, 0) = E, δ(D, 1) = C
δ(E, 0) = E, δ(E, 1) = C

Solution:
Step 1: Check reachability from A. A → {B, C}; B → {A, D}; C → {E, C}; D → {E, C}; E → {E, C}. All five states are reachable.
Step 2: Initial marking — pairs (final, non-final) get marked. Finals are {C, E}, non-finals {A, B, D}. Mark (A,C), (A,E), (B,C), (B,E), (D,C), (D,E). Leave (A,B), (A,D), (B,D), (C,E) unmarked.
Step 3: Refinement pass on the unmarked pairs.

• (A, B): on 0, (B, A) unmarked; on 1, (C, D) marked. So mark (A, B).
• (A, D): on 0, (B, E) marked. Mark (A, D).
• (B, D): on 0, (A, E) marked. Mark (B, D).
• (C, E): on 0, (E, E) same state, ignore; on 1, (C, C) same state, ignore. No mark; still unmarked.
  Next pass: nothing new.
  Step 4: The only unmarked pair is (C, E). Merge C and E into one class, say [CE]. Classes: {A}, {B}, {D}, {CE}.
  Conclusion: Minimal DFA has 4 states, down from 5.

Common misconception

The most punishing mistake is skipping Step 1 — removing unreachable states. The marking phase will still terminate, but you may merge an unreachable junk state with a useful one and finish with the wrong count. Always pencil in "reachable: yes/no" beside every state before you start the table.

A second misconception is treating "both final" or "both non-final" pairs as equivalent. They are only possibly equivalent — you have to wait for the refinement passes to confirm. A pair can pass the initial check and still be distinguished later by some longer string.

A third trap: the minimal DFA being unique up to isomorphism. Some students worry that two different orderings of the algorithm give different DFAs. They cannot. The class structure is canonical — only the state names differ.

Consider strings a^0, a^1, a^2, … For any i ≠ j, take suffix z = b^i. Then a^i b^i ∈ L but a^j b^i ∉ L, so a^i and a^j are distinguishable. Thus there are infinitely many ≡_L classes ⟹ by Myhill-Nerode L = {a^n b^n} is NOT regular — no finite DFA exists. The same suffix-distinguishing trick proves {ww}, {a^n b^n c^n}, and {palindromes} non-regular. Memory aid: pick an infinite family of prefixes, find one suffix per pair that separates them. Contrast with the pumping lemma, which only gives a necessary (not sufficient) condition.

Cover the answer, recall, then check. 12 cards on minimization and Myhill–Nerode.

Q1. State the Myhill–Nerode theorem.
A1. L is regular iff the relation x ≡_L y (∀z: xz∈L ⇔ yz∈L) has finitely many equivalence classes; that number equals the states of the minimal DFA.

Q2. Define the Myhill–Nerode equivalence ≡_L.
A2. x ≡_L y iff for every suffix z, xz∈L exactly when yz∈L (x and y have the same set of accepting continuations).

Q3. What is the index of L and what does it equal?
A3. The number of equivalence classes of ≡_L; it equals the number of states in the unique minimal DFA for L.

Q4. How do you prove a language is not regular using Myhill–Nerode?
A4. Exhibit infinitely many strings pairwise distinguishable (each pair separated by some suffix z) — infinite index ⇒ not regular.

Q5. When are two DFA states p and q equivalent (mergeable)?
A5. When for every string w, δ̂(p,w)∈F ⇔ δ̂(q,w)∈F — they accept the same set of suffixes.

Q6. Name the standard table/partition-refinement minimization algorithm.
A6. The table-filling (Moore) algorithm: mark pairs where one is final and one is not, then propagate marks; unmarked pairs merge. O(n²) per round.

Q7. Runtime of Hopcroft's minimization algorithm?
A7. O(n·|Σ|·log n) — the asymptotically fastest DFA minimization.

Q8. First step before minimizing a DFA?
A8. Remove unreachable states (they cannot affect L but can distort merging).

Q9. Is the minimal DFA unique?
A9. Yes — unique up to renaming of states (canonical form of the language).

Q10. For L = { w ∈ {0,1}* : k-th symbol from the end is 1 }, minimal DFA states?
A10. 2^k — Myhill–Nerode gives 2^k distinguishable classes (the last k symbols).

Q11. How many Myhill–Nerode classes does { a^n b^n : n ≥ 0 } have?
A11. Infinitely many — a^i and a^j (i≠j) are distinguished by suffix b^i — hence not regular.

Q12. After merging equivalent states, what happens to accepting status?
A12. A merged state is accepting iff its members were accepting (equivalent states never mix final and non-final).

Two finite automata can accept exactly the same language yet have different numbers of states. DFA minimization finds the unique smallest DFA for a language, and the Myhill–Nerode theorem explains why that minimum exists and how many states it must have.

Core concept: states that behave identically on every future input are redundant and can be merged. The Myhill–Nerode theorem says the minimum number of states equals the number of distinguishable classes of strings — and this minimal DFA is unique up to renaming.

How it works

Beginner — the idea of equivalent states

Two states p and q are equivalent if, for every string w, reading w from p accepts exactly when reading w from q accepts. Equivalent states are indistinguishable, so merging them changes nothing. Minimization = merge all equivalent states.

Intermediate — the table-filling (partition) algorithm

1. Remove unreachable states.
2. Mark every pair (accepting, non-accepting) as distinguishable.
3. Repeat: mark a pair (p, q) distinguishable if for some input symbol a, (δ(p,a), δ(q,a)) is already marked.
4. Unmarked pairs at the end are equivalent — merge them.
   This runs in polynomial time (Hopcroft's algorithm does it in O(n log n)).

Advanced — the Myhill–Nerode theorem

Define strings x, y as equivalent (x ≡_L y) if for every suffix z, xz ∈ L ⟺ yz ∈ L. This relation partitions all strings into equivalence classes.

• A language L is regular iff ≡_L has a finite number of classes.
• The number of classes equals the number of states in the minimal DFA.
• That minimal DFA is unique. This also gives a way to prove non-regularity: exhibit infinitely many pairwise-distinguishable strings.

Worked example

How does Myhill–Nerode show that L = { aⁿbⁿ | n ≥ 0 } is not regular?

• Consider the strings a⁰, a¹, a², a³, … For any i ≠ j, the suffix z = bⁱ distinguishes them: aⁱbⁱ ∈ L but aʲbⁱ ∉ L.
• So a⁰, a¹, a², … are all in different equivalence classes → infinitely many classes.
• By Myhill–Nerode, no finite DFA exists → L is not regular.

Exam relevance

GATE asks for the number of states in the minimal DFA, application of the table-filling method, using Myhill–Nerode to count classes or prove non-regularity, and the fact that the minimal DFA is unique. It is a heavily tested Theory-of-Computation topic.

Tricks & shortcuts

• Always remove unreachable states first, then merge equivalent ones.
• Number of Myhill–Nerode classes = states in the minimal DFA.
• To prove non-regularity: find infinitely many strings, pairwise distinguished by some suffix.