1
$\begingroup$

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

  • 0
    @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.2012-10-07

1 Answers 1

2

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

  • 0
    @Belgi: I picked [Greibach](http://en.wikipedia.org/wiki/Greibach_normal_form) 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.2012-10-07