4
$\begingroup$

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?

$\endgroup$
  • $\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 Oct 5 '14 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 Oct 6 '14 at 16:00
6
$\begingroup$

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.

$\endgroup$
  • 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 Oct 5 '14 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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