4
$\begingroup$

I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection. I was wondering if there was a simple proof or example demonstrating that CFLs are not closed under intersection.

$\endgroup$
  • $\begingroup$ I upvoted because I cannot find a duplicate here, so maybe this can be one of the frequently asked questions here. $\endgroup$ – xskxzr Apr 30 '18 at 3:58
  • 6
    $\begingroup$ To prove that CFLs are not closed under intersection, see if you can find two CFLs whose intersection is not context free (a canonical example of a language which is not context free is $a^nb^nc^n$). $\endgroup$ – roctothorpe Apr 30 '18 at 5:21
  • 1
    $\begingroup$ @xskxzr On the other hand, googling "CFL" leads to a wikipedia page that gives an explanation. $\endgroup$ – Acccumulation Apr 30 '18 at 16:31
13
$\begingroup$

Let us assume 2 CFLs L1 and L2 and their corresponding grammars be S1 and S2 respectively. It is very straightforward to see that the union of the two, represented by the new grammar as:

S -> S1 | S2

is also a CFG, as the rule of being context-free is still not violated.Context-free grammar

But to prove that they are not closed under intersection, I'll provide an example.

Let L1 and L2 respectively be:

L1 = { anbncm | n, m >= 0 }

L2 = { ambncn | n, m >= 0 }

It is not hard to see that:
L, which is L1 ∩ L2:

L = { anbncn | n, m >= 0 }
is not CFL ( a PDA cannot be created ).

Hope this explains.

$\endgroup$
5
$\begingroup$

Complementing the counterexample in the other answer, let me also what mentions when you try to construct a machine accepting the intersection of two context-free languages. Recall that a context-free language can be accepted by a pushdown automaton. Hence we can try to simulate two pushdown automata operating simultaneously. Since each PDA requires a stack, altogether we need to use two stacks. However, using two stacks we can simulate a Turing machine (exercise), so in general two stacks cannot be implemented in a single stack. Now it might be the case that in this particular case this reduction in the number of stacks is possible, but this hope is shattered by the example given by Akash Mahapatra.

Similar considerations apply for the quotient of two context-free languages $L_1/L_2 = \{ x \in \Sigma^* : \exists y \in L_2 \, xy \in L_1 \}$. In this case one can show that every r.e. language can be represented as the quotient of two context-free languages. Hence this particular way of using two stacks is as general as possible. The same doesn’t hold for intersection, since the intersection of any (finite) number of context-free languages is always recursive, indeed belongs to the much smaller class LOGCFL.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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