Pumping Lemma for Context-Free Languages

Prove a language is not context-free by pumping uvxyz.

The idea

Theorem (Pumping lemma for context-free languages).

If $L$ is context-free, there is a number $p$, the pumping length, such that every $s \in L$ with $|s| \ge p$ can be written $s = uvxyz$ with $|vy| \ge 1, \qquad |vxy| \le p, \qquad uv^{i}xy^{i}z \in L \ \text{ for every } i \ge 0.$

For regular languages the repetition came from a state recurring on a run through a machine; here it comes from a variable recurring on a path through a parse tree. A grammar has finitely many variables, and a long string forces a tall tree, so on some root-to-leaf path a variable $R$ appears twice. The upper occurrence derives a substring $vxy$; the lower occurrence, nested inside it, derives $x$; and $v$ and $y$ are the material between them on the left and right.

Since both occurrences are the same variable, either subtree may replace the other. Substituting the upper subtree for the lower inserts one more copy of $v$ and of $y$, and repeating this gives every $uv^{i}xy^{i}z$; substituting the lower for the upper deletes both, giving $i = 0$. The two pieces pump together because they flank one repeated variable.

The side conditions carry the applications: $|vy| \ge 1$ guarantees that pumping changes the string, and $|vxy| \le p$ confines the pumped material to a window of width $p$, so it cannot reach two far-apart parts of $s$ at once. Like the regular version, the lemma is a necessary condition only, used in the contrapositive: to prove $L$ is not context-free, choose $s$ and show that every split obeying the conditions pumps out of $L$.

Ways to work on it

Not sure where to start? Take the ten-question placement test.