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}$.
. 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
