# Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt:

For the language $$L=\{\omega \in \{a,b\}^* \colon \omega \text{ contains at most 1 } 'a' \}$$ The classes are $$M_1=\{\omega \in b^*\}$$ $$M_2=\{\omega \in b^*ab^*\}$$ $$M_3=\{\omega \in b^*ab^*a(a\cup b)^*\}$$

Now, the way I understand it I need to prove 2 things:

1. For each $u,v\in M_i (1\le i\le 3)$ and for each $x\in \Sigma^*$ $$ux\in L \iff vx\in L$$
2. There exists $u\in M_i,v\in M_j(1\le i \neq j \le 3)$ and $x\in \Sigma^*$ such that $$ux\in L,vx\notin L$$

Am I right about how I described the classes, and about how to prove it?

• Actually, you need to prove a 3rd thing: that your equivalence classes form a partition of $\Sigma ^{*}$ . Beside that, your EC are Ok, indeed you need 3 classes in this case – Roi Divon Jun 29 '14 at 11:44
• What research and reading have you done? Have you studied the explanation of Myhill-Nerode in standard textbooks? Have you looked at our reference questions on this topic? e.g., cs.stackexchange.com/q/1331/755 Finally, "please check my answer" questions are not a good fit for this site. Only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here. – D.W. Jun 29 '14 at 13:35

Your classes are correct, and one can also describe them in words: words containing no $a$, words containing a single $a$, words containing at least two $a$s. When described in this fashion, it is clear that the every word belongs to exactly one class.