Skip to main content

Pumping lemma: a^(n²) 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.

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

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:
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. ∎

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →