1
$\begingroup$

I feel that choice should work great for proving non - regularity of the mentioned language.

If $L=\{ww|w \in \{0,1\}^*\}$ and we choose $s=0^p0^p$, meaning s is atleast as long as 'p'. Then we can decompose s as follows $x=empty \ string,\ y = 0^p, \ z = 0^p$

Then we can pump 'y' according to the rules of pumping lemma we will end up with 2p zeroes which is more than the number of zeroes in 'z'

And we have reached a contradiction because this new string is not in the language and according to the pumping lemma it should have, so why does michael sipser say that it's a bad candidate for proving non regularity in this langauge?

$\endgroup$
3
  • $\begingroup$ $0 = 0$ (shocking, I know) $\endgroup$
    – Nathaniel
    Jan 13, 2023 at 16:44
  • $\begingroup$ Should that be $L = \{ww|w\in\{0,1\}^*\}$ (i.e. are the last } and * switched)? $\endgroup$ Jan 13, 2023 at 17:06
  • $\begingroup$ @DanielWagner oh my bad, i'll correct it now $\endgroup$ Jan 13, 2023 at 17:07

2 Answers 2

3
$\begingroup$

Your proof doesn't work. First of all you can't choose your favorite decomposition of $s$: the pumping lemma just ensures that such a decomposition exists so your argument needs to work for all possible decompositions.

Nevertheless, even with your decomposition it is false that the "pumped" word does not belong to the language. To see why suppose that the pumping length $p$ happens to be $2$. Then $s=0^20^2=0000$, $x=\varepsilon$, $y=0^2=00$, and $z=0^2=00$.

Now let's pump $y=00$ to, e.g., $y^2 = 0000$. The resulting word is $xy^2z = \varepsilon\, 0000\, 0^2 = 000000$. As you can see $000000 \in L$ (by choosing $w=000$).

You run in the same problem regardless of how many times (possibly $0$) you pump $y$.

$\endgroup$
16
  • $\begingroup$ but consider this scenario, what if pumping length $p$ happens to be 3 then the resultant string after pumping once would be $000000000$ which is 9 zeros, there's no way that this string would be in language $\endgroup$ Jan 13, 2023 at 16:45
  • 1
    $\begingroup$ Yes, but you don't get to choose the pumping length. You only know that there is some value of $p$ such that the pumping lemma holds. $\endgroup$
    – Steven
    Jan 13, 2023 at 16:50
  • $\begingroup$ basically are you saying that ~ one needs to carefully select a particular string such that our argument must work for all values of 'p'? $\endgroup$ Jan 13, 2023 at 16:55
  • 1
    $\begingroup$ Yes, you need to choose a particular string $s$ (that can be chosen as a function of $p$) such that the argument works regardless of $p$ and for all possible decompositions $s=xyz$ with $|xy| \le p$ and $|p|\ge 1$. For example, if you choose $0^p10^p1$ you can be ensured that $xy$, and in particular $y$, contain only $0$s that appear before the first $1$. Then pumping $y$ yields a word that is not in the language. $\endgroup$
    – Steven
    Jan 13, 2023 at 17:17
  • $\begingroup$ Ah gotchu, you answered my question. I additional doubt: you said "argument needs to work for all possible decompositions", but every video and tutorial mentions that if we are using pumping lemma to prove non regularity through contradiction then we just need to prove for 1 such decomposition, so why do you say that we need to prove for all decompositions? $\endgroup$ Jan 13, 2023 at 17:22
1
$\begingroup$

First of all, you don't get to pick the decomposition. So one decomposition you'd need to handle is $x = \varepsilon$, $y = 00$, $z = 0^{2p-2}$. Now if we pump $y$ for $i$ times, we get $xy^iz = 0^{2p + 2i - 2}$, which belongs to $L$.

$\endgroup$

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.