The pumping lemma

Every sufficiently long string accepted by an FSA must take the machine through some state at least twice. The part of the path between those two visits is a cycle. Traversing that cycle a different number of times yields a different accepted string. This repeated-state argument appears in the classical development of finite automata (Rabin and Scott 1959).

The pumping lemma turns this observation into a necessary property of every regular language.

Statement of the lemma

If $L$ is regular, then there is some pumping length $p>0$ such that every $w\in L$ with $|w|\geq p$ can be written as $w=xyz$ with the following properties:

$|y|>0$;
$|xy|\leq p$; and
$xy^iz\in L$ for every $i\geq0$.

What does the decomposition represent? The substring $y$ labels a nonempty cycle among the first $p$ transitions of an accepting path. Setting $i=0$ removes that cycle; setting $i>1$ repeats it.

Why the lemma is true

Let $L$ be regular. Then some deterministic finite-state automaton $M$ recognizes $L$. Suppose $M$ has $m$ states, and set the pumping length to $p=m$.

Now fix an arbitrary $w\in L$ with $|w|\geq p$. Because $M$ accepts $w$, there is an accepting run

\[ q_0\xrightarrow{\sigma_1}q_1 \xrightarrow{\sigma_2}\cdots \xrightarrow{\sigma_{|w|}}q_{|w|}. \]

Look only at the first $p+1$ visited states:

\[q_0,q_1,\ldots,q_p.\]

There are $p+1$ positions on this list but only $p$ states in the automaton. Thus, two positions must contain the same state. Choose positions $r<s\leq p$ such that $q_r=q_s$.

Split $w$ at those two positions:

\[ \underbrace{\sigma_1\cdots\sigma_r}_{x} \underbrace{\sigma_{r+1}\cdots\sigma_s}_{y} \underbrace{\sigma_{s+1}\cdots\sigma_{|w|}}_{z}. \]

Now check the three required properties one at a time. First, $s>r$, so $y$ is nonempty. Second, $s\leq p$, so $|xy|\leq p$. Third, reading $y$ takes the automaton from $q_r$ back to that same state, since $q_r=q_s$. The automaton may thus traverse this loop zero times, once, or any larger number of times before continuing along the path labeled $z$. Every string $xy^iz$ follows a path to the same accepting state as $w$.

We began with an arbitrary sufficiently long $w\in L$, so the argument supplies an appropriate decomposition for every such string. This proves the lemma. Rabin and Scott prove essentially this loop property as their Lemma 8. They then use it to give another proof that $\{0^n10^n\mid n\geq0\}$ cannot be defined by a finite automaton (Rabin and Scott 1959).

Quantifier order

To show that a language $L$ is not regular, we must argue as follows:

\[ \forall p\;\exists w\;\forall(x,y,z)\;\exists i \]

where $|w|\geq p$, $w=xyz$, $|y|>0$, $|xy|\leq p$, and $xy^iz\notin L$. We choose $w$ after the proposed pumping length is given, but an adversary chooses the decomposition. Thus, exhibiting one decomposition that fails is not enough.

Proving that $\{a^nb^n\mid n\geq0\}$ is not regular

Let

\[L=\{a^nb^n\mid n\geq0\}.\]

Assume for contradiction that $L$ is regular. We proceed in the order required by the quantifiers.

The pumping lemma supplies some pumping length $p$.
We respond with $w=a^pb^p$. This string belongs to $L$, and its length is at least $p$.
Now let an adversary choose any permitted decomposition $w=xyz$. We do not choose this decomposition.
Because $|xy|\leq p$, both $x$ and $y$ end within the first block of $p$ copies of $a$. Because $|y|>0$, we must have $y=a^k$ for some $1\leq k\leq p$.
We choose $i=0$, which removes the adversary’s substring $y$.

The resulting string is

\[xz=a^{p-k}b^p.\]

It contains $p-k$ copies of $a$ and $p$ copies of $b$. Since $k>0$, these counts differ, so $xz\notin L$.

The same response $i=0$ defeats every permitted decomposition: the only value that changes is the positive integer $k$. Thus, the proposed $p$ cannot be a pumping length. This contradicts the consequence of our regularity assumption, so $L$ is not regular.

The proof identifies the unbounded matching requirement: the language must retain an arbitrarily large count across the boundary between the $a$s and the $b$s. A finite set of states cannot store that count.

Question

Does every language that satisfies the conclusion of the pumping lemma have to be regular?

Answer

No. The pumping property is necessary for regularity, not sufficient. The lemma can prove that some languages are nonregular, but it cannot certify that a language is regular.

The same proof strategy will let us diagnose unbounded copying. We will keep that problem separate from hierarchical constituency, which motivates context-free grammars for a different reason.

References

Rabin, Michael O., and Dana Scott. 1959. “Finite Automata and Their Decision Problems.” IBM Journal of Research and Development 3 (2): 114–25. https://doi.org/10.1147/rd.32.0114.

