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
    Why not simply replace any rule $X\to ABC$ with $X\to CBA$ etc.?2012-10-07
  • 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
    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$]2012-10-07
  • 0
    But the conclusion still remains as far as I can see, since we added $S\to \epsilon$ we don't add any other terminal words2012-10-07
  • 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