Pumping Lemma for Regular Languages

The pumping lemma for regular languages is a necessary condition that every regular language satisfies. Its main use is negative: if you can show that a language breaks the condition, the language is not regular. It is not a sufficient test; some non-regular languages still satisfy the numeric conclusion for tricky reasons, so failing to pump does not prove regularity.

The skills are the classic non-regular proofs ($\{a^n b^n\}$, $\{ww\}$, $\{a^{n^2}\}$) and the correct quantifier order in the lemma statement.

If $L$ is regular, then there exists a pumping length $p \ge 1$ such that every $w \in L$ with $|w| \ge p$ can be written $w = xyz$ with:

Intuition. In a DFA with $p = |Q|$ states, a path of length $\ge p$ repeats a state inside the first $p+1$ states visited; the loop is $y$.

To show non-regularity, negate: $\forall p$, $\exists w \in L$ with $|w|\ge p$, $\forall$ splits $xyz$ with (1)-(2), $\exists k$ with $xy^k z \notin L$.

For $\{a^n b^n \mid n \ge 0\}$, take $w = a^p b^p$. Then $y$ lies inside the leading $a$'s (because $|xy|\le p$), so pumping changes the number of $a$'s only.

There is no "algorithm" inside the lemma; DFA cycle detection explains why it holds:

Input strings use 1-based positions; run-state visits use indices 0 through |w|.

Let $M$ be a DFA for $L$ with $p = |Q|$. Take $w \in L$, $|w|\ge p$. The run visits $p+1$ states in the first $p$ symbols plus the start, so by pigeonhole two visits $s_i = s_j$ occur with $0 \le i < j \le p$. Set $y$ to the substring between them. The loop can be taken $k$ times, staying accepting because the original run ended accepting and the loop returns to the same state.

For $\{a^n b^n\}$, the prefixes $a^i$ are pairwise distinguishable by the continuations $b^i$. Infinitely many classes $\Rightarrow$ not regular.

Assume regular, pumping length $p$. Let $w = a^p b^p$. For any $xyz$ with $|xy|\le p$, $y = a^t$ for some $t \ge 1$. Then $xy^2 z = a^{p+t} b^p \notin L$. Done.

Take $w = 0^p 1 0^p 1 \in L$. Because $|xy| \le p$, the piece $y = 0^t$ ($t \ge 1$) lies in the first block of 0s. Then $xy^2z = 0^{p+t} 1 0^p 1$: its two halves cannot be equal, since the only way to split it into equal halves of a string with exactly two 1s puts one 1 at the end of each half, which forces equal 0-blocks. So $xy^2z \notin L$. The choice of $w$ matters: $w = 0^p 0^p$ is in $L$ but pumps happily (pumping by an even $t$ stays in $L$, and for $p\ge2$ the adversary may pick $t=2$; an assumed pumping length can always be enlarged to at least 2), so it proves nothing.

Take $w = a^{p^2}$. Pumping adds $|y|$ letters with $1 \le |y| \le p$, producing a length strictly between consecutive squares $p^2$ and $(p+1)^2 = p^2 + 2p + 1$, hence not a square.

$L = a^*$ is regular. For $p=1$, any $w=a^n$ ($n\ge 1$) splits as $x=\varepsilon$, $y=a$, $z=a^{n-1}$; pumping stays in $a^*$. Satisfying the lemma does not by itself prove regularity (but here we already know it is regular via a 1-state DFA).

$L = \{0^n 1^m \mid n > m\}$. Take $w = 0^{p+1} 1^p$. Every legal $y$ is $0^t$ with $1 \le t \le p$. Pumping up keeps $n > m$, so it fails to leave $L$; pumping down ($k = 0$) gives $0^{p+1-t} 1^p$ with $p + 1 - t \le p$, so $n \le m$ and the string is outside $L$. Stopping after $k = 2$ would wrongly suggest that the language pumps.

$L = \{a^q \mid q \text{ prime}\}$. Take a prime $q \ge p + 2$ and $w = a^q$, with $|y| = t$, $1 \le t \le p$. Pump with $k = q - t$: the length is $q - t + (q - t)t = (q - t)(1 + t)$. Both factors are at least 2 ($q - t \ge 2$ because $q \ge p + 2$), so the length is composite and $xy^k z \notin L$.

IMPERATIVE RULE. Before pumping, ask whether the "counting" is really unbounded and coupled. Precisely bounded counts and fixed modular conditions often yield finite-state constructions. A unary alphabet alone is no guarantee: a unary language is regular exactly when its set of lengths is ultimately periodic.

The minimum pumping length of a regular $L$ is the smallest $p$ for which the lemma's conclusion holds. For $L = 0001^*$ it is 4: the string 000 (length 3) cannot be pumped, because removing or repeating any nonempty piece of it leaves $L$; with $p = 4$, every $w = 0001^j$ ($j \ge 1$) pumps with $y$ = the first 1. For $L = (01)^*$ it is 2: with $p = 1$ the string 01 would need $y = 0$, and 1 $\notin L$; with $p = 2$, take $y = 01$. For a finite language, any $p$ larger than its longest string works vacuously, so a finite language never needs to pump.

$L = \{a^i b^j c^k \mid i = 0 \text{ or } j = k\}$. With $p = 1$, every nonempty $w \in L$ pumps with $y$ = its first symbol: if $i \ge 1$, changing the number of $a$s keeps $j = k$ or produces $i = 0$, both in $L$; if $i = 0$, the string is $b^j c^k$ and changing its first block keeps $i = 0$. Yet $L$ is not regular: $L \cap a b^* c^* = \{a b^n c^n\}$, and the left quotient by $a$ gives $\{b^n c^n\}$, which is not regular. So passing the lemma proves nothing.

Wrong: "take $w=a^p b^p$ and set $y=a^{p/2} b^{p/2}$". That split may violate $|xy|\le p$ or place $y$ across the boundary; the adversary chooses the split, so your proof must handle every legal split.

Common misconceptions.