---
title: "Pumping lemma (CFL): aⁿbⁿcⁿ not CF"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:pumping-cfl-an-bn-cn"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-cfl-an-bn-cn
site: BCT Engineering
---

# Pumping lemma (CFL): aⁿbⁿcⁿ not CF

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2072 Kartik
- 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/pumping-cfl-an-bn-cn
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Using the pumping theorem for context free languages, show that L = {aⁿbⁿcⁿ : n ≥ 0} is not context free.

## Short answer

Assume L is CFL with pumping length p. Choose s = a^p b^p c^p. Since |vxy| ≤ p, vxy misses at least one letter. With i=2, counts of other letters increase, breaking equality. Thus L is not context free.

## Answer

**Pumping lemma for CFLs:** if L is context free, there is a constant p such that every s ∈ L with |s| ≥ p can be written s = uvxyz with (1) |vxy| ≤ p, (2) |vy| ≥ 1, (3) uvⁱxyⁱz ∈ L for all i ≥ 0.

#### Proof that L = { aⁿbⁿcⁿ : n ≥ 0 } is not context free
Assume L is context free, with pumping length p.

1. Choose s = aᵖbᵖcᵖ. Then s ∈ L and |s| = 3p ≥ p.
2. Let s = uvxyz satisfy the lemma. Since |vxy| ≤ p, the substring vxy cannot contain both an a and a c (between the last a and the first c there are p b's). So vxy has at most two kinds of letters, and some letter among a, b, c does not appear in vxy.
3. The letters in v and y come from at most two of a, b, c, and |vy| ≥ 1. Pumping changes the counts of only those letters; the missing letter keeps count p.
4. Take i = 2 (pumping up). Because |vy| ≥ 1, at least one letter count increases above p, while at least one letter (the one not in vxy) keeps count exactly p. Hence the counts of a, b, c are not all equal.
5. If v or y contains two different letters, uv²xy²z also has letters out of the order a…b…c.

In every case uv²xy²z ∉ L, which contradicts condition (3).

Therefore the assumption is false: **L = { aⁿbⁿcⁿ } is not context free.**

(It is context sensitive. A single stack can compare two counts, but it cannot check three equal counts, since popping destroys the count.)

## Check yourself

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

1. What conditions does the CFL pumping lemma require for s = uvxyz?
   A. |vxy| ≤ p, |vy| ≥ 1, uvⁱxyⁱz ∈ L for all i ≥ 0
   B. |uv| ≤ p, |v| ≥ 1
   C. |vxy| ≥ p, |vy| = 0
   D. uvⁱz ∈ L only for i = 1
   Answer: A. These are the three standard conditions. (Key point: Pumping lemma)

2. Which string is chosen to show aⁿbⁿcⁿ is not a CFL?
   A. aᵖbᵖ
   B. abc
   C. aᵖbᵖcᵖ
   D. a²ᵖb
   Answer: C. s = aᵖbᵖcᵖ is in L and has length at least p. (Key point: Choice of string)

3. Why can vxy not contain both a and c?
   A. a and c are not allowed
   B. The p b's lie between them and |vxy| ≤ p
   C. |vxy| = 1
   D. v is empty
   Answer: B. Spanning from an a to a c needs at least p+2 symbols. (Key point: Key observation)

4. Why is uv²xy²z not in L?
   A. It is too short
   B. The missing letter keeps count p while another count rises, so the counts are unequal
   C. The string becomes empty
   D. The counts remain equal
   Answer: B. Pumping changes at most two letters' counts, breaking the equality. (Key point: Contradiction)

## 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: 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
- [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
- [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×