Using MyHill Nerode theorem to prove a language is non-regular

Question

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?

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.