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

$\endgroup$
  • $\begingroup$ Why not simply replace any rule $X\to ABC$ with $X\to CBA$ etc.? $\endgroup$ – Hagen von Eitzen Oct 7 '12 at 11:21
  • $\begingroup$ @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. $\endgroup$ – Belgi Oct 7 '12 at 11:24
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$] $\endgroup$ – Belgi Oct 7 '12 at 11:34
  • $\begingroup$ 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 $\endgroup$ – Belgi Oct 7 '12 at 11:35
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 7 '12 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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