State and Prove the Pumping Lemma for Regular Sets

Verified Sources

Sep 12, 2026

The pumping lemma for regular sets is a structural property of regular languages (equivalently, regular sets of strings). It provides a necessary condition: every regular language admits a “pumping length” so that sufficiently long strings can be decomposed and iterated without leaving the language. A standard use is to prove that certain languages are not regular by contradiction.

We will present (i) a precise statement, (ii) the pumping property using a DFA proof, and (iii) a broader perspective connecting pumping to the finite-state nature of regular languages.

Key notions:

Regular set
Pumping length
Decomposition
DFA

Pumping Lemma for Regular Languages (DFA proof)

Statement (pumping lemma for regular languages)

Let $L$ be a regular language. Then there exists a constant $p \ge 1$ (the pumping length) such that for every string $s \in L$ with $|s| \ge p$ , there exist strings $x,y,z$ with:

$s = xyz$
$|y| \ge 1$
$|xy| \le p$
For all integers $i \ge 0$ , the string $xy^iz \in L$ .

This lemma formalizes the idea that, beyond a certain length, the DFA must revisit some state while processing the prefix of the string, enabling “pumping” of the segment between the repeated states.

Keywords for this section:

Pumping lemma
Factorization
Repetition of states
Closure under repetition

How the lemma is used

To show $L$ is not regular, assume it is regular, apply the lemma, and then pick a specific long string $s\in L$ . If you can show that for every decomposition with $|y|\ge1$ and $|xy|\le p$ , pumping breaks membership, you get a contradiction.

Proof strategy (DFA + pigeonhole principle)

Because $L$ is regular, there exists a DFA $M=(Q,\\Sigma,\\delta,q_0,F)$ that recognizes $L$ . Let $p=|Q|$ .

Take any $s\\in L$ with $|s|\\ge p$ . Consider the sequence of states reached by $M$ while reading the string from left to right. Since $M$ has only $p$ states, within the first $p$ input symbols the machine must repeat a state. The segment of input read between the two visits corresponds to the substring $y$ that can be pumped.

This proof is purely automata-theoretic and relies on:

existence of a DFA for regular languages
the pigeonhole principle on runs of length $p$

DFA-based proof of the pumping lemma

1
Step 1
Since $L$ is regular, fix a DFA $M=(Q,\Sigma,\delta,q_0,F)$ such that $L(M)=L$ . Let $p=|Q|$ .
2
Step 2
Let $s\in L$ with $|s|\ge p$ . Since $M$ accepts $s$ , the run of $M$ on $s$ ends in an accepting state.
3
Step 3
Write $s=a_1a_2\dots a_n$ with $n=|s|\ge p$ . Consider the sequence of states $r_0,r_1,\dots,r_p$ where $r_0=q_0$ and $r_k=\delta(r_{k-1},a_k)$ for $1\le k\le p$ .
4
Step 4
There are $p+1$ states in the sequence $(r_0,\dots,r_p)$ but only $p$ distinct states in $Q$ . Therefore, there exist indices $0\le i<j\le p$ such that $r_i=r_j$ .
5
Step 5
Let $x=a_1\dots a_i$ , $y=a_{i+1}\dots a_j$ , and $z=a_{j+1}\dots a_n$ . Then $s=xyz$ and $|y|=j-i\ge 1$ . Also, $|xy|=j\le p$ .
6
Step 6
Let $\delta$ -run from state $r_i$ . Because $r_i=r_j$ , reading the block $y$ takes the machine from $r_i$ back to $r_i$ . Hence, for any $i\ge 0$ , the run on $xy^iz$ follows the same sequence as on $xyz$ except that the loop induced by $y$ is repeated $i$ times. Therefore, $M$ ends in the same final state as it would on $xyz$ , so $xy^iz\in L$ for all $i\ge 0$ .
7
Step 7
All required conditions hold: $s=xyz$ , $|y|\ge1$ , $|xy|\le p$ , and $xy^iz\in L$ for every $i\ge0$ . Thus $L$ satisfies the pumping lemma.

Formalizing the “same final state” argument

Let the DFA run on $xyz$ reach state $r_i$ after reading $x$ , then after reading $y$ reach again $r_j=r_i$ . By induction, after reading $y^i$ the DFA is still in $r_i$ . Consequently, the suffix $z$ moves the machine from $r_i$ to the same state it reaches on $z$ after the original $i$ -th visit. Since $M$ accepts $xyz$ , it also accepts $xy^iz$ for all $i\\ge 0$ .

