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.

$\endgroup$

1 Answer 1

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

$\endgroup$
2
  • $\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, 2019 at 9:35
  • $\begingroup$ In your case, $L(G) = \{\#a\}$, which isn’t closed under reversal. $\endgroup$ Dec 26, 2019 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.