---
title: "Pumping lemma: aⁿb²ⁿ not regular"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:pumping-an-b2n-not-regular"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-an-b2n-not-regular
site: BCT Engineering
---

# Pumping lemma: aⁿb²ⁿ not regular

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2070 Chaitra; 2073 Shrawan (asked 2 times)
- Video: [Pumping lemma for Regular Language| Prove Language a^nb^n is not Regular|TOC](https://www.youtube.com/watch?v=XVUCrOuL45w) — CSE ACADEMY
- 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-an-b2n-not-regular
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

State the pumping lemma for regular languages and use it to prove that L = {aⁿb²ⁿ : n ≥ 1} is not regular.

## Short answer

The pumping lemma states that for any regular language there is a pumping length p such that every long enough string can be split into xyz with |xy|≤p, |y|≥1, and xy^iz in the language for all i. For L={aⁿb²ⁿ}, choosing a^p b^{2p} forces y to be only a's; pumping yields a mismatch in the 1:2 ratio, so L is not regular.

## Answer

#### Pumping lemma for regular languages
If L is a regular language, there is a constant p ≥ 1 (the pumping length) such that every string w ∈ L with |w| ≥ p can be written as w = xyz with

1. |xy| ≤ p,
2. |y| ≥ 1 (y ≠ ε),
3. xyⁱz ∈ L for every i ≥ 0.

(p can be taken as the number of states of a DFA for L.)

#### Proof that L = {aⁿb²ⁿ : n ≥ 1} is not regular
Use proof by contradiction. Assume L is regular, and let p be its pumping length.

1. Choose w = aᵖb²ᵖ. Then w ∈ L (n = p) and |w| = 3p ≥ p.
2. Let w = xyz with |xy| ≤ p and |y| ≥ 1. Since the first p symbols of w are all a, both x and y consist only of a's. So y = aᵏ for some k with 1 ≤ k ≤ p.
3. Pump with i = 2: the string xy²z = a^(p+k) b^(2p).
4. For this to be in L, the number of b's must be twice the number of a's: 2p = 2(p + k), which gives k = 0. But k ≥ 1, so xy²z ∉ L.

This contradicts condition 3 of the lemma. Hence the assumption was false, and L = {aⁿb²ⁿ} is **not regular**. ∎

(Pumping with i = 0 also works: a^(p−k)b^(2p) has too many b's.)

## Check yourself

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

1. Which conditions does the pumping lemma give for w = xyz?
   A. |y| ≤ p only
   B. |xy| ≥ p, |y| ≥ 1, xy^i z in L
   C. |xy| ≤ p, |y| ≥ 1, and xy^i z in L for all i ≥ 0
   D. xyz = yxz
   Answer: C. These are the three conditions. (Key point: Lemma statement)

2. Which string is chosen for {a^n b^2n}?
   A. (ab)^p
   B. a^p b^2p
   C. a^p b^p
   D. a^2p b^p
   Answer: B. It belongs to L with n = p and has length 3p ≥ p. (Key point: Choice of w)

3. Why does y consist only of a's?
   A. Because the b's come first
   B. |xy| ≤ p and the first p symbols are all a
   C. Because |y| = p
   D. Because y is always a single symbol
   Answer: B. xy lies within the first p symbols, which are a's. (Key point: Form of y)

4. Pumping with i = 2 gives a^(p+k) b^2p. Why is it not in L?
   A. It has b's before a's
   B. It needs 2(p + k) b's but has only 2p, and k ≥ 1
   C. The string is too long
   D. It has no a's
   Answer: B. The b count must be twice the a count, forcing k = 0, contradiction. (Key point: Contradiction)

## Close variants set in other exams

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

## Related in Theory of Computation

- [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 (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: 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×
- [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^p, p prime](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apumping-prime-not-regular) — Theory of Computation, chapter 2, asked 2×
- [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×

## Related in other subjects

- [Regular expressions and regular languages](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Aregular-expressions-and-languages) — Discrete Structure, chapter 2
- [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×