# Prove that the class of CFG languages that are closed under reversal is undecidable

## 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.

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)$$.
• 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})$. – David Chen Dec 26 '19 at 9:35
• In your case, $L(G) = \{\#a\}$, which isn’t closed under reversal. – Yuval Filmus Dec 26 '19 at 9:37
• Just to make sure, so you mean $$L(G) = (\#L(G_1)) \cup (L(G_2)^r\#)$$ – David Chen Dec 26 '19 at 9:41