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$ 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

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$ How are you sure that L is context-free? $\endgroup$ – Joe Oct 26 '19 at 16:37
  • $\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

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.