Skip to main content

Pumping lemma: a^p, p prime

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.

State the pumping lemma for regular languages. Show that the language L = {aⁿ : n is prime} is not regular.

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:
|xy^(q+1)z| = (q − k) + (q + 1)k = q − k + qk + k = q(1 + k)
  1. 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.)

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →