# Is Half - Palindrome subset of a context-free language context-free?

Suppose we have $$L$$ being a context-free language. Let $$L'=\{x \in \Sigma^* | xx^R \in L \}$$, is $$L'$$ context-free as well? I know that if $$L$$ is regular then $$L'$$ is regular as well by constructing a DFA. Is it possible to create a PDA here as well? I am stuck on this or even if there is a counter example?

• The language of all palindromes $\{xx^R\mid x\in \Sigma^*\}$ is certainly not regular, even though it is the palindrome subset of $\Sigma^*$ which clearly is regular. Perhaps you were thinking about the fact that if $L$ is regular, so is $L^R$. – rici Oct 26 '19 at 5:48
• @rici, sorry i do not quite get your point. If $L$ is regular then $L'$ is regular, you can see my previous question. I have asked about this before. But now, my question is what if $L$ is context free, is $L'$ is going to be context free as well? – Joe Oct 26 '19 at 5:53
• The case for regular grammar is here: cs.stackexchange.com/questions/115214/… Note that this is the language of "left halves of palindromes in language L" not "palindromes in language L" which is usually not regular. The construction is tricky; I expect the one for CFG to be much much more tricky or impossible, and wouldn't be surprised if there is a counter example. – gnasher729 Oct 26 '19 at 14:48

Let $$L=\{a^n b^n c^m d d c^k b^k a^m\}$$, then $$L$$ is context-free. I claim $$L'=\{a^n b^n c^n d\}$$ which is not context-free.
Suppose $$x\in L'$$. Then $$x$$ must be of the form $$a^i b^j c^k d$$. Then $$x x^R = a^i b^j c^k d d c^k b^j a^i \in L$$, which means that $$i=j=k$$. Conversely, it's clear that $$\{a^n b^n c^n d\} \subseteq L'$$.
• It's concatenation of two context-free languages $\{a^n b^n\}$ and $\{c^m d d c^k b^k a^m\}$. – sdcvvc Oct 26 '19 at 17:15
• Indeed. I put $dd$ so that I didn't have to think about $c^{m+k}$ being decomposed in a different way than $c^m c^k$, but that should work too. – sdcvvc Oct 27 '19 at 8:40