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?

  • 2
    $\begingroup$ It might help if you state the equivalence you are referring to. $\endgroup$ – reinierpost Oct 22 '15 at 8:07

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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.