Pumping Lemma for Context-Free Languages

The pumping lemma for context-free languages gives a necessary condition on every CFL. It is used to prove that languages such as $\{a^n b^n c^n\}$ and $\{ ww \}$ are not context-free. The decomposition has five pieces $uvxyz$ with constraints that reflect a repeated path in a CNF parse tree.

If $L$ is context-free, there exists $p \ge 1$ such that every $w \in L$ with $|w| \ge p$ can be written $w = u v x y z$ with:

$\forall p$, $\exists w \in L$ with $|w|\ge p$, $\forall$ decompositions obeying (1)-(2), $\exists k$ with $u v^k x y^k z \notin L$.

In a CNF parse tree for a long string, a long path repeats a variable $A$. The upper $A$ yields $vAy$ and the lower yields $x$, giving $A \Rightarrow^* v A y$ and $A \Rightarrow^* x$, so the yield pumps as $v^k x y^k$.

To show $L$ not CFL, sometimes easier: if $L$ were CFL then $L \cap R$ would be CFL for regular $R$; pick $R$ so that $L \cap R$ is a known non-CFL (often $a^* b^* c^*$).

No decision procedure inside the lemma; it is a proof tool. Membership remains decidable for CFLs even when the language class boundary is shown by pumping.

Take a grammar in CNF with $m = |V|$ variables and set $p = 2^m$. A CNF parse tree whose longest root-to-leaf path has $h$ edges yields at most $2^{h-1}$ terminals, so a string of length $\ge 2^m$ has a path with at least $m+1$ edges, hence at least $m+1$ variable nodes. Among the lowest $m+1$ variables on that path two are equal (pigeonhole). The subtree of the upper copy has height at most $m+1$, so its yield $vxy$ has length at most $2^m = p$; that is condition (1). In CNF the upper copy uses a rule $A \to BC$, and the lower copy lies under only one of $B$, $C$, so the other child contributes a nonempty string to $v$ or $y$; that is condition (2). Sipser states the same lemma for any grammar with $p = b^{|V|+1}$, where $b$ is an upper bound at least 2 on all RHS lengths, for example $b=\max(2,\max\{\lvert\alpha\rvert:A\to\alpha\})$.

Both come from the same repeated variable's upper and lower yields; you cannot pump only one side independently in the basic lemma (Ogden's lemma strengthens control).

Let $w = a^p b^p c^p$. Since $|vxy| \le p$, the window $vxy$ cannot touch both the $a$-block and the $c$-block (the $b$-block of length $p$ lies between them). Two cases:

Either way some $k \in \{0, 2\}$ leaves the language. A proof that treats only the case "$vxy$ inside one block" is incomplete.

Intersect with the regular language $0^*1^*0^*1^*$: the result is $\{0^i 1^j 0^i 1^j\}$. Pump $w = 0^p 1^p 0^p 1^p$. The window $vxy$ has length $\le p$, so it meets at most two adjacent blocks. If it lies in the first half, pumping down changes the first $0$-block or the first $1$-block but not its partner in the second half; symmetrically for the second half; if it straddles the middle ($1^p$ then $0^p$), pumping down shortens the first $1$-block or the second $0$-block alone. All cases break the pattern, so $\{ww\}$ is not context-free. The complement of $\{ww\}$ and $\{ww^R\}$ are both context-free, which is a standard trap.

Every context-free language over a one-letter alphabet is regular (a consequence of Parikh's theorem), so for unary languages the regular pumping lemma or a gap argument suffices. For $\{a^{n^2}\}$ take $w = a^{p^2}$: pumping once gives length between $p^2 + 1$ and $p^2 + p < (p+1)^2$, not a square. For $\{a^{n!}\}$ the gaps between consecutive factorials eventually exceed any fixed $|vy|$. The same gap argument works for primes: $\{a^q \mid q \text{ prime}\}$ is not context-free.

$\{a^n b^n\}$ is a CFL and satisfies the lemma with $p = 2$: for $w = a^n b^n$, $n \ge 1$, take $u = a^{n-1}$, $v = a$, $x = \varepsilon$, $y = b$, $z = b^{n-1}$. Then $uv^kxy^kz = a^{n-1+k} b^{n-1+k}$ for every $k$. The window sits on the $a$/$b$ boundary, which is exactly where the grammar $S \to aSb$ loops.

$L = \{a^i b^j c^k d^l \mid i = 0 \text{ or } j = k = l\}$ is not context-free, yet it satisfies the pumping lemma with $p = 1$. If $w$ has $i = 0$, pump the first letter: the string stays in $b^*c^*d^*$, which lies in $L$. If $i \ge 1$, pump a single $a$: the $b, c, d$ counts are untouched, and pumping down to $i = 0$ still lands in $L$. Ogden's lemma (mark at least $p$ positions; $vxy$ contains at most $p$ marked and $vy$ at least one marked) handles it: mark the $b$'s, $c$'s and $d$'s of $ab^pc^pd^p$. Since the lemma is only necessary, "it pumps" never proves a language context-free.

The pattern to remember: one stack can match nested pairs (like brackets) but not crossing pairs ($a$ with $c$ and $b$ with $d$ in $a\,b\,c\,d$ order) or three-way equalities.

Choosing $w$ where $vxy$ can sit on the boundary without a case analysis fails. Always case-split on which blocks $vxy$ intersects.

Common misconceptions.