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