CFL not closed under intersection

Claim: the class of context free languages (CFLs) is not closed under intersection. (It is closed under union, concatenation and star, but not under intersection or complement.)

Proof by counterexample

Take two languages:

• L1 = { aⁿbⁿcᵐ : n, m ≥ 0 }
• L2 = { aᵐbⁿcⁿ : n, m ≥ 0 }

Both are context free, since each has a CFG:

• L1: S → AC, A → aAb | ε, C → cC | ε (equal a's and b's, then any number of c's)
• L2: S → AB, A → aA | ε, B → bBc | ε (any number of a's, then equal b's and c's)

Their intersection. A string is in L1 ∩ L2 only if (number of a = number of b) and (number of b = number of c). Because the form is abc*, this gives

L1 ∩ L2 = { aⁿbⁿcⁿ : n ≥ 0 }

This language is not context free (pumping lemma for CFLs). Suppose it is, with pumping length p, and let s = aᵖbᵖcᵖ = uvxyz with |vxy| ≤ p, |vy| ≥ 1, and uvⁱxyⁱz ∈ L for all i ≥ 0.

• Since |vxy| ≤ p, the part vxy cannot contain all three letters a, b and c; it touches at most two kinds of letters.
• So pumping (take i = 2) increases the count of at most two letters, and the third letter keeps count p.
• The three counts are then no longer equal, so uv²xy²z ∉ L. This is a contradiction.

Hence aⁿbⁿcⁿ is not a CFL.

Conclusion

L1 and L2 are CFLs but L1 ∩ L2 is not a CFL. Therefore CFLs are not closed under intersection.

Consequence: CFLs are also not closed under complement. If they were, then L1 ∩ L2 = (L1ᶜ ∪ L2ᶜ)ᶜ would be a CFL, because CFLs are closed under union. This contradicts the result above.