1
$\begingroup$

The title pretty much explains the question, but still: Is the language $$L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$$ context-free?

I think it isn't and would motivate that suspicion by the following reasoning: if we consider the two languages: $$L' = \{xwx^{rev} \mid\ x,w\in\{0, 1\}^*\} \text{ which is context-free}$$ $$L'' = \{w^3\mid w\in\{0, 1\}^*\} \text{ which can be shown to be non-context-free by the pumping lemma}$$ Now if $L''$ were context-free, then we could obtain the initial language $L$ by "enclosing" $L''$ with $L'$, i.e. $L'$ is sort of a sub-language of $L''$. We can do that by extending the eventual CFG of $L'$ (let's assume its starting non-terminal is $S'$) with the following productions: $$S'' \to 0S''0 \,\mid\, 1S''1 \,\mid\, S'$$ and thus obtaining a grammar for $L$ whose starting symbol is $S''$.

The only problem is that I'm not sure how to formalize that idea and if it's even right and enough to prove that $L$ isn't context-free. Any ideas are welcome! Many thanks in advance!

$\endgroup$
1
1
$\begingroup$

Use closure properties to formalize your intuitions.

Context-free languages are closed under intersection with regular languages. In this case you can go from $L$ to (a language close to) $L''$ by observing that the string $xx^{rev}$ has the same first and last letter.

$\endgroup$
4
  • $\begingroup$ I also tried finding such an approach and your answer validates that idea, but I can't see it... Could you hint more? How could we go from L to L'' by intersecting with a regular language... Only thing I can think of is interesecting with $1\sum^*0\cup0\sum^*1$, i.e. the language of all words with different first and last character, but that would also restrict the possibilities of $w^3$ in the middle... $\endgroup$ – D. Petrov Jun 19 at 8:26
  • 1
    $\begingroup$ Ooooh, now I see, so the actual "close to L'' " language would be $w^3$ but where w starts and ends with different characters, which we can again show by the pumping lemma is not context-free, right? ^^ $\endgroup$ – D. Petrov Jun 19 at 8:28
  • $\begingroup$ @D.Petrov Yes, that is what I think will work. $\endgroup$ – Hendrik Jan Jun 19 at 13:07
  • $\begingroup$ Confirmed, I also checked it out, everything seems super duper fine! Thank you a lot! $\endgroup$ – D. Petrov Jun 20 at 11:50

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.