Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 2 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.