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.