# Context-free Languages closed under Reversal

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.

• "I've seen proofs for union, intersection and complement"?! As I recall, CFLs have not been closed under intersection nor complement for decades. Commented Apr 30, 2021 at 1:34

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

• (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).

• does this hold for deterministic context free language. Commented Jan 23, 2015 at 5:11
• @aksam Deterministic CFL are not closed under reversal. Note determinism for CFL usually is defined with pushdown automata, not grammars. Commented Jan 24, 2015 at 12:47

There is another way to look at this problem.

Consider that the Language $L$ is a CFL. This means that there is a grammar $G=\{N,\sum,P,S\}$ that satisfies the CFL. We can assume that this is in Chomsky Normal Form.

If $\epsilon$ is part of the language, trivially $\epsilon^R$ is also part of the language. Now for every production of the form $P_1 \longrightarrow AB$, replace it with, $P_1 \longrightarrow BA$ and for the productions of the form $P_1 \longrightarrow a$, where $a \in \sum$, leave it the same.

From the parse tree of the derived string, it is easy to see that the language derived will be exactly the reverse of the initial language as the construction mirrors the original parse tree.

• I don't think this is "another way": it's just the same way phrased in a different (and actually, I think, easier to follow) way. The part where you say "it is easy to see" is the part where the induction comes in. Anyway, +1 since this answer is definitely helpful. Commented Apr 26, 2017 at 15:05
• Wow!!! more easier to understand. thank you very much. Commented Jun 26, 2021 at 16:36

First off. CFL's are not closed under intersection or complement (or difference for that matter). They are closed under Union, Concatenation, Kleene star closure, substitution, homomorphism, inverse homomorphism, and reversal. NOTE: The two homomorphism's are usually not covered in an intro Computer Theory course.

To prove reversal, Let L be a CFL, with grammar G=(V,T,P,S). Let LR be the reverse of L, such that the Grammar is GR = (V,T,PR,S). That is, reverse every production.

Ex. P -> AB would become P -> BA

Since GR is a CFG, therefore L(GR) is a CFL.

• Welcome to the site! I'm amazed that nobody noticed before that the question incorrectly claims that CFLs are closed under intersection and complement. Commented May 15, 2017 at 9:04