The Pumping Lemma

Statement

Theorem (Pumping Lemma for Regular Languages):

Let $L$ be a regular language. There exists $p \geq 1$ (the pumping length) such that for every $w \in L$ with $|w| \geq p$:

$w$ can be written as $w = xyz$ where:

1. $|xy| \leq p$
2. $|y| \geq 1$ (so $y \neq \varepsilon$)
3. $xy^iz \in L$ for all $i \geq 0$

Intuition

If a string is long enough and the language is regular, then some part of the string can be “pumped” (repeated) any number of times while staying in the language.

The pumped part corresponds to a loop in an accepting computation of the DFA.

Proof Idea

Let $M = (Q, \Sigma, \delta, s, F)$ be a DFA for $L$ with $|Q| = n$.

Set $p = n$.

For any $w \in L$ with $|w| \geq n$: the computation visits $n+1$ states in sequence. By the pigeonhole principle, some state is visited twice.

The part of $w$ that causes the loop can be pumped.

Formal Argument

Path through DFA: $s = q_0 \to q_1 \to \cdots \to q_{|w|} = q_f$.

Since $|w| \geq n+1$ states are visited, but there are only $n$ states, some $q_i = q_j$ for $i < j$.

Let $x = w[0..i]$ (before the loop), $y = w[i..j]$ (the loop), $z = w[j..|w|]$ (after).

• Condition 1: Loop occurs within first $n$ states, so $|xy| \leq n = p$
• Condition 2: $i < j$, so $|y| \geq 1$
• Condition 3: Repeating or omitting the loop keeps the computation in the accepting state

Using the Pumping Lemma

To Prove Non-regularity

1. Assume $L$ is regular with pumping length $p$
2. Choose a string $w \in L$ with $|w| \geq p$
3. Show that for ALL possible decompositions $w = xyz$ satisfying conditions 1 and 2:
   • There exists $i$ such that $xy^iz \notin L$
4. Conclude: contradiction, so $L$ is not regular

Key Point

You must show that the pumping lemma fails for every possible choice of $x, y, z$ satisfying the conditions.

Application: $L = \{a^n b^n : n \geq 0\}$

Proof

Assume $L$ is regular with pumping length $p$.

Choose $w = a^p b^p$ (in $L$, length $\geq p$).

For any decomposition $w = xyz$ with $|xy| \leq p$ and $|y| \geq 1$:

• Since $|xy| \leq p$, the substring $xy$ consists of only $a$‘s
• Thus $y = a^k$ for some $k \geq 1$

Consider $xy^2z = a^{p+k} b^p$:

• Number of $a$‘s is $p+k > p$
• Number of $b$‘s is $p$
• Not equal, so $xy^2z \notin L$

Contradiction. Thus $L$ is not regular.

Application: $L = \{ww : w \in \{a, b\}^*\}$

Proof

Assume $L$ is regular with pumping length $p$.

Choose $w = a^p b a^p b$ (in $L$, length $2p+2 \geq p$).

For any decomposition $w = xyz$ with $|xy| \leq p$ and $|y| \geq 1$:

• $|xy| \leq p$ means $xy$ lies within the first $a^p b$ (actually, within first $a^p$)
• So $y = a^k$ for some $k \geq 1$

Consider $xy^2z = a^{p+k} b a^p b$:

• This is not of the form $ww$ (different lengths of prefix)
• Alternatively: after pumping, the string is $a^{p+k} b a^p b$, not a square

Contradiction.

Application: $L = \{a^{n^2} : n \geq 0\}$

Proof

Choose $w = a^{p^2}$.

The pumped string is $a^{p^2+k}$ for some $k$ with $1 \leq k \leq p$.

We need $p^2 + k$ to be a perfect square.

But $(p+1)^2 = p^2 + 2p + 1 > p^2 + k$ for $k \leq p$.

So $a^{p^2+k} \notin L$.

Limitations of the Pumping Lemma

The pumping lemma is a necessary condition for regularity, not sufficient.

Some non-regular languages satisfy the pumping lemma conditions.

For proving non-regularity, use:

• Pumping lemma
• Myhill-Nerode theorem
• Closure properties

---

Summary

• Pumping lemma: long strings in regular languages have pumpable parts
• Proof uses pigeonhole principle on DFA states
• Use: assume regular, find a counterexample string, show pumping fails
• Applications: $a^n b^n$, $ww$, $\{a^{n^2}\}$ are not regular
• Not a characterisation: necessary, not sufficient