Regular Language – Myhill Nerode Theorem: Is Language Regular?

equivalence-relationsregular-language

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 🙂

Best Answer

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.

Related Question