Pumping lemma for CFLs: Worked examples — Coding deep dive

The scenario matrix

Every CFL-pumping problem falls into one of these cells. The last column names the example that covers it.

Cell	What makes it this case	Winning move	Example
A. Three-block equality	three letter-blocks must all match ( $a^{n} b^{n} c^{n}$ )	window misses one block; pump $t = 2$	Ex 1
B. Inequality / ordering	counts must satisfy $\leq$ chain	split into pump-up vs pump-down cases	Ex 2
C. Copy / squared structure	string is $w w$ or has a repeated half	clever witness $0^{p} 1^{p} 0^{p} 1^{p}$ ; pump breaks symmetry	Ex 3
D. Arithmetic on a single count	length is a perfect square / prime etc.	pump changes length by a controllable amount	Ex 4
E. Degenerate / boundary inputs	$n = 0$ , empty string, $	w	<p$
F. The trap — $L$ actually IS a CFL	pumping "succeeds"; you must NOT conclude	give a grammar instead	Ex 6
G. Real-world word problem	balanced tags / matched resources	model as language, then pump	Ex 7
H. Exam twist — closure shortcut	pumping directly is messy	intersect with a regular language first	Ex 8

We now clear every cell.

Ex 1 — Cell A: three-block equality

Worked example

$L = {a^{n} b^{n} c^{n} : n \geq 0}$ is not a CFL Forecast: guess — after pumping, which of the three counts fall out of sync?

Assume $L$ is a CFL; get pumping length $p$ . Choose $w = a^{p} b^{p} c^{p}$ , so $∣ w ∣ = 3 p \geq p$ . ✓ Why this step? Three equal blocks is the hardest witness — one window can't touch all three.
Any split has $∣ v x y ∣ \leq p$ . Since the block of $a$ 's and the block of $c$ 's start $\geq p$ symbols apart, the window $v x y$ cannot contain both an $a$ and a $c$ . So $v y$ uses at most two of the three letters. Why this step? The length bound localizes the pump — this is the whole engine of the proof.
Pump to $t = 2$ : $u v^{2} x y^{2} z$ adds $\geq 1$ symbol (since $∣ v y ∣ \geq 1$ ) to at most two letter-types, leaving the third untouched at count $p$ . Why this step? At least one count grows while another stays fixed, so the three counts can no longer all equal $p$ .
Therefore $u v^{2} x y^{2} z \in / L$ for every split — contradiction. $∴ L$ not a CFL. ∎ Why this conclusion? The lemma promised every long string pumps; we exhibited one that can't, so the assumption " $L$ is a CFL" must be false.

Verify (concrete split): say $v = a$ , $y = b$ (window inside the $a$ - $b$ junction). Then $u v^{2} x y^{2} z = a^{p + 1} b^{p + 1} c^{p}$ . Counts $(p + 1, p + 1, p)$ are not all equal ⇒ not in $L$ . ✓ (checked numerically for $p = 4$ ).

Ex 2 — Cell B: inequality / ordering

Worked example

$L = {a^{i} b^{j} c^{k} : i \leq j \leq k}$ is not a CFL Forecast: if the window misses the $c$ 's, do we pump up or down?

