Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
