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?

  • 1
    $\begingroup$ 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 $\endgroup$ – Roi Divon Jun 29 '14 at 11:44
  • $\begingroup$ 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. $\endgroup$ – 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.

However, there is no reason to use the Myhill–Nerode criterion to prove that a language is regular. Instead, you can use its vast generalization and give a DFA or NFA for the language. In the other direction, there is no need to describe all classes, only infinitely many; this already shows the language is not regular.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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