World's most popular travel blog for travel bloggers.

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

, , No Comments
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?

Asked By : user270494

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback