Exercises — Pumping lemma for CFLs

The lemma splits a long string as $w=uvxyz$ — five pieces, with two pumped pieces $v$ and $y$.

1. $|vy|\ge 1$ (the two pumped pieces are not both empty).
2. $|vxy|\le p$ (the middle window is bounded by the pumping length).
3. $u{v}^{i}x{y}^{i}z\in L$ for all $i\ge 0$.

The two pieces $v$ and $y$ are pumped with the same exponent $i$ (not independent). Contrast Pumping lemma for regular languages which has one piece $y$ in $x{y}^{i}z$.

(a) In CNF every rule is $A\to BC$ or $A\to a$, so the parse tree is binary. A binary tree of height $h$ has at most $2^h$ leaves, which lets us convert "long string ⇒ many leaves" into "tall tree ⇒ long path" cleanly. (b) The Pigeonhole Principle: a path with more than $b$ variable nodes but only $b$ distinct variables must reuse one variable $A$.

Because the window has width $\le p$, and the three blocks each have length $p$, the window $vxy$ cannot stretch from inside the $a$-block to inside the $c$-block (they are $\ge p$ apart). So $vxy$ touches at most two of the three letter types — the geometric fact that makes the whole proof work.

Assume $L$ is a CFL; let $p$ be its pumping length. Choose $w=a^p{b}^p{c}^p\in L$ with $|w|=3p\ge p$.

Take any split $w=uvxyz$ with $|vy|\ge 1$ and $|vxy|\le p$. Since $|vxy|\le p$, the window spans at most two adjacent blocks, so $vy$ contains at most two of the three letter types (it can never contain both $a$ and $c$).

Pump to $i=2$: $u{v}^{2}x{y}^{2}z$. Since $|vy|\ge 1$, at least one letter type strictly increases, but the untouched type (there is always at least one) keeps count $p$. So the three counts are no longer all equal ⇒ $u{v}^{2}x{y}^{2}z\notin L$. Contradiction. ∴ $L$ is not a CFL. ∎

Assume CFL with pumping length $p$. Choose $w=a^p{b}^p{c}^p$; since $p\le p\le p$, $w\in L$. Write the pump exponent as $t$ to avoid clashing with the language's $i$.

Any split has $|vxy|\le p$, so $vy$ spans at most two adjacent letter types. Two cases cover every split:

• $vy$ omits $c$ (contains only $a$'s and/or $b$'s): pump up, $t=2$. Some $a$- or $b$-count rises above $p$ while $c$-count stays $p$. Then $b\text{-count}>p=c\text{-count}$ or $a\text{-count}>b\text{-count}$ — the ordering $i\le j\le k$ breaks.
• $vy$ omits $a$ (contains only $b$'s and/or $c$'s): pump down, $t=0$. Some $b$- or $c$-count drops below $p$ while $a$-count stays $p$. Then $a\text{-count}=p>$ that smaller count — the ordering breaks.

Every split falls into (at least) one case (if $vy$ spans $a$–$b$ it omits $c$; if $b$–$c$ it omits $a$; if a single type, both cases apply). Contradiction. ∴ not a CFL. ∎

Assume CFL, pumping length $p$. Choose $w=a^{p^2}\in L$ ($|w|=p^2\ge p$).

Any split $w=uvxyz$ has $1\le |vy|\le |vxy|\le p$. Let $d=|vy|$, so $1\le d\le p$. Pump to $i=2$: the new length is $|u{v}^{2}x{y}^{2}z|=p^2+d.$ Since $1\le d\le p$, we have $p^2<p^2+d\le p^2+p<p^2+2p+1=(p+1{)}^2.$ So the new length lies strictly between consecutive squares $p^2$ and $(p+1{)}^2$ — it is not a perfect square. Hence $u{v}^{2}x{y}^{2}z\notin L$. Contradiction. ∴ not a CFL. ∎

