[Solved]: Why does this pumping lemma application "prove" that 0*1* is not regular?

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