2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

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