Why $0^p{1}^p$ fails: it equals $ww$ with $w=0^{p/2}\dots$? No — actually $0^p{1}^p$ is pumpable while staying in $L$-like form for a naive attempt, and worse, a clever adversary split near the middle can keep it a valid $ww$. The point: a witness with only one $0$-block and one $1$-block gives the adversary room to pump symmetrically. We need a string where the two halves are far apart.

The real proof. Assume CFL, pumping length $p$. 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$, and $|w_0|=4p\ge p$.

Take any split $w_0=uvxyz$ with $|vy|\ge 1$, $|vxy|\le p$. Label the four blocks $B_1=0^p,B_2=1^p,B_3=0^p,B_4=1^p$. Because $|vxy|\le p$, the window sits within a stretch of length $\le p$, so it overlaps at most two adjacent blocks. Pump to $i=2$ (add $|vy|$ symbols) — casework on where the window sits:

• Window in $B_1$–$B_2$ region: the first half grows but the second half ($B_3{B}_4$) is unchanged, so the two halves have different lengths ⇒ result cannot be $ss$ (both halves of $ss$ have equal length $2p$).
• Window in $B_3$–$B_4$ region: symmetric — second half grows, first half fixed.
• Window straddling $B_2$–$B_3$ (the exact middle): even then it lies wholly in the "first-half's $1$-region + second-half's $0$-region," and adding symbols there shifts the midpoint, so the halves no longer split as identical copies.

In every case the halves become unequal in length or content, so $u{v}^{2}x{y}^{2}z\notin L$. Contradiction. ∴ not a CFL. ∎

Assume CFL, pumping length $p$. Choose $w=a^p{b}^{p^2}\in L$ ($|w|=p+p^2\ge p$).

Any split has $|vxy|\le p$. Because the $a$-block has length $p$ and the $b$-block length $p^2\ge p$, the window sits in one of three positions. Let $\alpha =$ number of $a$'s in $vy$ and $\beta =$ number of $b$'s in $vy$, with $\alpha +\beta =|vy|\ge 1$.

Pump to $i=2$: new counts are $a\text{-count}=p+\alpha$, $b\text{-count}=p^2+\beta$. For membership we need $p^2+\beta =(p+\alpha {)}^2=p^2+2\alpha p+{\alpha }^2$, i.e. $\beta =2\alpha p+{\alpha }^2.$

• If $\alpha =0$: need $\beta =0$, but then $|vy|=0$, contradicting $|vy|\ge 1$. So membership fails.
• If $\alpha \ge 1$: then $\beta =2\alpha p+{\alpha }^2\ge 2p$. But $\beta \le |vy|\le |vxy|\le p<2p$. Impossible.

Either way $u{v}^{2}x{y}^{2}z\notin L$. Contradiction. ∴ not a CFL. ∎

Direct. Assume CFL, pumping length $p$. Choose $w=a^p{b}^p{c}^p{d}^p$. Any split has $|vxy|\le p$, so $vy$ touches at most two of the four blocks. Pump $i=2$: at least one touched count rises but at least two untouched blocks keep count $p$, so the four counts are no longer all equal ⇒ $\notin L$. Contradiction. ∎

Slicker (closure). Suppose $L$ were a CFL. CFLs are closed under intersection with regular languages. Intersect with the regular language $a^{\ast }{b}^{\ast }{c}^{\ast }{d}^{\ast }$ (no change), then project... actually the clean statement: if $L$ were context-free, so would be a language we already know isn't. The direct pump above is the safest here — closure shines more in L4.2.

This one is a lesson in what closure can and cannot do.

CFLs are closed under intersection with a regular language, but $\{a^n{b}^n{c}^n\}$ is not itself an intersection of a CFL with a regular language in an obviously helpful way. However, here is the classic closure argument for a related fact:

