# 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, 2019 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, 2019 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. Oct 26, 2019 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'$$.

• How are you sure that L is context-free?
– Joe
Oct 26, 2019 at 16:37
• It's concatenation of two context-free languages $\{a^n b^n\}$ and $\{c^m d d c^k b^k a^m\}$. Oct 26, 2019 at 17:15
• S->LR, L->aLb | eps, R->cRa | ddK, K->cKb | eps. Oct 26, 2019 at 17:54
• do we actually need the dd in middle? I think the proof still works if we remove the dd part
– Joe
Oct 26, 2019 at 18:09
• 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. Oct 27, 2019 at 8:40