We have therefore established the pumping property: $\\forall s\\in L,\\ |s|\\ge p,\\ \\exists x,y,z:\\ s=xyz,\\ |y|\\ge1,\\ |xy|\\le p,\\ \\forall i\\ge0,\\ xy^iz\\in L.$

Keywords:

Loop state
[Induction on pumping factor]{def="Proving $y^i$ keeps the run in the same state via repeated application"}
Acceptance
Run on input

Common mistake: pumping both sides

The lemma guarantees pumping the middle substring $y$ with $|xy|\le p$ and $|y|\ge1$ . Pumping arbitrary parts of the string (e.g., prefix or suffix) is not supported by the theorem.

Where the $|xy|\\le p$ condition comes from

Because the repeated state is guaranteed among the first $p$ transitions, we can ensure that $j\\le p$ . By construction $|xy|=|a_1\\dots a_j|=j$ , so $|xy|\\le p$ .

This matters: the lemma does not allow us to pump anywhere in the string—it forces the pumped section to lie within the first $p$ symbols of the input.

Mermaid view of how the repeated state yields a loop:

Keywords:

Prefix length bound
[Repeated-state loop]{def="A cycle in the DFA run enabling $y$ to be iterated"}

Alternative viewpoint: pumping as a consequence of finiteness

The pumping lemma is ultimately a manifestation of finite memory. A DFA has finitely many states; reading enough symbols forces repetition. The decomposed substring $y$ is precisely the segment that takes the automaton around a cycle. Pumping corresponds to traversing this cycle multiple times.

This is also why the lemma works for all equivalent regular model forms (e.g., regexes via DFA/NFA conversion, or right-linear grammars), because they all characterize the same class of languages.

Keywords:

Finite automaton
Cycle pumping
Equivalence of models

Constraints in the Pumping Lemma

What each condition guarantees

Edge cases and subtleties

Knowledge Check

Question 1 of 4

Q1Single choice

Let $L$ be regular. In the pumping lemma, we pick $p=|Q|$ for a DFA with state set $Q$ . Which condition must the decomposition $s=xyz$ satisfy?

$|y|\ge 1$ and $|xy|\le p$

$|y|=0$ and $|xy|\le p$

$|y|\ge 1$ and $|xz|\le p$

$|x|\le p$ and $|z|\le p$

Explore Related Topics

Finite-State Machines (FSM): A Short Note with Core Theory and Examples

Converting the Regular Expression $(a+b)^*ab$ into an NFA

The course shows how to turn the regular expression  $(a+b)^*ab$ —the set of all strings over  $\{a,b\}$ that end with “ab”—into an NFA, first via Thompson’s systematic ε‑construction and then with a minimal three‑state NFA.

Thompson’s construction builds ε‑transitions for symbols  $a$ ,  $b$ , their union, the Kleene star, and the final concatenations, yielding a 12‑state ε‑NFA.
A compact direct NFA uses only three states: $q_0$ loops on $a,b$ , branches on $a$ to $q_1$ , and $q_1$ moves on $b$ to accepting $q_2$ .
The compact NFA’s transition table illustrates nondeterministic moves (e.g., $δ(q_0,a)=\{q_0,q_1\}$ ) and accepts exactly the strings ending in “ab”.
State‑complexity comparison: Thompson’s method needs many states and ε‑moves, while the direct NFA is far smaller and easier to simulate.

Rice’s Theorem (Undecidability of All Nontrivial Semantic Properties)

Browse all research articles

State and Prove the Pumping Lemma for Regular Sets

Pumping Lemma for Regular Languages (DFA proof)

Statement (pumping lemma for regular languages)

How the lemma is used

Proof strategy (DFA + pigeonhole principle)

DFA-based proof of the pumping lemma

Formalizing the “same final state” argument

Common mistake: pumping both sides

Where the ∣xy∣lep|xy|\\le p∣xy∣lep condition comes from

Alternative viewpoint: pumping as a consequence of finiteness

Constraints in the Pumping Lemma

Edge cases and subtleties

Knowledge Check

Explore Related Topics

Where the $|xy|\\le p$ condition comes from