Course contentsShow
← Computer Science
Lesson 1809 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Myhill-Nerode Theorem: Characterizing Regularity

A language is regular if and only if it has finitely many equivalence classes.

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.