# Proving the context-free languages are closed under reverse

In the book I am reading it is stated that if $L$ is a context-free language then so is $L^{R}$(where $L^{R}:=\{w^{R}:w\in L\}$, example: $(ab)^{R}=ba$).

This claim has been proven in the text using Chomsky normal form and hence it $\epsilon\in L$ the proof is invalid.

Can I make a reduction from the general case (i.e. any context-free language) to this case ?

My only thought is to add the rule $S\to\epsilon$ to the grammar and prove the claim in a similar manner

-
Why not simply replace any rule $X\to ABC$ with $X\to CBA$ etc.? – Hagen von Eitzen Oct 7 '12 at 11:21
@HagenvonEitzen - The proof did something similir, $X\to BC$ was replaced by $X\to CB$ . I guess the auther did not want to mess around with general (long) expressions so he tooked greibach normal form. by the way, I tried proving this in that way and I had a difficult time with the long and general expressions for the rules. – Belgi Oct 7 '12 at 11:24

## 1 Answer

Let $L$ be any context-free language. If $\epsilon\notin L$, you already know that $L^R$ is context-free. If $\epsilon\in L$, then $L\setminus\{\epsilon\}$ is context-free and so $L^R\setminus\{\epsilon\}=\left(L\setminus\{\epsilon\}\right)^R$ is context-free. Let $G$ be a grammar for $L^R\setminus\{\epsilon\}$ in Greibach normal form, and just add the production $S\to\epsilon$. Since $S$ does not appear on the righthand side of any production in $G$, this simply adds $\epsilon$ to the language, and you get $L^R$.

-
I'm sorry, I made a mistake in the question. the book used Chomsky normal form. as far as I understand in this form we allow for something like $A\to SB$, right ? [I believe that Greibach also allows for something like $A\to aS$] – Belgi Oct 7 '12 at 11:34
But the conclusion still remains as far as I can see, since we added $S\to \epsilon$ we don't add any other terminal words – Belgi Oct 7 '12 at 11:35
@Belgi: I picked Greibach because it doesn’t allow $S$ on the righthand side; that makes it clear that adding $S\to\epsilon$ just adds $\epsilon$ to the language. – Brian M. Scott Oct 7 '12 at 11:37