World's most popular travel blog for travel bloggers.

# [Answers] Why do non regular languages have infinitely many equivalence classes?

, ,
Problem Detail:

For example, for the language \$L = \{a^nb^m|n \neq m\}\$, why does it have infinitely many equivalence classes? How do I show/see that?

#### Answered By : Yuval Filmus

There are at least two ways. The first way is to give infinitely many pairwise inequivalent words. In the case of your language, you can take \$\{ a^n : n \geq 0 \}\$, for example (exercise).

The second way is to prove that the language is not regular. The Myhill–Nerode theorem then implies that it has infinitely many equivalence classes. The reason is that for any language, we can construct a DFA (finite or infinite!) for the language whose states are the equivalence classes. If there are finitely many then this is a bona fide DFA, and we get that the language is regular. Conversely, for every regular language, the states of the minimal DFA correspond to the equivalence classes.