# Why does this pumping lemma application "prove" that 0*1* is not regular?

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?

• The problem arises from y = 0^(p-1)1 which leads to the claim "expanding" with p-1 and thus claiming a contradiction. Start with y = 0^i1, such that for all i >= 0, xy^iz in L. Now apply the pumping lemma.
– user2864740
Oct 5, 2014 at 1:19
• Our reference questions (and many examples via pumping-lemma) explain in detail how to apply the Pumping lemma.
– Raphael
Oct 6, 2014 at 16:00