# Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?

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!

## 1 Answer

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.

• 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... Commented Jun 19, 2021 at 8:26
• 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? ^^ Commented Jun 19, 2021 at 8:28
• @D.Petrov Yes, that is what I think will work. Commented Jun 19, 2021 at 13:07
• Confirmed, I also checked it out, everything seems super duper fine! Thank you a lot! Commented Jun 20, 2021 at 11:50