HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theundecidablelanguagesareclosedcfgproveunderthatreversal

Problem

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

Context

StackExchange Computer Science Q#118891, answer score: 4

Revisions (0)

No revisions yet.