the Myhill-Nerode theorem
/ Myhill: MY-hill; Nerode: neh-ROH-dee /
The Myhill-Nerode theorem is the exact, two-way answer to 'which languages are regular?', whereas the pumping lemma is only one-way. The idea is to ask, for a fixed language L, how many genuinely DIFFERENT 'situations' a reader can be in after consuming some prefix. If finitely many situations suffice, you can build a DFA with one state per situation; if infinitely many are needed, no finite automaton can keep track, so L is not regular.
Make 'situation' precise. Two strings x and y are indistinguishable with respect to L if for EVERY continuation z, the string xz is in L exactly when yz is in L — they have the same future no matter what comes next. This is an equivalence relation that splits Σ* (all strings) into classes; the number of classes is called the index of L. The theorem states: L is regular IF AND ONLY IF this relation has FINITELY many classes (finite index). Moreover, when L is regular, the number of classes equals the number of states of the MINIMAL DFA — so the theorem simultaneously characterizes regularity and pins down the exact minimal machine.
This gives two powerful, exact tools. To prove L non-regular, exhibit an infinite family of strings that are pairwise distinguishable (each pair separated by some witness z) — infinitely many classes means not regular, and unlike the pumping lemma this NEVER fails when the language really is non-regular. To find the smallest possible DFA, count or construct the equivalence classes; each becomes one state. Named for John Myhill and Anil Nerode.
For a^n b^n, the strings a^0, a^1, a^2, ... are pairwise distinguishable: a^i and a^j (i ≠ j) split via z = b^i, since a^i b^i is in L but a^j b^i is not. Infinitely many classes ⇒ not regular. For 'even number of a's', only TWO classes (even-so-far, odd-so-far) ⇒ regular, minimal DFA has 2 states.
Finite index ⇔ regular; the class count is exactly the minimal DFA's state count.
Myhill-Nerode is necessary AND sufficient — it characterizes regularity exactly, so it never gives a false result, unlike the pumping lemma. The equivalence is on STRINGS (the language's right-congruence), not on the states of any particular machine.