World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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?

#### Answered By : Yuval Filmus

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.