Myhill Nerode to prove $0^*1^*$ is regular?

595 Views Asked by At

For the language $L=0^*1^*$, I want to use the Myhill-Nerode theorem to prove it is regular.

I'm trying to first list out the subsets of the alphabet but don't understand how I can use them to make my proof:

$A1 = L$

$A2 = \{w\mid \text{w is not in L}\}$

How would I use these to go on with proving the language is regular?

1

There are 1 best solutions below

0
On

You need to chose your subsets so that they are Nerode equivalence classes, where two words $v,w$ are in the same equivalence class iff for all words $z$ we have: $vz\in L \iff wz \in L$.

So first, your $A_2$ is actually a equivalence class. The proof of why that is is really simple. (However, note the complement of $L$ isn't always an equivalence class. Take $L=L((a|b)^*bb(a|b)^*)$ for example)

Second, $A_1=L$ is not an equivalence class. For example it contains $0$ and $1$. Think about how this shows $L$ is not an equivalence class.

To show $L$ is regular, you must simply show that there are finitely many equivalence classes by simply listing all equivalence classes (Hint: there are three).

In case you're struggling to find all equivalence classes it can be helpful to think about how you would construct a DFA and think about what each state means for some word in that state. Often each state of the intuitive DFA approach (especially for such easy languages) corrosponds to an equivalence class.