Let $L_1=\{a^n{b}^n{c}^m:n,m\ge 0\}$ and $L_2=\{a^n{b}^m{c}^m:n,m\ge 0\}$. Both are CFLs (each matches only one pair of blocks — build a grammar per Context-Free Grammars). Their intersection is $L_1\cap L_2=\{a^n{b}^n{c}^n:n\ge 0\}.$ If CFLs were closed under intersection, this would be a CFL. But by L2.1 it is not a CFL. Therefore CFLs are not closed under intersection — and conversely this exhibits $\{a^n{b}^n{c}^n\}$ as an intersection of two CFLs that is not a CFL. ∎

(Moral: closure gives a proof-by-outsourcing, but you still need the pumping lemma somewhere to seed the contradiction — here in L2.1.)

This one IS context-free — a synthesis test of whether you reach for the right tool. $L=\{a^i{b}^i{c}^k\}\cup \{a^i{b}^j{c}^j\}$ is a union of two CFLs, and CFLs are closed under union (Closure properties of CFLs). Grammar: $S\to S_1\mid S_2,S_1\to AC,A\to aAb\mid \epsilon ,C\to cC\mid \epsilon ,$ $S_2\to DB,D\to aD\mid \epsilon ,B\to bBc\mid \epsilon .$ Here $S_1$ generates $a^i{b}^i{c}^k$ and $S_2$ generates $a^i{b}^j{c}^j$. Since a grammar exists, $L$ is context-free. Pumping lemma cannot prove this (it only ever proves not-CFL); you must exhibit a grammar or PDA — see Pushdown Automata. ∎

Assume CFL with pumping length $N$ (call it $N$ to avoid clash with "prime $p$"). Pick a prime $q\ge N$ and take $w=a^q\in L$, $|w|=q\ge N$.

Split $w=uvxyz$ with $d:=|vy|\ge 1$. Then $u{v}^{i}x{y}^{i}z=a^{q+(i-1)d}$ for each $i\ge 0$. Its length is $q+(i-1)d$; we need this to be prime for all $i\ge 0$. Choose $i=q+1$: $\text{length}=q+(q+1-1)d=q+qd=q(1+d).$ Since $d\ge 1$, we have $1+d\ge 2$ and $q\ge 2$, so $q(1+d)$ is a product of two integers each $\ge 2$ — a composite number, not prime. Hence $u{v}^{q+1}x{y}^{q+1}z\notin L$. Contradiction. ∴ not a CFL. ∎

Assume CFL, pumping length $p$. Pick $n$ large enough that $2^n\ge p$ and take $w=a^{2^n}$.

Let $d=|vy|$ with $1\le d\le |vxy|\le p\le 2^n$. Pump to $i=2$: new length $=2^n+d$. We need $2^n+d$ to be a power of two. But $2^n<2^n+d\le 2^n+2^n=2^{n+1}.$ Since $d\ge 1$ the length is strictly greater than $2^n$, and since $d\le 2^n$ it is at most $2^{n+1}$; it equals $2^{n+1}$ only if $d=2^n$, but $d\le p\le 2^n$ forces $d=2^n$ only when $p=2^n$ and the window fills the whole string — impossible since $|vxy|\le p<|w|=2^n$ when we take $n$ large enough that $2^n>p$. So $2^n<2^n+d<2^{n+1}$: strictly between consecutive powers of two ⇒ not a power of two. Hence $\notin L$. Contradiction. ∴ not a CFL. ∎

(Cleanest: choose $n$ with $2^n>p$; then $d\le p<2^n$ gives $2^n<2^n+d<2^{n+1}$ with no equality edge case.)

(a) $p=2^4+1=17$. (b) At most $2^h$ leaves (binary tree of height $h$). (c) We need $2^h\ge 20$. Since $2^4=16<20\le 32=2^5$, the height must satisfy $h\ge 5$. So the longest root-to-leaf path has $\ge 5$ variable nodes (plus the terminal leaf). With only $b=4$ distinct variables available, a path carrying $\ge 5$ variable nodes must reuse one — Pigeonhole Principle: 5 nodes into 4 pigeonholes forces a repeat. That repeated variable is the pumpable loop. ∎