Problem Detail: Here is a proof that $0^*1^*$ is not regular, even though it is regular. I’m having a hard time figuring out what is wrong with the proof. Assume $0^*1^*$ is regular. Let $p$ be the pumping length as defined by the pumping lemma. Let $s = 0^{p-1}11$, then $|s| ge p$ and $s in 0^*1^*$. According to the pumping lemma, we can split $s$ into three parts $s = xyz$ such that $|y|>0$, $|xy| le p$, and $xy^iz in 0^*1^*$ for $i ge 0$. Let $x = varepsilon$, $y = 0^{p-1}1$, and $z = 1$. Clearly, $|xy| le p$ and $|y|>0$. However, $xy^2z = 0^{p-1}10^{p-1}11$ is not a member of $0^*1^*$. This is a contradiction to the pumping lemma, therefore $0^*1^*$ is not regular. We know $0^*1^*$ is regular, building a NFA for it is easy. What is wrong with this proof?
Asked By : Justo
Answered By : user124577
The idea is that there is some partition that fulfills the condition of the pumping lemma – you do not have the choice of the x, y, and z – you have to show that there exists no x, y, and z that satisfies the conditions.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30660
