Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

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.