# Myhill Nerode - is language regular or not?

I'm trying to understand how to find equivalence classes of a language to prove its regularity. I think that if I'm able to FULLY understand one example then I will get this topic right.

Let's say I have a language

$L=\{a^{m} b^{n} :1\le m \le n\}$ over alphabet $\Sigma=\{a,b\}$

My approach is following:

$K_{\epsilon} = \{\epsilon\}$ - class containing empty word. If we concatenate any word $z$ from the language, then word from this class will be in the language.

$K_{A} = \{a^{i}\} \land i \gt 1$ - class containing strings of a's. If we concatenate word $z = b^{k} \land k>i$ than all strings from this class will be in the language. There is infinitely many such classes.

$K_{AB} = \{a^{i}b^{j}\} \land i>1 \land j<i$ - class containing strings of a's and b's. If we concatenate word $z=b^{i-j+1}$ then words from this class will be in the language. There is infinitely many such classes.

What I don't understand is why we am I looking for such word $z$ and why different length of word constitutes new class. Also why words from classes do not have to be indluded in language ?

I know that I still have to show that those classes are not related but firstly I want to understand whats above.

Please give me intuition rather than solution - I want to understand it more than just do it :)

-
Are you asking for help in proving that your $L$ is regular? If so, you're in trouble, because it isn't. – Peter Taylor Nov 27 '12 at 13:35
That I see, because of infinitely many equivalence classes. What I want to know is if I'm doing it right and I want to understand what I'm actually doing – xwhyz Nov 27 '12 at 13:53

The Myhill-Nerode relation $\equiv_L$ of $L$ is a relation on $\Sigma^*$ (not on $L$, so representatives do not have to be members of $L$, as you observed). It is for words $x,y \in \Sigma^*$ defined by $$x \equiv_L y \iff \forall z \in \Sigma^*: xz \in L \Leftrightarrow yz \in L$$ That is, two words are equivalent, iff however we add some $z$ to both of them, we either have to words in $L$ or two words off $L$.
One usually looks at $\equiv_L$ to see a language is or is not regular. To see a language is not regular, one has to give infinitely many words $x_i \in \Sigma^*$ with $$x_i \not\equiv_L x_j, \qquad i \ne j$$ That is, why you were given those $z$s, they will be usefull to see your classes listed are indeed different. For example:
$\epsilon \not\equiv_L a$, as with $z = b$ (look at your $K_A$ list), we have $\epsilon z = b \not\in L$, but $az = ab \in L$.
Note moreover that one infinite list suffices, that is if you can show $a^i\not\equiv_L a^j$ for $i \ne j$, you are done in showing that $L$ isn't regular. If you want to find all equivalence classes, there is at least one missing.