6
$\begingroup$

Note

The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below.

Problem Description

Given a word $w$, define $w^{r}$ to be its reversal.

Let $L=\{ G \vert G \text{ is a } CFG \text{ and for every } w \in L(G), w^{r} \in L(G) \}$

Prove that $L$ is undecidable.

My Attempt

I am aware that I should reduce a known-to-be-undecidable language to L, but by looking at the four undecidable languages here (Equivalence, Disjointness, Containment, Universality), I still failed to determine which language I can use. Please guide me a direction, thank you.

Improve this question
$\endgroup$
4
$\begingroup$

Let $G_1,G_2$ be two context-free grammars. We can construct a context-free grammar $G$ such that $$ L(G) = \#L(G_1) \cup L(G_2)^r\#, $$ where $\#$ is a new symbol. The language $L(G)$ is closed under reverse iff $L(G_1) = L(G_2)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thank you for the response. But what if $L(G_{1})=\{a\}$ and $L(G_{2})=\emptyset$? In this case, $L(G)=\{\#a\#\}$ is closed under reversal, but $L(G_{1}) \neq L(G_{2})$. $\endgroup$ – David Chen Dec 26 '19 at 9:35
  • $\begingroup$ In your case, $L(G) = \{\#a\}$, which isn’t closed under reversal. $\endgroup$ – Yuval Filmus Dec 26 '19 at 9:37
  • $\begingroup$ Just to make sure, so you mean $$ L(G) = (\#L(G_1)) \cup (L(G_2)^r\#) $$ $\endgroup$ – David Chen Dec 26 '19 at 9:41
  • 1
    $\begingroup$ I think when there might be ambiguity, it doesn't hurt to make things clear. $\endgroup$ – David Chen Dec 26 '19 at 10:14
  • 1
    $\begingroup$ Is there ambiguity in the expression $ax+yb$? $\endgroup$ – Yuval Filmus Dec 26 '19 at 10:15

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.