Prove that $L^r$ is context free without alphabet

Question

I'm stuck with this problem:

Given $L$ a CFL on the alphabet $\Sigma$. Prove that $L^r=\{x^r|x\in L\}$, where for each $a\in\Sigma$ and $y\in\Sigma^*$, $$\epsilon^r=\epsilon,$$ $$(ay)^r=y^ra,$$ is context free or not.

Since I don't have the alphabet I cannot think of a grammar that generates this language, so I decided to prove that it's not context free by applying the pumping lemma for CFL. So I started with the hypothesis that $L^r$ is context free, thus if $x\in L^r$ that $x^r\in L$.

Then I tried to find different possible strings that once pumped didn't belong anymore to $L^r$, but I'm not able to find such string.

Is this a bad aproach? Where am I wrong?

Answer 1

Informally, by construction $L^r$ consists of the strings in $L$ reversed. Since $L$ is context-free, it has a Grammar in Chomsky normal form. All production rules in this grammar will fall in one of three classes:

1. $A \rightarrow BC$
2. $A \rightarrow a$
3. $S \rightarrow ε$

Thus by reversing the order of non-terminals in the RHS of all rules of category 1., a new grammar can be derived that produces $L^r$.

This new grammar is also in Chomsky normal form, thus $L^r$ is context-free.