Pumping lemma for regular languages

Why it exists

DFAs have finitely many states, so a long enough input must repeat a state, and the part of the input between the two visits can be repeated any number of times without the machine noticing. The pumping lemma turns this observation into a test: if a language has no such repeatable part, it is not regular. GATE asks it constantly: "which of these languages is not regular?" and "which step of this proof is wrong?"

Prerequisites

You need closure properties of regular languages (closure properties): many non-regularity proofs combine the pumping lemma with intersection or complement.

Precise definitions

Pumping lemma. If $L$ is a regular language, then there is an integer $p \ge 1$ (the pumping length) such that every string $w \in L$ with $|w| \ge p$ can be written as $w = xyz$ with

1. $|y| \ge 1$ (the pumped part is not empty),
2. $|xy| \le p$ (the pumped part lies within the first $p$ symbols),
3. $x y^i z \in L$ for every $i \ge 0$ (pumping up and also "pumping down" with $i = 0$).

Quantifier structure (this is where mistakes come from):

$L \text{ regular} \Rightarrow \exists p \ \forall w \in L,\ |w| \ge p \ \ \exists x, y, z \ \bigl(w = xyz,\ |y| \ge 1,\ |xy| \le p,\ \forall i \ge 0:\ xy^iz \in L\bigr).$

It is only a necessary condition. The lemma can prove a language is not regular; it can never prove that a language is regular.

Proof sketch. Take a DFA for $L$ and let $p$ be its number of states. Let $w \in L$, $|w| \ge p$. Reading the first $p$ symbols visits $p + 1$ states (counting the start state), so by the pigeonhole principle some state $q$ occurs twice among them. Let $x$ be the string that leads from the start to the first visit of $q$, $y$ the nonempty string that leads from $q$ back to $q$, and $z$ the rest. Then $|xy| \le p$, $|y| \ge 1$ and going round the loop $i$ times (or not at all) still ends in the same accepting state: $x y^i z \in L$.

How it works

The game

To prove $L$ is not regular, play against an adversary who claims $L$ is regular.

1. The adversary chooses $p$ (you cannot choose it).
2. You choose a string $w \in L$ with $|w| \ge p$ (it may depend on $p$; choose it so that the first $p$ symbols are very restricted).
3. The adversary chooses any cut $w = xyz$ with $|xy| \le p$ and $|y| \ge 1$.
4. You choose $i \ge 0$ so that $x y^i z \notin L$.

If you have a winning strategy for every $p$ and every cut, $L$ is not regular. The table plays the game with $p = 5$ for six languages: for each, the string you choose, the number of legal cuts ($15$ when $|w| \ge 5$: the pairs $(|x|, |y|)$ with $|x| + |y| \le 5$, $|y| \ge 1$), how many cuts survive pumping with $i = 0, \ldots, 9$ and which $i$ breaks them.

In every row no cut survives, which is the proof. Below are the arguments in words.

Standard proofs

$L = \{a^n b^n : n \ge 0\}$. Choose $w = a^p b^p$. Since $|xy| \le p$, $y$ consists only of $a$'s. Then $x y^0 z = a^{p - |y|} b^p$ has fewer $a$'s than $b$'s, so it is not in $L$.

$L = \{ww : w \in \{a, b\}^*\}$. Choose $s = a^p b a^p b = uu$ with $u = a^p b$. The cut lies inside the first block of $a$'s, so $y = a^k$ with $k \ge 1$ and $x y^2 z = a^{p + k} b a^p b$, of length $2p + k + 2$. If $k$ is odd the length is odd, so it is not of the form $vv$. If $k$ is even then $k \ge 2$, and a hypothetical $v$ would have length $p + 1 + k/2 \le p + k$, so $v$ would lie inside the leading block of $a$'s and contain no $b$, while $vv$ contains two $b$'s: contradiction. (A careless choice such as $s = a^{2p}$ fails: the cut $y = aa$ pumps to $a^{2p + 2j} = (a^{p + j})^2$ and always survives.)

$L = \{a^{n^2} : n \ge 0\}$. Choose $w = a^{p^2}$. After pumping once, the length is $p^2 + k$ with $1 \le k \le p$, strictly between $p^2$ and $(p + 1)^2 = p^2 + 2p + 1$, so it is not a perfect square.

$L = \{a^q : q \text{ prime}\}$. Choose a prime $q \ge p$. Pump with $i = q + 1$: the length is $q + k \cdot q = q(1 + k)$ with $k = |y| \ge 1$, which is composite. (This works for every cut.)

Balanced parentheses. Choose $w = (^p )^p$. The cut lies inside the opening parentheses, so pumping down gives more closing than opening ones.

Palindromes. Choose $w = a^p b a^p$. The cut lies inside the first block of $a$'s; pumping up moves the $b$ away from the centre.

$L = \{a^n : n = 2^k\}$. Choose $w = a^{2^m}$ with $2^m > p$; after one pump the length lies strictly between $2^m$ and $2^{m + 1}$.

