Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let $L = \{\space ww \space | \space w \in \{0,1\}^*$} (need to prove that $L$ is not CFL)
Assuming $L$ is CFL we can use the PL and split $s=uvxyz$ and we choose $s = 0^p1^p0^p1^p$ where $p$ is the pumping length.
Using the 3$^{rd}$ rule, namely $|vxy| \le p$, can I say that $vxy$ can consist only of $0's$ and either pumping up(e.g. $uv^2xy^2z)$ or down ($uxz$) will throw us out of $L$ ?
Remember that the PL is stated for any partition $s=uvxyz$, so it is not enough to show that for one specific partition pumping $v$ and $y$ will exclude the resulting string from $L$. While it is true that $xyz$ can consist only of 0′s, it could also be the case that $xyz$ is of the form $0^i1^j$ for some $i, j < p$, for instance. You must show that pumping excludes the resulting string from $L$ in this (and all possible other) cases as well.
Here is a decomposition $s = uvxyz$ such that $|vxy| \leq p$ but $xyz$ doesn't consist only of zeroes: $$ u = 0^p \\ v = 1^p \\ x = \epsilon \\ y = \epsilon \\ z = 0^p 1^p $$
