---
title: "CFGs for L1, L2; L1∩L2 not CF"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:cfg-l1-l2-pumping-proof"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-l1-l2-pumping-proof
site: BCT Engineering
---

# CFGs for L1, L2; L1∩L2 not CF

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2070 Chaitra
- Video: [Pumping Lemma for Context Free Language with example (a^n b^n c^n)  || TOC || FLAT || Theory of Com.](https://www.youtube.com/watch?v=nnyHfZssTWA) — Sudhakar Atchala
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/cfg-l1-l2-pumping-proof
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Write context free grammars (CFG) for the languages L1 = {aᵐbⁿcⁿ : m ≥ 1, n ≥ 1} and L2 = {aⁿbⁿcᵐ : m ≥ 1, n ≥ 1}, and L = L1 ∩ L2. Prove that the language thus obtained is not context free by using the pumping lemma for context free languages. [The printed combining operator is hard to read; the solution takes the intersection.]

## Short answer

L1: S→AB, A→aA|a, B→bBc|bc. L2: S→AB, A→aAb|ab, B→cB|c. Intersection yields {a^n b^n c^n}. Pumping lemma: pick s=a^p b^p c^p; vxy misses one letter, pumping changes other counts, breaking equality, so not CFL.

## Answer

#### CFG for L1 = { aᵐbⁿcⁿ : m ≥ 1, n ≥ 1 }
Some a's (at least one), then equal numbers of b's and c's (at least one each).

```text
S → A B
A → aA | a
B → bBc | bc
```

#### CFG for L2 = { aⁿbⁿcᵐ : m ≥ 1, n ≥ 1 }
Equal a's and b's (at least one each), then at least one c.

```text
S → A B
A → aAb | ab
B → cB | c
```

#### L = L1 ∩ L2
A string in both has the form a*b*c* with (#a = #b) from L2 and (#b = #c) from L1. So

L = { aⁿbⁿcⁿ : n ≥ 1 }.

#### Proof that L is not context free (pumping lemma)
Suppose L is a CFL with pumping length p. Take s = aᵖbᵖcᵖ ∈ L, |s| ≥ p, and write s = uvxyz with |vxy| ≤ p, |vy| ≥ 1, and uvⁱxyⁱz ∈ L for all i ≥ 0.

- Because |vxy| ≤ p, the substring vxy cannot contain both a and c (the p b's lie between them). So vxy misses at least one of the three letters, and that letter keeps its count p in every pumped string.
- Because |vy| ≥ 1, at least one other letter occurs in v or y, so its count changes when we pump with i = 2 (it becomes larger than p).
- Hence in uv²xy²z the numbers of a's, b's and c's are not all equal. (If v or y mixes two letters, the order a…b…c is also broken.)

So uv²xy²z ∉ L, a contradiction. Hence L1 ∩ L2 = { aⁿbⁿcⁿ } is **not context free**, although L1 and L2 both are. This also shows that context free languages are not closed under intersection.

## Check yourself

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

1. Which grammar generates L1 = {aᵐbⁿcⁿ : m,n ≥ 1}?
   A. S → AB; A → aA | a; B → bBc | bc
   B. S → AB; A → aAb | ab; B → cB | c
   C. S → aSbc
   D. S → ABC
   Answer: A. A makes one or more a's, and B makes matched bⁿcⁿ with n ≥ 1. (Key point: Grammar for L1)

2. In the grammar for L2 = {aⁿbⁿcᵐ}, which variable generates the matched a's and b's?
   A. B → cB | c
   B. S
   C. A → aAb | ab
   D. Neither
   Answer: C. A → aAb | ab produces aⁿbⁿ with n ≥ 1; B produces the c's. (Key point: Grammar for L2)

3. What is L1 ∩ L2?
   A. {aⁿbⁿcⁿ : n ≥ 1}
   B. {aᵐbⁿ}
   C. a⁺b⁺c⁺
   D. {aⁿbⁿ}
   Answer: A. #a = #b and #b = #c force equal counts. (Key point: Intersection)

4. Why does pumping fail on aᵖbᵖcᵖ?
   A. vxy contains all three letters
   B. |vxy| ≤ p means vxy misses a letter, so after pumping the counts are no longer all equal
   C. The lemma does not apply
   D. |vy| = 0
   Answer: B. One letter stays at p while another grows, so the counts differ. (Key point: Pumping step)

## Related in Theory of Computation

- [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
- [Pumping lemma: a^(n²) not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-square-not-regular) — Theory of Computation, chapter 2, asked 5×
- [Pumping lemma: aⁿb²ⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-an-b2n-not-regular) — Theory of Computation, chapter 2, asked 3×
- [Pumping lemma: aⁿbaⁿ not regular](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-anban-not-regular) — Theory of Computation, chapter 2
- [Pumping lemma: equal 0s and 1s](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-equal-zeros-ones) — Theory of Computation, chapter 2, asked 2×

## Related in other subjects

- [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
- [High level languages and natural language](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Ahll-similar-natural-language) — Computer Programming, chapter 1