patternModerate
Context-free Languages closed under Reversal
Viewed 0 times
freelanguagesclosedunderreversalcontext
Problem
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.
Solution
Your sources are right, and I am afraid there is only little to add, except formalism. Indeed it is enough to reverse all productions to reverse the language. I denote the reverse (mirror) of string $w$ by $w^R$.
If $G$ is a grammar, let $H$ be its reverse, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$.
Then by induction we show that original grammar $G$ generates a string iff the reverse grammar $H$ generates the reverse of the string. Formally $A\Rightarrow_G^w$ iff $A\Rightarrow_H^w^R$.
$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: they are just reversed (or mirrored).
If $G$ is a grammar, let $H$ be its reverse, so for production $A\to w$ in $G$ we have $A\to w^R$ in $H$.
Then by induction we show that original grammar $G$ generates a string iff the reverse grammar $H$ generates the reverse of the string. Formally $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: they are just reversed (or mirrored).
Context
StackExchange Computer Science Q#6992, answer score: 17
Revisions (0)
No revisions yet.