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?

  • $\begingroup$ 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. $\endgroup$
    – user2864740
    Commented Oct 5, 2014 at 1:19
  • 1
    $\begingroup$ Our reference questions (and many examples via pumping-lemma) explain in detail how to apply the Pumping lemma. $\endgroup$
    – Raphael
    Commented Oct 6, 2014 at 16:00

1 Answer 1


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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – Justo
    Commented Oct 5, 2014 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.