Pumping lemmas and nonmembership proofs
Goals and the quantifier game
Use necessary pumping properties to disprove regularity or context-freeness. The pumping length belongs to the assumed language; it is not a value chosen after examining a convenient split. Both lemmas below are one-way necessary conditions. Showing that one string pumps, or even establishing the lemma's condition, is not by itself a proof that a language belongs to the class.
1. Regular pumping lemma
If L is regular, there exists p≥1 such that every w∈L with |w|≥p has a decomposition w=xyz satisfying |xy|≤p, |y|≥1 and xy^i z∈L for every integer i≥0. The order is: ∃p, ∀long w, ∃valid split, ∀i. Repeated states among the first p+1 states on a DFA path explain the loop y; removing it gives i=0 and repeating it gives larger i.
To refute regularity, assume a pumping length p, choose w depending on p, then defeat every valid split by choosing some i (which may depend on that split). You do not get to choose y for the opponent. A single bad split is insufficient because the lemma promises only one good split.
Worked proof for L={a^n b^n:n≥0}: take w=a^p b^p. Any valid split has y=a^k with 1≤k≤p because |xy|≤p. Set i=0. Then xz=a^(p−k)b^p has unequal counts, so lies outside L. Every split fails and the assumed regularity is contradicted. Choosing w=ε would be invalid because the lemma only constrains strings of length at least p.
Second worked proof: L={a^(n²):n≥0}. Take w=a^(p²). Any valid y has length k with 1≤k≤p. Pump i=2, giving length p²+k. Since p²<p²+k≤p²+p<(p+1)², that length is not a square. Thus L is nonregular. The inequality handles all possible k, not just a selected split.
2. Context-free pumping lemma
If L is context-free, there exists p≥1 such that every w∈L with |w|≥p can be written uvxyz with |vxy|≤p, |vy|≥1 and uv^i x y^i z∈L for every integer i≥0. Both v and y pump together using the same i. One may be empty, but not both. The bounded window is vxy, not the whole prefix uvxy. A repeated variable on a sufficiently long parse-tree path permits repeating nested derivations, yielding two pumped pieces.
To disprove context-freeness, choose a long word for each hypothetical p, consider every allowed five-part decomposition, and find an exponent making the pumped word leave L. Failing the regular lemma proves only nonregularity; a PDA can still recognize the language.
3. Complete non-CFL proof for three equal blocks
Let L={a^n b^n c^n:n≥0}. Choose w=a^p b^p c^p. Any window vxy of length at most p cannot contain both an a and a c: such a window would contain all p b symbols plus an a and a c, needing length at least p+2. Thus v and y together contain symbols from at most two adjacent blocks.
Pump down with i=0, deleting v and y. At least one symbol is deleted because |vy|≥1. At least one of the three symbol counts remains exactly p because the window misses an entire symbol type; at least one count becomes less than p. Deletion preserves the abc* block order, but the three counts cannot all remain equal. Hence uxz∉L for every valid split, contradicting the CFL lemma. This proof covers windows inside a block, crossing a boundary and empty v or y without assuming both are nonempty.
4. Combining closure with pumping
For K={w over {a,b,c}: #a(w)=#b(w)=#c(w)}, intersect with regular abc*. The result is exactly the three-block non-CFL above. If K were a CFL, closure under intersection with a regular language would make this result a CFL. Therefore K is not context-free. The regular filter makes the pumping proof easier while preserving the contradiction direction.
Checklist
Name the assumed class; write its quantifiers; choose w∈L with enough length; keep the split arbitrary; obey its length restrictions; specify i; show the result is outside L. Never conclude that a failed proof attempt establishes membership.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. In a regular pumping contradiction, who must handle the choice of valid split?
A. Choose one convenient split B. Show failure for every valid split C. Ignore |xy|≤p D. Choose p after choosing y
Answer: B
A: The lemma may use a different split.
B: Every possible promised split must be defeated.
C: This restriction is essential to locating y.
D: The pumping length comes first.
P02. For a^p b^p, regular pumping forces y to be:
A. a^k with 1≤k≤p B. b^k with k≥1 C. ε D. A string necessarily crossing the a/b boundary
Answer: A
A: The first p positions contain only a.
B: The bound prevents reaching b.
C: The lemma forbids empty y.
D: The window ends within the a block.
P03. The CFL pumping lemma requires:
A. Both v and y nonempty B. Only v pumps C. |vxy|≤p and |vy|≥1 D. |uvxy|≤p
Answer: C
A: One of v,y may be empty.
B: Both pump with the same exponent.
C: These are the correct window and nonemptiness constraints.
D: The bounded window excludes u.
P04. Why can a length-p window in a^p b^p c^p not contain both a and c?
A. a and c are equal symbols B. It would require at least p+2 positions C. The word has no b D. The pumping length must be zero
Answer: B
A: They are distinct symbols.
B: All p b symbols lie between the chosen a and c.
C: There are exactly p b symbols.
D: p is at least one.
P05. A proof that a language is not regular establishes:
A. It is not context-free B. It is undecidable C. No finite automaton recognizes it D. No PDA recognizes it
Answer: C
A: Some nonregular languages are CFLs.
B: a^n b^n is decidable.
C: This follows from the definition of regular languages.
D: A PDA recognizes a^n b^n.
P06. In the square-length proof, why is p²+k not square for 1≤k≤p?
A. It is always odd B. It lies strictly between p² and (p+1)² C. All large numbers are nonsquares D. Pumping changes the alphabet
Answer: B
A: Its parity varies.
B: There is no square between consecutive squares.
C: Arbitrarily large squares exist.
D: The alphabet remains unary.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Theory of Computation syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in