Pumping lemma for CFLs: Visual walkthrough — Coding deep dive

Step 1 — What a parse tree looks like

A parse tree records how a string was built: start at the top circle $S$ , apply rules, and read the bottom row of leaves left-to-right to get your string.

WHAT the figure shows: a tiny parse tree whose leaves spell a b b a. WHY we care: the whole lemma is a statement about the shape of this tree, not about algebra. Get comfortable reading trees now. PICTURE: follow the lavender circles (variables) down to the coral leaves (terminals). Reading the bottom row gives the string.

Step 2 — Why we force the tree to be binary (Chomsky Normal Form)

WHAT we did: we agreed to only look at grammars where circles split in two. WHY this tool and not another? Because a tree where every internal node has two children is a binary tree, and binary trees have a clean counting law (next step). A messy grammar could split into 5 children or loop $A \to A$ ; CNF bans all of that. Any CFG can be rewritten into CNF without changing the language, so we lose nothing.

PICTURE: left = a "wild" node with three children (forbidden). Right = the CNF version: every split is a clean fork of two.

Step 3 — The counting law: short trees can only hold few leaves

WHAT we did: bounded how many letters a short tree can spell. WHY the power of two? Because CNF forces two children per split — "two children" is literally the " $\times 2$ " in $2^{h}$ . This is why we insisted on binary trees in Step 2.

PICTURE: a full binary tree drawn level by level: $1, 2, 4, 8$ nodes. The bottom row has $2^{h}$ leaves — count them.

Step 4 — Choosing the magic length $p$

WHAT we did: picked a threshold length, one bigger than $2^{b}$ . WHY exactly $2^{b} + 1$ ? Look back at Step 3's law $leaves \leq 2^{h}$ . If a string is strictly longer than $2^{b}$ , then a tree of height $\leq b$ cannot produce it — because such a tree caps out at $2^{b}$ leaves. Adding the $+ 1$ turns " $\geq p$ " into the strict " $> 2^{b}$ " we need. So any $w$ with $∣ w ∣ \geq p$ is guaranteed to force a tall tree.

PICTURE: a number line. Everything at or right of $p = 2^{b} + 1$ (mint zone) is "too long for a short tree." The butter dot at $2^{b}$ is the last length a height- $b$ tree can reach.

Step 5 — Pigeonhole forces a variable to repeat

Because $∣ w ∣ \geq p$ (Step 4), the tree's height is $> b$ , so its tallest path passes through at least $b + 1$ variable circles. But only $b$ different names exist. Pigeonhole ⇒ two circles on that path wear the same name $A$ .

WHAT we did: located a variable $A$ appearing twice on one vertical path. WHY this is the whole game: a variable that reappears below itself is a loop in disguise — the grammar re-entered the same state, so whatever it did once it can do again.

PICTURE: a tall path highlighted; the two circles labelled $A$ (both lavender, glowing) are the repeated pigeon. We always pick the two lowest such $A$ 's — remember that choice, it pays off in Step 7.

Step 6 — Naming the five pieces $u, v, x, y, z$

Now cut the string using those two $A$ 's.

Reading the tree:

The upper $A$ eventually produces the middle chunk $v x y$ . Everything to its left is $u$ ; to its right is $z$ .
Inside that, the lower $A$ produces just $x$ .
The material the upper $A$ grew that the lower one did not — that is $v$ (on the left branch) and $y$ (on the right branch).

WHAT we did: turned "a repeated variable" into five concrete substrings. WHY two extra pieces $v$ and $y$ (unlike the single piece in the regular lemma)? Because a CNF split $A \to B C$ branches both left and right. The lower $A$ hangs off one side; the other side's leaves become $v$ or $y$ . Branching in two directions is exactly why CFLs pump on two sides at once.

PICTURE: the same tall tree, now colour-blocked: $u$ and $z$ in slate at the far edges, $v$ and $y$ in coral hugging the middle, $x$ in mint at the bottom under the lower $A$ .

Step 7 — Why the loop pumps (repeat the subtree)

Plugging back through the top $S \Rightarrow^{*} u A z$ : $S \Rightarrow^{*} u v^{i} x y^{i} z \in L for every i \geq 0.$

