Context-free Languages closed under Reversal

Problem Detail: 

In class this week we've been learning about the CFLs and their closure properties. I've seen proofs for union, intersection and compliment but for reversal my lecturer just said its closed. I wanted to see the proof so I've been searching for the past few days but all I've found is most people just say that to reverse the productions is enough to prove it. Those that do go a little more formal just state there is an easy inductive proof you can give. Can anyone provide me with some more information/hints about the inductive proof? Try as I might I can't come up with it.

Asked By : Sam Hooper

Answered By : Hendrik Jan

Your sources are right, and I am afraid there is only little to add, except formalisms. I denote the reverse (mirror) of string $w$ by $w^R$.

If $G$ is a grammar, let $H$ be its reversed, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$. Then by induction we show that $A\Rightarrow_G^*w$ iff $A\Rightarrow_H^*w^R$. (basis) In zero steps we have $A\Rightarrow_G^0 A$ iff $A\Rightarrow_H^0 A$. (induction) Assuming $A\Rightarrow_G^*w_1Bw_2$ iff $A\Rightarrow_H^*w_2^RBw_1^R$ we can apply any production $B\to u$ in $G$ (and in $H$ in reverse) and obtain $A\Rightarrow_G^*w_1uw_2$ and $A\Rightarrow_H^*w_2^Ru^Rw_1^R$ respectively, where indeed $w_2^Ru^Rw_1^R$ is the reverse of $w_1uw_2$.

This is a very condensed proof, but contains all necessary ingredients. Again, a derivation of the reverse grammar is the reverse of the original one. This is especially clear when looking at the two derivation trees.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6992