I'm trying to prove that the language: \begin{equation*} L = \{ w \in \{ 0, 1 \}^* : w \text{ contains more 0's than 1's} \} \end{equation*} is irregular using the Myhill-Nerode theorem. I've been through all the basic examples in the book, and thought I understood them, but I'm having trouble with this one.

So far, I've been thinking about letting $ x_i = 1^i 0^i $ and $x_j = 1^{j+1} 0^{j-1}$, then if I let $ w_{ij} = 0$, only $x_iw_{ij} \in L$. That seems to be sufficient, but it seems weak compared to some of the other examples.

Am I on the right track here? I would really appreciate any hints/suggestions.

up vote 1 down vote accepted

You can observe that $L$ is accepted by this infinite DFA $\mathcal{A}$$\mathcal{A}$. This might help you to separate the words $0^i$, as suggested by Yuval Filmus.

By the way, this will also prove that $\mathcal{A}$ is the minimal DFA of $L$.

Update. I apologize, but the link to the automaton $\mathcal{A}$ seems to be broken at the moment. Just in case, a brief description: set of states $\mathbf{N}$, initial state $0$, final states $\mathbf{N} \setminus \{0\}$, transitions $n \xrightarrow{0} n + 1$ and $n+1 \xrightarrow{1} n$ for all $n \in \mathbf{N}$.

You need to come up with an infinite number of pairwise inequivalent strings. Try $x_i = 0^i$ for all $i \geq 0$.

You need to show that there are infinitely many equivalence classes. For that you should find an infinite number of strings, such that no pair of them is equivalent. Right now you have an infinite number of inequivalent pairs, which is a much weaker statement.

Complete a chain of strings. Say, first you had $1^i0^i$ and $1^{j+1}0^{j-1}$. See what could go next to keep all strings inequivalent. See what pattern emerges. There is plenty of solutions.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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