---
title: "Pumping lemma: a^(n²) not regular"
subject: "Theory of Computation"
chapter: 2
key: "semester_3/theory_of_computation:pumping-square-not-regular"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pumping-square-not-regular
site: BCT Engineering
---

# Pumping lemma: a^(n²) not regular

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2071 Chaitra
- Video: [Show that L={0^n^2} is not regular || perfect square || Pumping Lemma for Regular Languages || TOC](https://www.youtube.com/watch?v=ccdsYbgQUHY) — 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-square-not-regular
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

State the pumping lemma for regular languages. Using this lemma, prove that the language L = {a^(n²) : n > 0} is not regular.

## Short answer

If L is regular, there exists p≥1 such that any w∈L with |w|≥p can be split w=xyz, |xy|≤p, |y|≥1, xyⁱz∈L for all i. For L={a^(n^2)}, assume regular with p, pick w=a^(p^2). Then y=a^k (1≤k≤p); i=2 gives length p^2+k, strictly between p^2 and (p+1)^2, not a perfect square, contradiction, so L not regular.

## Answer

#### Pumping lemma
If L is regular, there exists p ≥ 1 such that any w ∈ L with |w| ≥ p can be written w = xyz with |xy| ≤ p, |y| ≥ 1 and xyⁱz ∈ L for every i ≥ 0.

#### Proof that L = {a^(n²) : n > 0} is not regular
Assume L is regular, with pumping length p.

1. Take w = a^(p²). Then w ∈ L and |w| = p² ≥ p.
2. Let w = xyz, |xy| ≤ p, |y| = k with 1 ≤ k ≤ p.
3. Pump with i = 2: |xy²z| = p² + k.
4. Bounds on this length:

```text
p²  <  p² + k  ≤  p² + p  <  p² + 2p + 1 = (p+1)²
```

So p² + k lies strictly between the consecutive perfect squares p² and (p+1)². It is therefore not a perfect square, so a^(p²+k) ∉ L.

This contradicts condition 3. Hence L is **not regular**. ∎

## Check yourself

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

1. Which w is taken for L = {a^(n^2)}?
   A. a^(p+1)
   B. a^p
   C. a^(2p)
   D. a^(p^2)
   Answer: D. It is in L, with length p^2 ≥ p. (Key point: String choice)

2. With i = 2 and |y| = k, what is |xy^2 z|?
   A. p^2 + 2k
   B. 2p^2
   C. p^2 + k
   D. p^2 − k
   Answer: C. Pumping adds k symbols. (Key point: Length after pumping)

3. Why is p^2 + k not a perfect square?
   A. p^2 < p^2 + k ≤ p^2 + p < (p+1)^2, strictly between consecutive squares
   B. Because k is even
   C. Because it equals (p+1)^2
   D. Because it is prime
   Answer: A. No perfect square lies strictly between p^2 and (p+1)^2. (Key point: Contradiction)

## Close variants set in other exams

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

- [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×
- [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
- [Language of grammar; grammar for strings not ending in ab](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Alanguage-of-grammar-and-grammar-not-ending-ab) — Discrete Structure, chapter 2