Why are CFLs not closed under intersection?

Question

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.

Answer 1

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.

Answer 2

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.