gotchaMinor
Why does this pumping lemma application "prove" that 0*1* is not regular?
Viewed 0 times
thiswhyapplicationregularprovepumpingthatlemmadoesnot
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#30660, answer score: 6
Revisions (0)
No revisions yet.