Pumping Lemma for CFL | Sahithyan's Notes

Let $L$ be a CFL. Then $\exists n \in \mathbb{N}$ such that $\forall u \in L$ satisfying $|u| \ge n$ , there exist strings $v, w, x, y, z$ satisfying:

$u = vwxyz$
$|wy| > 0$
$|wxy| \le n$
$\forall m \ge 0$ , $vw^mxy^mz \in L$

Using the Lemma to Prove Non-CFL

To show $L$ is not a CFL, assume $L$ is a CFL and derive a contradiction.

Standard proof structure:

Assume $L$ is a CFL with pumping length $n$ .
Choose a string $u \in L$ with $|u| \ge n$ .
Consider all possible decompositions $u = vwxyz$ satisfying $|wy| > 0$ and $|wxy| \le n$ .
Show that for every such decomposition, some $vw^mxy^mz \notin L$ for some $m \ge 0$ .
Contradiction. $L$ is not a CFL.

Example

Prove $L = \{a^n b^n c^n \mid n \ge 1\}$ is not a CFL.

Solution Reveal Hide

Assume $L$ is a CFL with pumping length $p$ . Choose $u = a^p b^p c^p$ , so $|u| = 3p \ge p$ .

Any decomposition $u = vwxyz$ with $|wxy| \le p$ means $wxy$ spans at most 2 of the 3 symbol types (cannot reach from the $a$ -block to the $c$ -block in $p$ characters).

Case 1: $wxy$ lies entirely in $a^p b^p$ . Pumping increases the count of $a$ s or $b$ s (or both) but not $c$ s. The pumped string has unequal counts.

Case 2: $wxy$ lies entirely in $b^p c^p$ . Pumping increases $b$ s or $c$ s but not $a$ s. Unequal counts.

In all cases, $vw^2xy^2z \notin L$ . Contradiction. $L$ is not a CFL.

Ogden’s Lemma

A generalization of the pumping lemma for CFL. Allows marking “distinguished” positions in $u$ . Guarantees $w$ or $y$ contains at least 1 distinguished position.

Useful when the standard lemma is insufficient to force a contradiction. Every CFL satisfies Ogden’s lemma; it strictly subsumes the pumping lemma.