11
$\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$
3
  • $\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, 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$ Apr 30, 2018 at 5:21
  • 1
    $\begingroup$ @xskxzr On the other hand, googling "CFL" leads to a wikipedia page that gives an explanation. $\endgroup$ Apr 30, 2018 at 16:31

2 Answers 2

23
$\begingroup$

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.

$\endgroup$
1
  • 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$
    – bogec
    Mar 12, 2021 at 18:41
9
$\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$
2
  • $\begingroup$ Is this also why a CFL∩Regular lang is CFL because a DFA needs no stack for themselves? $\endgroup$
    – rsonx
    Jan 12, 2021 at 17:11
  • 1
    $\begingroup$ Right, that’s why this closure property does hold. $\endgroup$ Jan 12, 2021 at 17:15

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.