Languages that look hard but are regular. $\{w \in \{0, 1\}^* : \#01(w) = \#10(w)\}$ (equal numbers of occurrences of the substrings $01$ and $10$) is regular: the occurrences alternate, so the counts are equal iff the string is empty or begins and ends with the same symbol (checked for all strings up to length $14$). Do not be fooled by "equal counts".

Using it together with closure

For languages defined by counts of two symbols, intersect with $a^* b^*$ first (closure properties): if $L$ were regular, $L \cap a^* b^*$ would be regular; it is $\{a^n b^n\}$ for $\#a = \#b$. This is often shorter than the pumping argument.

The lemma is not an "if and only if"

There are non-regular languages that satisfy the pumping condition. Example:

$L = \{a^i b^j c^k : i, j, k \ge 0,\ \text{if } i = 1 \text{ then } j = k\}.$

Every string $w = a^i b^j c^k$ in $L$ with $|w| \ge 3$ can be pumped with $p = 3$ (verified for all strings up to length $9$). The cut always has $x = \varepsilon$: if $i = 0$, let $y$ be the first symbol (the string stays of the form $b^* c^*$); if $i = 1$, let $y = a$ (pumping gives $a^t b^j c^j$ with $t = 0$ or $t \ge 2$, which is in $L$ since $i \ne 1$, and $t = 1$ is $w$ itself); if $i = 2$, let $y = aa$ (the number of $a$'s becomes $0, 2, 4, \ldots$, never $1$); if $i \ge 3$, let $y = a$ (the number of $a$'s stays at least $2$). Yet $L$ is not regular, because $L \cap a b^* c^* = \{a b^j c^j\}$ is not. So: pumping condition holds does not mean regular. The exact characterisation is the Myhill-Nerode theorem (Myhill-Nerode): a language is regular iff it has finitely many classes of equivalent strings. For $\{a^n b^n\}$ the strings $a^0, a^1, a^2, \ldots$ all have different futures, so there are infinitely many classes; in the check, no DFA with $3$ states agrees with $a^n b^n$ on all strings up to length $8$ (all $5832$ machines tried).

Useful consequences for DFAs

Let a DFA have $n$ states.

• $L$ is non-empty iff it accepts a string of length $< n$.
• $L$ is infinite iff it accepts a string of length $\ge n$ and $< 2n$.
• If $L$ is finite and its longest string has length $m$, the pumping lemma holds with $p = m + 1$ (no string is long enough, so the condition is empty): every finite language is regular.

Both tests agree with a direct graph search on 300 random DFAs.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The same idea (a repeated state in a bounded computation) gives the pumping lemma for context-free languages with two pumped parts (pumping lemma for CFLs); the Myhill-Nerode theorem is the exact test that the pumping lemma only approximates (Myhill-Nerode); closure properties shorten many proofs (closure properties).

PYQs

Consider the following two languages over the alphabet {a,
b}:
L1 = { αβα | α ∈ {a, b}+ AND β ∈ {a, b}+ }
L2 = { αβα | α ∈ {a}+ AND β ∈ {a, b}+ }
Which ONE of the following statements is CORRECT?

Let Σ = {a, b, c}. For x ∈ Σ* , and α ∈ Σ, let #α(x) denote
the number of occurrences of α in x. Which one or more of
the following option(s) define(s) regular language(s)?

For Σ = {a,b}, let us consider the regular language L = {x|x
= a 2+3k or x = b 10+12k , k ≥ 0}. Which one of the following
can be a pumping length (the constant guaranteed by the
pumping lemma) for L?

Which of the following language is/are regular
languages?

L1 : {wxwR|w,x ε {a, b}* and |w|, |x| > 0}, wR is the
reverse of string w
L2 : {anbm | m != n and m, n >= 0}
L3 : {apbqcr | p, q, r >= 0}

Let L1 = {w ∈ {0,1}* | w has at least as many occurrences
of (110)'s as (011)'s}. Let L2 = {w ∈ {0,1}*|w has at least
as many occurrences of (000)'s as (111)'s}. Which one of
the following is TRUE?

Which one of the following is TRUE?

Which of the following are regular sets?
I. { anb2m | n ≥ 0, m ≥ 0 }
II. { anbm | n = 2m }
III. { anbm | n ≠ m }
IV. { xcy | x, y ∈ {a, b}* }

Which of the following languages is regular?

If s is a string over (0 + 1)* then let n0(s) denote the
number of 0's in s and n1(s) the number of 1's in s. Which
one of the following languages is not regular?

Consider the following languages.
L1 = {wxyx | w, x, y ε (0 + 1)+}
L2 = {xy | x, y ε(a + b)*, |x| = |y|, x !=y}
Which one of the following is TRUE?

Which of the following is true for the language
{ ap| p is prime} ?

Self-check

Revision card

References