--- title: The pumping lemma bibliography: ../../references.bib --- Every sufficiently long string accepted by an FSA must take the machine through some state at least twice. The part of the path between those two visits is a cycle. Traversing that cycle a different number of times yields a different accepted string. This repeated-state argument appears in the classical development of finite automata [@rabin_finite_1959]. The **pumping lemma** turns this observation into a necessary property of every regular language. ## Statement of the lemma If $L$ is regular, then there is some pumping length $p>0$ such that every $w\in L$ with $|w|\geq p$ can be written as $w=xyz$ with the following properties: 1. $|y|>0$; 2. $|xy|\leq p$; and 3. $xy^iz\in L$ for every $i\geq0$. What does the decomposition represent? The substring $y$ labels a nonempty cycle among the first $p$ transitions of an accepting path. Setting $i=0$ removes that cycle; setting $i>1$ repeats it. ## Why the lemma is true Let $L$ be regular. Then some deterministic finite-state automaton $M$ recognizes $L$. Suppose $M$ has $m$ states, and set the pumping length to $p=m$. Now fix an arbitrary $w\in L$ with $|w|\geq p$. Because $M$ accepts $w$, there is an accepting run $$ q_0\xrightarrow{\sigma_1}q_1 \xrightarrow{\sigma_2}\cdots \xrightarrow{\sigma_{|w|}}q_{|w|}. $$ Look only at the first $p+1$ visited states: $$q_0,q_1,\ldots,q_p.$$ There are $p+1$ positions on this list but only $p$ states in the automaton. Thus, two positions must contain the same state. Choose positions $r<s\leq p$ such that $q_r=q_s$. Split $w$ at those two positions: $$ \underbrace{\sigma_1\cdots\sigma_r}_{x} \underbrace{\sigma_{r+1}\cdots\sigma_s}_{y} \underbrace{\sigma_{s+1}\cdots\sigma_{|w|}}_{z}. $$ Now check the three required properties one at a time. First, $s>r$, so $y$ is nonempty. Second, $s\leq p$, so $|xy|\leq p$. Third, reading $y$ takes the automaton from $q_r$ back to that same state, since $q_r=q_s$. The automaton may thus traverse this loop zero times, once, or any larger number of times before continuing along the path labeled $z$. Every string $xy^iz$ follows a path to the same accepting state as $w$. We began with an arbitrary sufficiently long $w\in L$, so the argument supplies an appropriate decomposition for every such string. This proves the lemma. Rabin and Scott prove essentially this loop property as their Lemma 8. They then use it to give another proof that $\{0^n10^n\mid n\geq0\}$ cannot be defined by a finite automaton [@rabin_finite_1959]. ::: {.callout-caution} ## Quantifier order To show that a language $L$ is not regular, we must argue as follows: $$ \forall p\;\exists w\;\forall(x,y,z)\;\exists i $$ where $|w|\geq p$, $w=xyz$, $|y|>0$, $|xy|\leq p$, and $xy^iz\notin L$. We choose $w$ after the proposed pumping length is given, but an adversary chooses the decomposition. Thus, exhibiting one decomposition that fails is not enough. ::: ## Proving that $\{a^nb^n\mid n\geq0\}$ is not regular Let $$L=\{a^nb^n\mid n\geq0\}.$$ Assume for contradiction that $L$ is regular. We proceed in the order required by the quantifiers. 1. The pumping lemma supplies some pumping length $p$. 2. We respond with $w=a^pb^p$. This string belongs to $L$, and its length is at least $p$. 3. Now let an adversary choose any permitted decomposition $w=xyz$. We do not choose this decomposition. 4. Because $|xy|\leq p$, both $x$ and $y$ end within the first block of $p$ copies of $a$. Because $|y|>0$, we must have $y=a^k$ for some $1\leq k\leq p$. 5. We choose $i=0$, which removes the adversary's substring $y$. The resulting string is $$xz=a^{p-k}b^p.$$ It contains $p-k$ copies of $a$ and $p$ copies of $b$. Since $k>0$, these counts differ, so $xz\notin L$. The same response $i=0$ defeats every permitted decomposition: the only value that changes is the positive integer $k$. Thus, the proposed $p$ cannot be a pumping length. This contradicts the consequence of our regularity assumption, so $L$ is not regular. The proof identifies the **unbounded matching requirement**: the language must retain an arbitrarily large count across the boundary between the $a$s and the $b$s. A finite set of states cannot store that count. ::: {.callout-caution} ## Question Does every language that satisfies the conclusion of the pumping lemma have to be regular? ::: ::: {.callout-tip collapse=true} ## Answer No. The pumping property is necessary for regularity, not sufficient. The lemma can prove that some languages are nonregular, but it cannot certify that a language is regular. ::: The same proof strategy will let us diagnose unbounded copying. We will keep that problem separate from hierarchical constituency, which motivates context-free grammars for a different reason.

Statement of the lemma

Why the lemma is true

Proving that \(\{a^nb^n\mid n\geq0\}\) is not regular

References