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

# Pumping lemma: a^p, p prime

Theory of Computation · Chapter 2: Finite Automata

- Asked in: 2072 Kartik
- Video: [Prove that L={ a^p p is prime} is not regular || Pumping Lemma for Regular Languages || TOC || FLAT](https://www.youtube.com/watch?v=aw6Akr6_e5k) — 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-prime-not-regular
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-2

## Question

State the pumping lemma for regular languages. Show that the language L = {aⁿ : n is prime} 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. Assume L={a^q | q prime} regular, pick prime q≥p, w=a^q. y=a^k (1≤k≤p). Pump i=q+1: length = q(1+k), composite, contradiction, so L not regular.

## Answer

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

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

1. There are infinitely many primes, so choose a prime q ≥ p (and q ≥ 2). Let w = a^q ∈ L, |w| = q ≥ p.
2. Write w = xyz with |xy| ≤ p, y = aᵏ, 1 ≤ k ≤ p. Then |x| + |z| = q − k.
3. Pump with i = q + 1:

```text
|xy^(q+1)z| = (q − k) + (q + 1)k = q − k + qk + k = q(1 + k)
```

4. Here q ≥ 2 and 1 + k ≥ 2, so q(1 + k) has two factors both greater than 1. It is a composite number, not a prime. So xy^(q+1)z ∉ L.

This contradicts condition 3 of the pumping lemma. Hence L = {aⁿ : n prime} is **not regular**. ∎

(Pumping down with i = 0 does not always work, because q − k may itself be prime. The choice i = q + 1 always gives a composite length.)

## Check yourself

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

1. What is chosen as w for the primes language?
   A. a^q for a prime q ≥ p
   B. a^(2p)
   C. a^p for any p
   D. a^(p^2)
   Answer: A. Infinitely many primes exist, so q ≥ p can be picked. (Key point: String choice)

2. Which i is used and what length results?
   A. i = 0, giving q − k
   B. i = 2, giving q + k
   C. i = q, giving q·k
   D. i = q+1, giving q(1 + k)
   Answer: D. (q−k) + (q+1)k = q(1+k). (Key point: Pump amount)

3. Why is q(1+k) not prime?
   A. It is less than q
   B. It is a perfect square
   C. Both factors are greater than 1
   D. It is even
   Answer: C. q ≥ 2 and 1+k ≥ 2, so it is composite. (Key point: Why composite)

## 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ⁿ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 (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
- [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×
- [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