Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)

share|cite|improve this question
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
up vote 5 down vote accepted

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.

share|cite|improve this answer
perfect explanation, thank you :) – xwhyz Nov 27 '12 at 15:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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