Closure properties of context-free languages and intersection with regular languages

Question

The intersection of a context-free language and a regular language is always context-free but context-free languages are not closed under set intersection. Could anyone explain why both theorems are true if all regular languages are context-free (the opposite is not always true)?

Answer 1

To prove that context-free languages are not closed under intersection, we provide a counterexample.

Consider L = {a^i b^j c^k | i = j} and R = {a^i b^j c^k | i = k}. The intersection of these two sets is S = {a^i b^j c^k | i = j = k}, i.e., strings of the form a^n b^n c^n. It can be shown using the pumping lemma for context free languages that this language is not context free. Context free grammars for the other two are easy:

  L is given by
  S := AC
  A := aAb | lambda
  C := cC | lambda

  R is given by
  S := aSc | B | lambda
  B := bB | lambda

To address your question more specifically, the reason both theorems can be true is that the regular languages are a proper subset of the context free languages; for the context free languages to be closed under set intersection, the intersection of any arbitrary context free languages must also be context free (it's not; see above). However, it is at the same time true that it happens to be the case that the intersection of any regular language and any context free language is also context free (there's no reason the Cartesian product machine can't be made using a FA and a PDA; only one machine needs a stack, after all - not the case when trying the Cartesian product machine with two PDAs, since two stacks are needed in some cases, and two stack PDAs are equivalent to Turing machines).