Prove that $\{ww^R\#ww^R\}$ is not context free

990 Views Asked by At

I need to prove that $L = \{ww^R\#ww^R \; | \; w \text{ is in } \{a,b\}^*\}$ is not context free.
I have tried using the pumping lemma for this.
For $w=a^pb^pb^pa^p\#a^pb^pb^pa^p$.
I have two cases for $w=uvxyw$:

(1) $v$ and $y$ are both before the $\#$ or both after the $\#$. Obviously $w^2$ is not in $L$, contradiction.

(2) $v$ is before $\#$ and $y$ is after $\#$. I separated the word $w$ to four parts:

$w = AB\#CD$
Therefore $A=B^R$ and $C=D^R$.
If $v$ is homogeneous or $y$ is homogeneous, we can show that $A$ does not equal $B^R$ or $C$ does not equal $D^R$. But here is where I got stuck - if $v$ and $y$ are heterogeneous, how do I get the contradiction?
Thanks in advance.

1

There are 1 best solutions below

0
On BEST ANSWER

Remember that $|vxy|\le p$. If $vxy$ includes the $\#$, obviously the $\#$ must be in $x$, so $v=a^k$ and $y=a^\ell$ for some $k$ and $\ell$ such that $1\le k+\ell\le p-1$. But then clearly $uxw\notin L$.