An example of context free language and pumping lemma.

Question

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?

Answer 1

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$.