Choose $w = a^{p} b^{p} c^{p}$ . Since $p \leq p \leq p$ , $w \in L$ (here the counts are $i = j = k = p$ ). ✓ Why this step? The all-equal witness sits on the tightest boundary of every $\leq$ .
$∣ v x y ∣ \leq p$ ⇒ the window spans at most two adjacent letter-types. Why this step? The three blocks each have length $p$ , so a window of length $\leq p$ cannot reach from the $a$ -block across the whole $b$ -block into the $c$ -block — it can straddle at most one block boundary, hence touches at most two letter-types.
Case (i): $v y$ has no $c$ (only $a$ 's and/or $b$ 's). Pump up ( $t = 2$ ): some earlier count exceeds $p$ while $k$ stays $p$ . We get $i > p$ or $j > p$ with $k = p$ , so $j \leq k$ or $i \leq j$ fails. Why this step? Growing a count before $c$ while $c$ is frozen breaks the $\leq$ chain.
Case (ii): $v y$ has no $a$ (only $b$ 's and/or $c$ 's). Pump down ( $t = 0$ ): remove $\geq 1$ symbol from $b$ or $c$ , so $j < p$ or $k < p$ while $i = p$ . Then $i \leq j$ or $j \leq k$ fails. Why this step? Shrinking a count after $a$ while $a$ is frozen breaks the chain.
Every split lands in case (i) or (ii) (the window can't contain both an $a$ and a $c$ ), so we always win. Contradiction. ∎ Why this conclusion? We beat every possible adversary split (both cases), which is exactly what refuting "every long string pumps" requires.

[!mistake] Don't confuse the pump exponent with a count The pump exponent $t$ (0 or 2) is not the count $i$ of $a$ 's in $a^{i} b^{j} c^{k}$ . We deliberately used the separate letter $t$ so the two never collide.

Verify: Case (i) with $v = a$ : $u v^{2} x y^{2} z = a^{p + 1} b^{p} c^{p}$ needs $p + 1 \leq p$ — false ⇒ out. Case (ii) with $v = c$ : $u v^{0} x y^{0} z = a^{p} b^{p} c^{p - 1}$ needs $p \leq p - 1$ — false ⇒ out. ✓ (checked for $p = 4$ ).

Ex 3 — Cell C: copy / squared structure

Worked example

$L = {w w : w \in {0, 1}^{*}}$ is not a CFL Forecast: why is $0^{p} 1^{p}$ a bad witness but $0^{p} 1^{p} 0^{p} 1^{p}$ a good one?

Choose $w_{0} = 0^{p} 1^{p} 0^{p} 1^{p}$ . This is $ss$ with $s = 0^{p} 1^{p}$ , so $w_{0} \in L$ , $∣ w_{0} ∣ = 4 p \geq p$ . ✓ Why this step? The naive $0^{p} 1^{p}$ pumps happily (e.g. $v = 0, y = 1$ keeps it of form $ss$ ), proving nothing. We need a witness where the two halves can't stay identical.
Label the four blocks $B_{1} = 0^{p}, B_{2} = 1^{p}, B_{3} = 0^{p}, B_{4} = 1^{p}$ . Since $∣ v x y ∣ \leq p$ , the window fits inside at most two adjacent blocks, so it lies entirely in the left half or entirely in the right half (or across one internal boundary), never symmetric across the midpoint. Why this step? To stay in $L$ we'd need the first half to equal the second half; the window's locality prevents a matching change on both sides.
Pump $t = 2$ . Total length becomes $4 p + ∣ v y ∣$ . For the result to be in $L$ it must factor as (some string)(same string), i.e. its length must be even and the two halves identical. Even if $∣ v y ∣$ is even, the content is now asymmetric — the added symbols land only on one side of the midpoint, so the two halves differ. Why this step? $w w$ demands positional identity, and a one-sided edit destroys it.

The figure above draws exactly this witness. The four coloured blocks are $B_{1} \dots B_{4}$ ; the dashed plum line is the midpoint that separates the two halves that $L$ forces to be equal. The shaded orange rectangle is a length- $\leq p$ window $v x y$ sitting entirely inside $B_{2}$ — notice it lives wholly in the left half, so pumping it edits only the left copy while the right copy stays fixed. That asymmetry is precisely why the two halves can no longer match. (If instead the window sat in $B_{3}$ or $B_{4}$ it would edit only the right half — same conclusion by symmetry.)

So $u v^{2} x y^{2} z \in / L$ for every split. Contradiction. ∎ Why this conclusion? Every legal window is trapped on one side of the midpoint, so no split survives — the "every long string pumps" promise fails, so $L$ is not a CFL.

Verify (a concrete split): window in $B_{2}$ , $v = 1$ . Then $u v^{2} x y^{2} z = 0^{p} 1^{p + 1} 0^{p} 1^{p}$ , length $4 p + 1$ — odd, so it can't be $ss$ at all. ⇒ out. ✓ (checked for $p = 3$ ).

Ex 4 — Cell D: arithmetic on a single count

Worked example

$L = {a^{n^{2}} : n \geq 0}$ (perfect-square lengths) is not a CFL Forecast: after pumping once, does the new length land between two consecutive perfect squares?

Choose $w = a^{p^{2}}$ , $∣ w ∣ = p^{2} \geq p$ (for $p \geq 1$ ). ✓ Why this step? A perfect-square length that is itself $p^{2}$ means the next square is a full $2 p + 1$ symbols away — and our pump can add at most $p$ symbols, so we'll be guaranteed to land strictly between two squares. Choosing $w = a^{p^{2}}$ engineers exactly that gap.
Any split $uv x y z$ has $1 \leq ∣ v y ∣ \leq ∣ v x y ∣ \leq p$ . Let $d = ∣ v y ∣$ , so $1 \leq d \leq p$ . Why this step? Pumping $t = 2$ adds exactly $d$ symbols; we only need to control that gap.
Pump $t = 2$ : new length $= p^{2} + d$ . We show $p^{2} < p^{2} + d < (p + 1)^{2}$ .
- Left: $d \geq 1$ ⇒ $p^{2} + d > p^{2}$ . ✓
- Right: $(p + 1)^{2} = p^{2} + 2 p + 1$ , and $d \leq p < 2 p + 1$ ⇒ $p^{2} + d < (p + 1)^{2}$ . ✓ Why this step? A length strictly between consecutive squares is not a perfect square.
So $∣ u v^{2} x y^{2} z ∣$ is not a perfect square ⇒ $\in / L$ , for every split. Contradiction. ∎ Why this conclusion? For any split the pumped length is wedged strictly between $p^{2}$ and $(p + 1)^{2}$ , so no split stays in $L$ — the lemma's promise fails and $L$ is not a CFL.

Verify: for $p = 5$ , $p^{2} = 25$ , next square $36$ . Adding any $d \in [1, 5]$ gives $26 \dots 30$ , none a perfect square. ✓ (checked).

Ex 5 — Cell E: degenerate / boundary inputs

Worked example Where the lemma stays silent (and why that's fine)

Forecast: does the pumping lemma say anything about the empty string $ε$ ?

Take $L = {a^{n} b^{n} c^{n}}$ again (a **non-**CFL). Consider these boundary inputs:

$w = ε$ (the $n = 0$ member $a^{0} b^{0} c^{0}$ ): here $∣ w ∣ = 0 < p$ . The lemma's guarantee only covers strings with $∣ w ∣ \geq p$ , so it makes no claim about $ε$ . Why this step? You cannot derive a contradiction from a string shorter than $p$ — never pick one as your witness.
Any $w$ with $∣ w ∣ < p$ : same — outside the lemma's scope. A common exam error is to "pump" $a^{2} b^{2} c^{2}$ against $p = 100$ ; that string is simply too short to test. Why this step? The lemma is a statement about long strings; short strings are exempt by design.
The pump $t = 0$ on a minimal witness: if you chose $w = a^{p} b^{p} c^{p}$ and remove pieces, you must still ensure $u v^{0} x y^{0} z$ is a legal string to test. It always is (a substring), and here $ux z$ has unequal counts ⇒ out — consistent with Ex 1. Why this step? $t = 0$ is legal ( $t \geq 0$ ); don't forget it as a weapon.

[!recall]- Why can't we use $ε$ as a witness? Because the lemma only guarantees pumpability for $∣ w ∣ \geq p$ ::: $ε$ has length $0 < p$ , so it is outside the promise and gives no contradiction.

Ex 6 — Cell F: the trap (this language IS a CFL)

Worked example

$L = {a^{i} b^{j} c^{k} : i = j or j = k}$ is a CFL — don't try to pump it Forecast: will pumping $a^{p} b^{p} c^{p}$ produce a contradiction? (It won't — see why.)

Suppose you try the pumping lemma with $w = a^{p} b^{p} c^{p}$ (which has $i = j = k$ , so both clauses hold). Any adversary split can be pumped and still land in $L$ : e.g. pumping only $a$ 's can keep $j = k$ true, so the string stays valid. Why this step? The lemma is necessary, not sufficient — passing it proves nothing, and here it genuinely passes.
Correct move: exhibit a grammar using CFGs and closure under union. $L = L_{1} \cup L_{2}$ where $L_{1} = {a^{i} b^{i} c^{k}}$ and $L_{2} = {a^{i} b^{j} c^{j}}$ , each context-free: $S \to S_{1} ∣ S_{2}, S_{1} \to A_{1} C, A_{1} \to a A_{1} b ∣ ε, C \to c C ∣ ε$ $S_{2} \to A B_{2}, A \to a A ∣ ε, B_{2} \to b B_{2} c ∣ ε$ Why this step? CFLs are closed under union, so a union of two CFLs is a CFL.
Conclusion: $L$ is a CFL. Attempting a pumping-lemma "disproof" would fail — a healthy sign you should look for a grammar instead. Why this step? Recognizing when pumping can't work saves you an hour of a doomed proof.

[!mistake] Passing the pumping lemma ≠ context-free The lemma only ever proves non-membership in CFL. To prove membership, build a grammar or a PDA.

Verify: $a^{2} b^{2} c^{5}$ has $i = j = 2$ ⇒ in $L_{1}$ ⇒ in $L$ . $a^{3} b^{2} c^{2}$ has $j = k = 2$ ⇒ in $L_{2}$ ⇒ in $L$ . $a^{1} b^{2} c^{3}$ has neither ⇒ out. ✓ (checked).

Ex 7 — Cell G: real-world word problem

Worked example Balanced triple-tags in a markup toy language

Forecast: an "open–body–close" tag system where body length must equal open count — CFL or not?

A toy renderer accepts documents of the form: $n$ opening marks <, then a body of exactly $n$ characters, then $n$ closing marks >, and the body must be exactly $n$ dots. Formally $L = {<^{n} .^{n} >^{n} : n \geq 0} .$

This is structurally $a^{n} b^{n} c^{n}$ with $a = <$ , $b = .$ , $c = >$ . Why this step? Rename symbols and it's exactly Ex 1 — three interlocked counts.
By the identical argument (choose $w = <^{p} .^{p} >^{p}$ , window misses one block, pump $t = 2$ ), $L$ is not a CFL. Why this step? Three simultaneous equal counts exceed a stack's single-counter reach.
Practical reading: a pushdown automaton (one stack) can match opens to closes, or opens to body, but not all three at once — so no CFG/parser handles this without extra machinery. Why this step? This is why real HTML/XML parsers don't enforce "body length = tag count" in the grammar itself.

Verify: $w = <<..>>$ ( $n = 2$ ) is in $L$ ; pumping a < to get $<<<..>>$ gives counts $(3, 2, 2)$ — not all equal ⇒ out. ✓ (checked for $p = 2$ ).

Ex 8 — Cell H: exam twist (closure shortcut)

Worked example Convicting a language via

intersection with a regular language Forecast: can we reuse the already-proven non-CFL ${a^{n} b^{n} c^{n}}$ instead of pumping from scratch?

The key closure fact: CFLs are closed under intersection **with a regular language** (they are not closed under intersection with each other). We exploit this.

Let $M = {a^{i} b^{j} c^{k} : i = j = k}$ — this is literally ${a^{n} b^{n} c^{n}}$ written with the equality spelled out. Suppose, for contradiction, that $M$ were a CFL.

Intersect $M$ with the regular language $R = a^{*} b^{*} c^{*}$ . Every string of $M$ already has its letters in the order $a$ 's then $b$ 's then $c$ 's, so $M \subseteq R$ and $M \cap R = M = {a^{n} b^{n} c^{n}}$ . Why this step? Intersecting with the regular "well-ordered" filter $R$ leaves $M$ unchanged, so it exposes the exact known non-CFL without altering it.
By the closure property, if $M$ were a CFL then $M \cap R$ would be a CFL too. But $M \cap R = {a^{n} b^{n} c^{n}}$ , which we already proved is not a CFL (Ex 1). Why this step? Closure would force a known non-CFL to be a CFL — an outright contradiction.
Therefore $M$ is not a CFL. No fresh pumping argument was needed — Ex 1 plus closure did the work. Why this conclusion? Assuming $M$ is a CFL collided with a proven fact, so the assumption is false.

[!intuition] When this shortcut pays off If a candidate language becomes a known non-CFL after intersecting with some regular filter (fixing letter order, deleting a letter, etc.), you inherit the non-CFL verdict for free.

[!mnemonic] Closure convictions "Intersect with a regular filter, land on a known non-CFL, and closure does the pumping for you."

Verify: the filter $R = a^{*} b^{*} c^{*}$ accepts the well-ordered $a^{2} b^{2} c^{2}$ (so $M \cap R$ keeps it) and rejects a scramble like ba; and ${a^{n} b^{n} c^{n}}$ fails Ex 1's pump. ✓ (checked).

Recap

Recall Which cell needs a

two-case split, and why? Cell B (inequalities) ::: because the window may miss the $c$ 's (then pump up) or miss the $a$ 's (then pump down) — you must beat both possibilities.

Recall When does the pumping lemma stay silent?

On strings with $∣ w ∣ < p$ , including $ε$ ::: the guarantee only covers long strings, so short/degenerate inputs give no contradiction (Ex 5).

Recall If pumping "succeeds", what have you proved?

Nothing about CFL-ness ::: the lemma is necessary, not sufficient; prove membership with a grammar or PDA instead (Ex 6).

Related: Pumping lemma for CFLs · Chomsky Normal Form · Parse Trees and Derivations · Pigeonhole Principle · Pumping lemma for regular languages