Foundations — Pumping lemma for CFLs

This page assumes you have read the parent Pumping Lemma for CFLs note and got stuck on the notation. Here we build every symbol from the ground up, in an order where each idea leans only on the ones before it. Two symbols the parent leans on heavily — the pumping length $p$ and the variable count $b$ — are only named here; both are fully defined in Section 5 once we have the tree picture to explain them.

1. Alphabet, symbol, string — the raw material

Picture it as beads on a wire: each bead is a symbol, the wire read left-to-right is the string.

Figure s01 — what it shows: the string $aabbb$ drawn as five coloured beads on a horizontal wire, with its length $|w|=5$ called out. It defines string and length visually so "counting beads" becomes literal.

Why we need this: the pumping lemma constantly says things like "$|w|\ge p$" (the string is at least $p$ beads long — we define the pumping length $p$ in Section 5) and "$|vy|\ge 1$" (at least one bead among these pieces). Every one of those is just counting beads.

2. Concatenation and the pieces $u,v,x,y,z$

When the parent note writes $w=uvxyz$, it is saying: cut the string $w$ into five consecutive pieces named $u,v,x,y,z$ and glue them back — nothing is added or lost, they are just labels for five stretches of the same wire.

Figure s02 — what it shows: the wire cut into five coloured blocks $u,v,x,y,z$ in order, with the two pump pieces $v$ and $y$ flagged by arrows. It defines the five-piece split and marks which pieces get spun.

3. Language, and "context-free"

Picture a big bag; only the allowed strings are dropped inside. "$w\in L$" means the string $w$ is in the bag; "$w\notin L$" means it is not.

See Context-Free Grammars for the full machinery. A context-free language is any language some CFG can generate.

4. Derivation arrows $\Rightarrow$ and ${\Rightarrow }^{\ast }$

Why the topic needs it: the loop is written $A{\Rightarrow }^{\ast }vAy$, i.e. "starting from $A$, after several steps you reach a string that still contains $A$, with $v$ on its left and $y$ on its right." That is a picture of a variable reproducing itself with extra material around it — the spinnable engine.

5. Parse trees — turning a derivation into a picture

Figure s03 — what it shows: a parse tree with root $S$, the outer pieces $u,z$, then the same variable $A$ appearing twice on one downward path, with $v,x,y$ below. It pictures the repeated-variable loop that pumping exploits.

Picture doubling: 1 root, up to 2 at the next level, 4, 8, … so height $h$ reaches at most $2^h$ leaves.

Figure s04 — what it shows: three levels of a binary tree with node counts $1,2,4$ labelled per level, illustrating the doubling that gives "at most $2^h$ leaves at height $h$". It justifies why long strings force tall trees.

Why the topic needs it: "Long string ($|w|\ge p$) $\Rightarrow$ more than $2^b$ leaves $\Rightarrow$ tall tree $\Rightarrow$ a variable must repeat" is the entire skeleton, and it rides on this doubling bound.

6. Chomsky Normal Form — why we tidy the grammar first

Why it matters here: "$A\to BC$" gives exactly two children, so the parse tree becomes binary — that is what unlocks the clean $2^h$ leaf bound in Section 5, and it also guarantees the upper subtree is strictly bigger than the lower one (giving $|vy|\ge 1$).

7. The Pigeonhole Principle — why a repeat is forced

8. Supporting cast (used but not central)

Prerequisite map

The diagram below renders (in any Mermaid-aware Obsidian view) as a flowchart whose boxes are the foundations of Sections 1–7 and whose arrows mean "you need the lower idea before the higher one makes sense." Read it bottom-up, following arrows into the final "Pumping Lemma" box; it is literally the reading order of this page. Trace one path at a time: raw strings feed grammars, grammars draw parse trees, CNF makes those trees binary so the doubling bound bites, and pigeonhole then forces the repeat that is the pumping lemma. If any box looks unfamiliar, jump back to its section before reading the parent proof.

If your viewer does not render Mermaid, read the arrow list as plain prerequisites: alphabet/string → pieces and → language → grammar → derivation arrows → parse trees; separately grammar → Chomsky Normal Form → binary-tree height/leaves; then parse trees and CNF both feed binary-tree height/leaves → pigeonhole → Pumping Lemma, with pieces and pushdown automata also feeding the final lemma.

Equipment checklist

Test yourself — each line is prompt ::: answer.