# 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?

## migrated from stackoverflow.comOct 6 '14 at 14:43

This question came from our site for professional and enthusiast programmers.

• 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 '14 at 1:19
• Our reference questions (and many examples via pumping-lemma) explain in detail how to apply the Pumping lemma. – Raphael Oct 6 '14 at 16:00

## 1 Answer

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.

• Ah I see, we are allowed to choose a string s such that |s|>=p but we can't choose a specific partition s=xyz to arrive at a contradiction, that would only be a single case. We have to contradict with all cases. Thanks. – Justo Oct 5 '14 at 1:44