0
$\begingroup$

I try to figure out why cannot I prove, using contraposition of pumping lemma, that the language $L = \{(0^n)(1^n) | n \gt 1 \}$ is not CFL. If I take a constant $n$ and $z = (0^n)(1^n)$ where $z = uvwxy$, where $vwx = 0^n$, where $v=0^k$, $x=0^j$, where k+j = n, then when I pump it I will get different number of zeroes and ones and so it proves the language L is not CFL, but indeed the language L is CFL. What do I wrong?

$\endgroup$
1
$\begingroup$

If $n$ is the pumping length, and $z=0^n1^n$, the pumping lemma says that there is some decomposition $z=uvwxy$ such that $|vwx|\le n$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for each $k\ge 0$. You don’t get to choose the decomposition: all you know is that there is one. And in fact there is: take $u=0^{p-1}$, $v=0$, $w=\epsilon$ (or $\lambda$, if that’s your symbol for the empty string), $x=1$, and $y=1^{p-1}$. Then

$$uv^kwx^ky=0^{p-1+k}1^{p-1+k}$$

is indeed in $L$ for each $k$.

$\endgroup$

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.