Prove that the class of CFG languages that are closed under reversal is undecidable
-
28-09-2020 - |
Question
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.
Solution
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)$.