Myhill-Nerode Theorem: Characterizing Regularity
You'll learn the fundamental connection between finite equivalence classes and regular languages.
The Core Idea
The Myhill-Nerode Theorem gives us a powerful if-and-only-if characterization of regular languages: a language is regular if and only if it has finitely many equivalence classes under the equivalence relation we learned previously.
This is huge! Instead of constructing a DFA or writing a regular expression to prove a language is regular, you can simply count its equivalence classes. And conversely, if you show a language has infinitely many equivalence classes, you've proven it's not regular.
Why This Works
Think of equivalence classes as "behavioral buckets" — strings that future inputs can't tell apart. A DFA works by remembering which bucket you're in as it reads input. Since a DFA has finitely many states, it can only distinguish finitely many buckets.
The forward direction: If a language is regular, some DFA recognizes it. That DFA has finitely many states, which directly correspond to equivalence classes. Therefore, finite equivalence classes.
The reverse direction: If there are finitely many equivalence classes, you can build a DFA where each state represents one class. Transitions follow the natural structure of how strings extend.
Practical Impact
This theorem turns regularity into a counting problem. Want to prove {0ⁿ1ⁿ | n ≥ 0} is non-regular? Show that strings ε, 0, 00, 000, ... are all in different equivalence classes (because they need different numbers of 1's to be accepted). Infinitely many classes → not regular!
Key Takeaway: The Myhill-Nerode Theorem establishes that regularity is equivalent to having finitely many equivalence classes, providing both a tool for proving languages are regular and a systematic way to prove they are not.