Show that the language L = {ww^Rw: w in {a,b}*} is not a context-free language.


2 Answers 2


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:

  1. 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$.
  2. "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.


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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.