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.
-
$\begingroup$ I upvoted because I cannot find a duplicate here, so maybe this can be one of the frequently asked questions here. $\endgroup$– xskxzrApr 30, 2018 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$– roctothorpeApr 30, 2018 at 5:21
-
1$\begingroup$ @xskxzr On the other hand, googling "CFL" leads to a wikipedia page that gives an explanation. $\endgroup$– AcccumulationApr 30, 2018 at 16:31
2 Answers
Let us assume $2$ CFLs $L_1$ and $L_2$ and their corresponding grammars be $S_1$ and $S_2$ respectively. It is very straightforward to see that the union of the two, represented by the new grammar as
$$S \to S_1 \mid S_2$$
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 $L_1$ and $L_2$ respectively be:
$$L_1 = \{ a^nb^nc^m \mid n, m \ge 0 \}$$
$$L_2 = \{ a^mb^nc^n \mid n, m \ge 0 \}.$$
It is not hard to see that $L_1 \cap L_2$ is
$$L = \{ a^nb^nc^n \mid n, m \ge 0 \},$$
which is not CFL (No PDA cannot accept that language).
Hope this explains.
-
1$\begingroup$ For proof that your intersection L is not CFL, wikipedia (en.wikipedia.org/wiki/…) says that you can use the pumping lemma, although I did not dive deep enough to understand this. $\endgroup$– bogecMar 12, 2021 at 18:41
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.
-
$\begingroup$ Is this also why a CFL∩Regular lang is CFL because a DFA needs no stack for themselves? $\endgroup$– rsonxJan 12, 2021 at 17:11
-
1$\begingroup$ Right, that’s why this closure property does hold. $\endgroup$ Jan 12, 2021 at 17:15