The language is $S = (a^nb^m | n \geq m)$.

I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that there are infinitely many equivalence classes. So in this case if I choose $S = a^n$ is simply not working since $n \geq m$ and thus $a^mb^m \in S$. So I think I have to pick $S = b^m$ and $a^nb^m \in S$ but $a^nb^n \notin S$. Does my assumption accurate or any suggestion?


1 Answer 1


The classes are defined over words of the alphabet such that two words $x, y$ are equivalent if for any word $z$ we have $xz \in L$ if and only if $yz \in L$.

Consider for each $n\in \mathbb{N}$ the class $C_n$ defined as $$C_n = \{x \in S : \#_b(x) \geq 1 \text{ and } \#_a(x) -\#_b(x) = n\}.$$

Note that for each word in this class we can append exactly the strings $b^i$ where $i \leq n$. So for two different values $n_1$ and $n_2$ where $n_1 < n_2$ the word $b^{n_2}$ is a valid suffix to words in $C_{n_2}$ but not in $C_{n_1}$. Hence we have infinitely many such classes. Words ending with the letter $a$ accept additionally more $a$s and hence do not even belong to these classes and we have even more classes. Since we have infinitely many classes, the language is not regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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