3
$\begingroup$

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?

$\endgroup$

migrated from stackoverflow.com Nov 16 '15 at 13:52

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ Reread the pumping lemma carefully. When writing a string as $uvwxy$ you can't pick a particular decomposition; it has to apply to all possible decompositions. $\endgroup$ – Rick Decker Nov 17 '15 at 1:54
  • $\begingroup$ But whenever someone tries to prove a language is not context free, they try all the possible combinations of decompositions before coming to a conclusion that the language is not context free. May be they're just trying to explain but I think they're trying to find at least one decomposition that satisfies. $\endgroup$ – user41965 Nov 17 '15 at 5:38
5
$\begingroup$

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