9
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ "I've seen proofs for union, intersection and complement"?! As I recall, CFLs have not been closed under intersection nor complement for decades. $\endgroup$
    – John L.
    Apr 30, 2021 at 1:34

3 Answers 3

15
$\begingroup$

Your sources are right, and I am afraid there is only little to add, except formalism. 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.

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

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 26, 2017 at 15:05
  • $\begingroup$ Wow!!! more easier to understand. thank you very much. $\endgroup$
    – milad
    Jun 26, 2021 at 16:36
4
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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