WHAT we did: replaced the lower $A$ 's subtree with a copy of the upper $A$ 's subtree, as many times as we like. Setting $i = 0$ instead deletes the loop (use the lower subtree directly). WHY it stays in $L$ : every splice uses only legal rules that were already in the grammar — we are just re-running an allowed derivation.

PICTURE: three panels. $i = 0$ (loop cut out, just $x$ ), $i = 1$ (original, $v x y$ ), $i = 2$ (loop nested twice, $v v x y y$ ). Watch $v$ pile up on the left and $y$ on the right, symmetrically.

Step 8 — Why the two guarantee-conditions hold

WHAT we did: proved the two "small print" promises of the lemma. WHY "lowest pair" mattered: any repeat would give a loop, but only the lowest repeat keeps the middle window short enough to satisfy $∣ v x y ∣ \leq p$ — that is the entire reason we specified "lowest" back in Step 5.

PICTURE: left — the strictly-bigger upper subtree with the extra $v, y$ leaves circled (proves $∣ v y ∣ \geq 1$ ). Right — the "lowest pair" keeping the middle subtree short and squat (proves $∣ v x y ∣ \leq p$ ).

Step 9 — The degenerate cases (never leave a gap)

Short strings ( $∣ w ∣ < p$ ): the lemma says nothing and promises nothing. No tall tree is forced, no repeat, no split. That's fine — the lemma only speaks about $∣ w ∣ \geq p$ .
$v = ε$ but $y \neq = ε$ (the left growth is empty, right growth isn't): still legal, since Condition 1 only needs $∣ v y ∣ \geq 1$ , not both nonempty. Pumping then piles up only on the right. The mirror case ( $y = ε$ , $v \neq = ε$ ) piles up only on the left.
$x = ε$ (lower $A$ produces nothing between the pumps): allowed; $v$ and $y$ then sit adjacent. The loop still works.
$u = ε$ or $z = ε$ (the repeat sits at the very edge): allowed; nothing outside the middle window, but pumping is unaffected.

WHAT we did: confirmed the derivation survives every empty-piece scenario. WHY it matters for using the lemma: when you run the adversary game, the adversary may hand you any of these; your chosen $i$ must break membership for all of them (see the parent note's $a^{n} b^{n} c^{n}$ proof).

PICTURE: four mini-trees, one per degenerate case, each still showing a valid loop. Nothing breaks.

The one-picture summary

This single figure compresses the whole chain: long string ⇒ tall binary tree ⇒ pigeonhole repeat of $A$ ⇒ split $uv x y z$ ⇒ pump the loop.

Recall Feynman retelling — say it back in plain words

Imagine every valid string is drawn as a family tree of splitting circles, and every circle always has two kids. A short tree can only ever spell out a short string — its bottom row runs out of room. So the moment your string is long enough (longer than $2^{b}$ leaves, where $b$ is how many circle-names you own), the tree is forced to grow tall. Tall means some vertical path visits more circles than you have names, so — pigeonhole — one name shows up twice on that path. That double-visit is a loop: the grammar came back to the same circle, so it can run that stretch again and again. Running it grows letters on the left ( $v$ ) and right ( $y$ ) at the same time, with an untouched core $x$ in the middle and fixed ends $u$ and $z$ . That's the whole $uv x y z$ . Because the loop is legal, you can repeat it any number of times (or zero) and still land in the language. To prove a language is not context-free, you flip it around: find one long string where no loop can survive being repeated, and the whole story collapses into a contradiction.

One line ::: Long string forces a tall binary tree, pigeonhole repeats a variable, the repeat is a pumpable loop that grows $v$ and $y$ together.

Recall Quick self-check

Why must there be two pumped pieces, not one? ::: A CNF split $A \to B C$ branches both left and right, so the loop grows material on both sides — $v$ on the left, $y$ on the right. Why $p = 2^{b} + 1$ and not $2^{b}$ ? ::: The $+ 1$ makes $∣ w ∣ \geq p$ imply the strict $∣ w ∣ > 2^{b}$ , which forces height $> b$ so a variable must repeat. Which choice guarantees $∣ v x y ∣ \leq p$ ? ::: Picking the two lowest repeated occurrences of $A$ , keeping the middle subtree short.

See also: Pushdown Automata, Closure properties of CFLs.