# Myhill-Nerode Theorem

Tom Henzinger’s notes about the Myhill-Nerode: http://www-cad.eecs.berkeley.edu/~tah/172/7.pdf

A regular language L has finitely many equivalence classes. Since the whole number of equivalence classes is finite, there can be only finitely many equivalence classes which contain strings in L (which correspond to the accepting states in the minimal finite automaton), and finitely many equivalence classes which contain strings not in L (which correspond to the non-accepting states in the minimal finite automaton).

But what for a non-regular language L?

A little thought will give the example \(L = \{ 0^n1^m: m \geq 0, m \leq n \leq 2m, \text{n is even} \}\) It’s easy to prove L is non-regular so there are infinitely many equivalence classes:

- \(L_\alpha = {0^n1^m: m > n \geq 0} \cup \Sigma^* 1 \Sigma^* 0 \Sigma^*\)
- \(L_{00} = {0^{2n}1^n: n \geq 0}\)
- \(L_{01} = {0^{2n}1^{n+1}: n \geq 0}\)
- \(L_{02} = {0^{2n}1^{n+2}: n \geq 0}\)
- …
- \(L_{11} = {0^{2n}1^{n-1}: n \geq 0}\)
- \(L_{12} = {0^{2n}1^{n-2}: n \geq 0}\)
- \(L_{13} = {0^{2n}1^{n-3}: n \geq 0}\)
- …

Among these equivalence classes, \(L_\alpha\) and \(L_{1x}\) are not in L. And \(L_{0x}\) is in L. There are both infinitely many equivalence classes that are in L and not in L.

Furthermore, the notes of Tom give an example of a non-regular language B that has finitely many equivalence classes in B, and infinitely many equivalence classes not in B. And we know \(\overline{B}\) is also non-regular. And \(\overline{B}\) has infinitely many equivalence classes in \(\overline{B}\), and finitely many equivalence classes not in \(\overline{B}\).

Therefore, there should be no restriction w.r.t. infinity about the equivalence classes of a non-regular language.