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?
$\begingroup$
$\endgroup$
-
$\begingroup$ 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$. $\endgroup$ – rici Oct 26 '19 at 5:48
-
$\begingroup$ @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? $\endgroup$ – Joe Oct 26 '19 at 5:53
-
$\begingroup$ 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. $\endgroup$ – gnasher729 Oct 26 '19 at 14:48
$\begingroup$
$\endgroup$
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'$.
-
-
$\begingroup$ It's concatenation of two context-free languages $\{a^n b^n\}$ and $\{c^m d d c^k b^k a^m\}$. $\endgroup$ – sdcvvc Oct 26 '19 at 17:15
-
$\begingroup$ S->LR, L->aLb | eps, R->cRa | ddK, K->cKb | eps. $\endgroup$ – gnasher729 Oct 26 '19 at 17:54
-
$\begingroup$ do we actually need the dd in middle? I think the proof still works if we remove the dd part $\endgroup$ – Joe Oct 26 '19 at 18:09
-
$\begingroup$ 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. $\endgroup$ – sdcvvc Oct 27 '19 at 8:40
