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

# Pumping lemma: aⁿbaⁿ not regular

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Chaitra
- Video: [Proving Non-Regular Languages Using the Pumping Lemma | Theory of Computation](https://www.youtube.com/watch?v=MDxqPLa7k4U) — Engineering Funda
- 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-anban-not-regular
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

Define the pumping lemma for regular languages. Use it to show that L = {aⁿbaⁿ : n = 0, 1, 2, ...} is not regular.

## Short answer

If L is regular, there exists p such that any w∈L with |w|≥p can be split w=xyz with |xy|≤p, |y|≥1 and xy^iz∈L for all i. For L={a^n b a^n}, assume regular with p, take w=a^p b a^p. Since |xy|≤p, y=a^k (k≥1). Then xy^2z = a^(p+k) b a^p, not of form a^n b a^n, contradiction, so L not regular.

## Answer

#### Pumping lemma
If L is regular, there is an integer p ≥ 1 such that every w ∈ L with |w| ≥ p can be split as w = xyz where

1. |xy| ≤ p,
2. |y| ≥ 1,
3. xyⁱz ∈ L for all i ≥ 0.

#### Proof that L = {aⁿbaⁿ : n ≥ 0} is not regular
Assume L is regular with pumping length p.

1. Take w = aᵖbaᵖ ∈ L. |w| = 2p + 1 ≥ p.
2. Write w = xyz with |xy| ≤ p and |y| ≥ 1. The first p symbols are all a, so y = aᵏ with 1 ≤ k ≤ p (y lies inside the first block of a's).
3. Take i = 2: xy²z = a^(p+k) b aᵖ.
4. This string has p + k a's before the b and only p after it. Since k ≥ 1, the two counts are different, so it is not of the form aⁿbaⁿ. Thus xy²z ∉ L.

This contradicts the pumping lemma. Therefore L = {aⁿbaⁿ} is **not regular**. ∎

## Check yourself

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

1. Which string is used for {a^n b a^n}?
   A. a^p b
   B. a^p b a^p
   C. b a^p
   D. a^p b^p a^p
   Answer: B. It is in L and has length 2p + 1. (Key point: String choice)

2. Why is y = a^k with 1 ≤ k ≤ p?
   A. Because |y| must equal p
   B. Because y contains the b
   C. Because x is empty
   D. |xy| ≤ p and the first p symbols are all a
   Answer: D. xy is inside the first block of a's. (Key point: Location of y)

3. What does pumping with i = 2 give?
   A. a^p b^2 a^p
   B. a^(p+k) b a^p, with unequal a's on both sides
   C. a^(p−k) b a^p
   D. a^p b a^(p+k), which is in L
   Answer: B. More a's before the b than after, so not of the form a^n b a^n. (Key point: Pump)

## Related in Theory of Computation

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

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