[Solved]: Is {ww^r ww^r} a context-free language?

Problem Detail: 

Is the language $L = \{w w^r w w^r \mid w \in \Sigma^*\}$ context-free? ($w^r$ is the reversal of $w$.)

I heard that by using the pumping lemma, we can only prove that a language is not context-free, but can't prove that a language is context-free. I tried the pumping lemma and we can produce the language by repeating $v$ and $x$ by taking first $ww^r$ as $v$ and the second $ww^r$ as $x$ which again belongs to the same language. However I'm not able to build any grammar or build a PDA with one stack. I know that may if someone tries harder than me they may be able to construct it, but I'm thinking this may not be a context-free language. Does anyone have any idea about this language?

Asked By : user41965

Answered By : rici

It's not context free for the same reason that $L' = \{w w \mid w \in \Sigma^*\}$ is not context free, and the proof below is a simple adaption of the standard proof for the language $L'$, using the pumping lemma:

Choose the string $0^p1^p1^p0^p0^p1^p1^p0^p$, (which is $\omega \omega^r \omega \omega^r$ where $\omega = 0^p 1^p$). [Note 1] Now any $vwx$ whose length is no greater than $p$ is either entirely within the first half of the string, entirely within the second half of the string, or entirely within the central span of $0^{2p}$. Repeating $v$ and $x$ 0 times -- that is, changing $vwx$ to $w$ -- must make the first half of the string different from the second half, either because only one of the halves is altered, or because changing the suffix of one half and the prefix of the other half renders the two halves distinct. So the result is not in $L$.

Since for any $p$, we can find a string which cannot be pumped, we can conclude that there is no pumping length $p$ for the language. That contradicts the pumping lemma, which states that every context-free language has a pumping length. So the language is not context-free.

---

You can't "take the first $ww^r$ as $v$" because of the restriction that the length of $vwx$ is no greater than the pumping length $p$. So, whatever $p$ is (if it exists) there is some $ww^r$ which is longer, and for the corresponding string $ww^rww^r$ in $L$, $v$ cannot be $ww^r$.

---

Notes:

1. I could have chosen a shorter string, such as $\omega = 0^m1^n$ where $m>0, n>0, 4mn>=p$. But there are no prizes for parsimony here; the string I chose makes the proof less verbose.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49557