Myhill–Nerode theorem

1. What are the two methods for minimizing a DFA?
   Stuck? Peek at 1.3.2 Partition and table-filling methods

   • Partition: remove unreachable; P₀ = {F, Q−F}; split by signatures w.r.t. previous partition; stop when stable.
   • Table filling: n(n−1)/2 cells; mark (F, non-F); propagate “successor pair marked ⇒ mark”; unmarked = equivalent.
   • Count by distinct futures: list situations with different accepted continuations, include dead / satisfied states.
   • Exactly k of a symbol: k + 2 states; at least k: k + 1; at most k: k + 2.

   Read lesson 1.3.2

2. Minimal DFA for strings with exactly 3 a’s over {a,b}?
   Stuck? Peek at 1.3.2 Partition and table-filling methods

   • Partition: remove unreachable; P₀ = {F, Q−F}; split by signatures w.r.t. previous partition; stop when stable.
   • Table filling: n(n−1)/2 cells; mark (F, non-F); propagate “successor pair marked ⇒ mark”; unmarked = equivalent.
   • Count by distinct futures: list situations with different accepted continuations, include dead / satisfied states.
   • Exactly k of a symbol: k + 2 states; at least k: k + 1; at most k: k + 2.

   Read lesson 1.3.2

3. What is the index of an equivalence relation?
   Stuck? Peek at 0.2.2 Functions, relations and equivalence classes

   • Relation ⊆ A × B. Function: every input exactly one output. Partial function: some inputs have none.
   • #functions A→B = |B|^|A|. #one-to-one (|A| ≤ |B|) = |B|·(|B|−1)···. #relations on n-set = 2^(n²).
   • Equivalence = reflexive + symmetric + transitive. Classes partition the set; number of classes = index.
   • Finer relation (refinement) ⇒ more classes; every fine class sits inside a coarse class.

   Read lesson 0.2.2

Minimization needed a DFA to start with. But GATE often gives only a description: “the language of all strings where …”. And sometimes the honest answer is “no DFA exists at all”. Is there a way to count states — or prove none suffice — directly from the language? Yes: group strings (not states) by their futures. This is the Myhill–Nerode theorem, and it explains why minimization works.

Language L = { aⁿbⁿ | n ≥ 0 }. Do the strings a and aa have the same “future”? That is, is there a continuation z such that az ∈ L but aaz ∉ L?

Prediction check

Yes: z = b. ab ∈ L but aab ∉ L. In fact aⁱ and aʲ (i ≠ j) are always separated by z = bⁱ. So infinitely many strings have pairwise different futures — and that will mean no DFA can exist for L.

The Myhill–Nerode relation

“x and y need the same continuations.” It is an equivalence relation. It is also right-invariant: if x ≡_L y then xa ≡_L ya for every symbol a.

The theorem

Why: in any DFA for L, strings ending in the same state have the same future, so #states ≥ #classes. And the classes themselves form a DFA: state [x], move [x] ─a→ [xa], start [ε], accept the classes inside L. That DFA has exactly #classes states, so it is minimal.

Two uses

• Count minimal states: find a list of strings that are pairwise distinguishable (each pair separated by some z) and show every string falls into one of their classes. The list size = minimal state count.
• Prove a language is not regular: find infinitely many strings, pairwise distinguishable. Then the index is infinite, so no DFA exists. This is our first rigorous proof of non-regularity.

Example: ends with ab

Classes: [ε] (strings ending in neither a nor ab, including ε, “b”, “abb”), [a] (ending in a), [ab] (ending in ab). Pairwise: ε vs a: z = b (ab ∈ L, b ∉ L). ε vs ab: z = ε. a vs ab: z = ε. Three classes ⇒ minimal DFA has 3 states.

Putting it together

• x ≡_L y when every continuation treats them alike.
• Regular ⇔ finitely many classes; the count is the minimal DFA size (dead class included).
• Infinitely many pairwise-distinguishable strings prove a language is not regular.

L = { w ∈ {a,b}* : w ends with ab }

 class      sample strings          continuations z that lead into L
 [ε]        ε, b, bb, abb, aab b    z ends with ab  (e.g. "ab")
 [a]        a, ba, aba, aa          z = b, or z ends with ab
 [ab]       ab, bab, aab            z = ε, or z ends with ab
 three different "future sets" → 3 states → same as 1.2.3's DFA

L = { aⁿbⁿ } :    ε   a   aa   aaa   aaaa ...
 separating z:     ε   b   bb   bbb   bbbb   (aⁱbⁱ ∈ L, aʲbⁱ ∉ L for j ≠ i)
 infinitely many classes  →  NOT regular

Myhill–Nerode ties the whole of Phase 1 together: states are just names for “futures”; minimization finds them from a machine; the theorem finds them from the language; and infinitely many futures means no finite machine. One small topic remains in Phase 1: finite machines that produce output instead of just yes/no.

1. MCQ

   x ≡_L y means:

   1. x and y have the same length
   2. for all z, xz ∈ L ⇔ yz ∈ L
   3. x and y are both in L
   4. for all z, zx ∈ L ⇔ zy ∈ L
2. NAT

   Index of ≡_L for L = strings over {a,b} containing bb?

   Write your answer before opening the key.

3. MSQ

   Which follow from the Myhill–Nerode theorem?

   1. L regular ⇒ ≡_L has finite index
   2. Finite index ⇒ L regular
   3. #classes = #states of the minimal DFA
   4. Every infinite language has infinite index
4. MCQ

   To prove L non-regular with Myhill–Nerode you need:

   1. one string not in L
   2. infinitely many pairwise distinguishable strings
   3. a DFA for the complement
   4. two strings with the same future

• Myhill–Nerode relation ≡_L
• right-invariant
• finite index
• Myhill–Nerode theorem
• non-regular language

1. Myhill–Nerode theorem?
   Reveal answer

   L is regular iff ≡_L has finitely many classes; the number of classes = states of the minimal DFA.
2. How do you prove aⁿbⁿ is not regular with Myhill–Nerode?
   Reveal answer

   The strings aⁱ are pairwise distinguishable (z = bⁱ), so there are infinitely many classes.
3. Can an infinite language have finite index?
   Reveal answer

   Yes — e.g. Σ* has index 1.