[Solved]: Proving a Language is Irregular using Myhill-Nerode

Problem Detail: 

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.

Asked By : Craig Spurr

Answered By : J.-E. Pin

You can observe that $L$ is accepted by this infinite DFA $\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}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14701