1
$\begingroup$

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?

$\endgroup$
3
  • $\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, 2019 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, 2019 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, 2019 at 14:48

1 Answer 1

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ How are you sure that L is context-free? $\endgroup$
    – Joe
    Oct 26, 2019 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, 2019 at 17:15
  • $\begingroup$ S->LR, L->aLb | eps, R->cRa | ddK, K->cKb | eps. $\endgroup$
    – gnasher729
    Oct 26, 2019 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, 2019 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, 2019 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.