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.

Was it helpful?

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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top