Show that the language L = {ww^Rw: w in {a,b}*} is not a context-free language.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Hello. Check our reference questions for techniques to solve this question. cs.stackexchange.com/questions/265/… $\endgroup$– Ran G.Commented Nov 9, 2014 at 22:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Let's call the first $w$ of a word $ww^Rw \in L$ "part A", the middle part $w^R$ "part B" and the remaining $w$ "part C".
Use the word $$z=\underbrace{0^n10^n}_{A} \underbrace{0^n10^n}_{B} \underbrace{0^n10^n}_{C} \in L$$ with $|z|\geq n$.
The pumping lemma states that if $L$ is context-free, $z$ can be written as $z=uvwxy$ and
(1) $|vwx| \leq n$,
(2) $|vx| \geq 1$,
(3) $\forall i \in \mathbb{N}: uv^iwx^iy \in L$.
However, when setting $i=0$, the resulting word $z'=uwy$ cannot be element of $L$ as one of the following situations occurs:
- Exactly one "1" has been deleted from $z$, possibly among other "0" symbols (another "1" cannot have been deleted due to $|vwx|\leq n$). Then two parts of $z'$ contain a "1", but the third one, A, B or C doesn't, therefore, $z' \notin L$.
- "0"s from at most two parts of $z$ have been deleted, but not from the third part (again due to $|vwx|\leq n$). So, in this case too it hold that $z' \notin L$.
Therefore we have to give up the assumption that $L$ is a context-free language.
$\begingroup$
$\endgroup$
Let $1 \leq p$ and let $p\leq|w|$ if we take the $ww^{R}w \in L$ then by the pumping leemma we are going to have that : $\forall n\ uv^{n}wx^{n}y \in L $ and $|vwx|\leq p$ and |vx|>0 so we can see that either $v,x$ are letters of $w^{R},w$ or one is in $w$ and the other in $w^{R}$ . if we take $n=0$ we get to contraction. So it isnt context-free.