Myhill–Nerode theorem

Remarks

If a DFA $A$ accepts $L$, then two words that lead $A$ to the same state are equivalent, so $\sim_L$ has at most as many classes as $A$ has states. Conversely, if there are finitely many classes, the classes themselves are the states of a DFA. On the letter $a$, the class of $x$ goes to the class of $xa$. The class of $\varepsilon$ is initial, and the classes inside $L$ are accepting. This DFA is well defined because $x \sim_L y$ implies $xa \sim_L ya$. Example: for $L = \set{a^n b^n : n \ge 0}$, the words $a^i$ for $i \ge 0$ lie in pairwise different classes, since $a^i b^i \in L$ but $a^j b^i \notin L$ for $j \ne i$; so $L$ is not regular. The class of $x$ corresponds to the Brzozowski derivative $x^{-1} L = \set{z : xz \in L}$, since $x \sim_L y$ means $x^{-1} L = y^{-1} L$.

Going deeper

For a student

Unlike the pumping lemma, this theorem characterizes regular languages, so it can prove both regularity and non-regularity. It also gives the theoretical basis of DFA minimization: minimizing a DFA means merging states that lead to equivalent words. The two-sided version of the same idea, the syntactic congruence, leads to the syntactic monoid of a language.