Skip to main content

Pumping lemma: aⁿbaⁿ 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.

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

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

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →