---
title: "CFL not closed under intersection"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfl-intersection-not-closed"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfl-intersection-not-closed
site: BCT Engineering
---

# CFL not closed under intersection

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2072 Chaitra
- Video: [Closure Properties of Context-Free Languages](https://www.youtube.com/watch?v=P_F0-kY_kKQ) — Easy Theory
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfl-intersection-not-closed
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Use the concept of closure properties to prove that the intersection of context free languages is not context free.

## Short answer

The languages L1 = {a^n b^n c^m} and L2 = {a^m b^n c^n} are context-free, but their intersection L1 ∩ L2 = {a^n b^n c^n} is not context-free (by the pumping lemma). Hence CFLs are not closed under intersection.

## Answer

**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 a*b*c*, 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. Which pair of CFLs is used to show CFLs are not closed under intersection?
   A. {aⁿbⁿcᵐ} and {aᵐbⁿcⁿ}
   B. {aⁿbⁿ} and {bⁿcⁿ}
   C. {a*} and {b*}
   D. {aⁿbⁿ} and {aⁿ}
   Answer: A. Both are context free but their intersection is {aⁿbⁿcⁿ}. (Key point: Counterexample languages)

2. What is L1 ∩ L2?
   A. {aⁿbⁿ}
   B. {aⁿbⁿcⁿ : n ≥ 0}
   C. a*b*c*
   D. {aⁿbᵐcⁿ}
   Answer: B. #a = #b from L1 and #b = #c from L2 force all three counts to be equal. (Key point: Intersection result)

3. Why is pumping aᵖbᵖcᵖ impossible within CFL rules?
   A. The string is too short
   B. Any v and y touch at most two letters, so the third count stays p and the counts become unequal
   C. The pumping length is 0
   D. a, b and c never occur together
   Answer: B. Since |vxy| ≤ p, one letter is untouched, so pumping breaks equality. (Key point: Why not CFL)

4. Why does non-closure under intersection imply non-closure under complement?
   A. Complement is the same as intersection
   B. Because L1 ∩ L2 = (L1ᶜ ∪ L2ᶜ)ᶜ, and CFLs are closed under union
   C. Because complement removes terminals
   D. Because CFLs are regular
   Answer: B. If CFLs were closed under complement and union, they would be closed under intersection by De Morgan's law. (Key point: Complement consequence)

## Related in Theory of Computation

- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Aregular-closure-properties) — Theory of Computation, chapter 2, asked 2×
- [Pumping lemma (CFL): ww not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-cfl-ww) — Theory of Computation, chapter 3
- [Pumping lemma (CFL): aⁿbⁿcⁿ not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-cfl-an-bn-cn) — Theory of Computation, chapter 3
- [CFGs for L1, L2; L1∩L2 not CF](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Acfg-l1-l2-pumping-proof) — Theory of Computation, chapter 3

## Related in other subjects

- [Closure properties of regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aclosure-properties-regular-language) — Discrete Structure, chapter 2, asked 2×
- [Context-sensitive, context-free, regular grammars](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Agrammar-types-context-sensitive-free-regular) — Discrete Structure, chapter 2
- [Transmission and y parameters, prove not reciprocal or symmetrical](https://www.bctengineer.com/question.md?key=semester_3%2Felectrical_circuit_theory%3Atransmission-and-y-parameters-neither-reciprocal) — Electrical Circuit Theory, chapter 7, asked 2×
- [3 m wall under wind: free top, fixed bottom](https://www.bctengineer.com/question.md?key=semester_5%2Fconcrete_technology_and_masonry_structure%3Awind-wall-3m-free-top) — Concrete Technology and Masonry Structure, chapter 9, asked 2×