Exam Prep — Pumping Lemma

FIRST DECISION — Read this before writing anything

Can the proof be finished, or not? This determines your entire answer and your max score.

CAN finish Every valid split leads to a contradiction	CAN'T finish At least one valid split survives all pumping
Your answer: Enumerate all possible splits. For each, find an i that breaks membership. Write “Contradiction for all splits, so L is not regular. □”	Your answer: Identify the surviving split. Show xyⁱz ∈ L for all i ≥ 0. Explain why this word choice fails and what word would work instead.
Full marks available (3–5 pts)	Full marks available (4 pts). But if you wrongly try to finish it → max 2/4.

How to detect: Look at the first p characters of w. If y can consist of two different symbols whose counts are linked in the language condition (e.g. b and c where the condition is c_a+c_b=c_c), pumping may preserve the balance → suspect CAN'T finish. If the first p characters are all one symbol, or all cases break the condition → likely CAN finish.

All Past Exam Instances

Exam	Q#	Language	Word given	Finish?	Points
Endterm 23–24	Q5	L = {w ∈ {a,b,c}* \| starts with a, c_a+c_b = c_c}	w = (ac)(b)^p(c)^p	CAN'T	4
Resit 23–24	Q4	L = {aⁿb^m \| 0 ≤ n ≤ m}	w = a^⌈p/2⌉b^⌈p/2⌉	CAN	5
Endterm 24–25	Q4	L = {aⁿ \| n is prime}	w = a^q (smallest prime > p)	CAN	3
Resit 24–25	Q4	L = {a^mbⁿa^q \| m·q ≥ n}	w = ab^pa^p	CAN	3

Pattern: 3 out of 4 exams = CAN finish. 1 out of 4 = CAN'T finish.

The CAN'T case appeared on the endterm (not the resit). The CAN'T case was worth the most points (4 pts) and had the harshest penalty for getting it wrong: max 2/4 if you failed to recognize the word was bad. Points range from 3–5 across exams.

The Pumping Lemma (cheatsheet)

If L is regular, then there exists a pumping length p such that:

For all w ∈ L with |w| ≥ p, there exists a split w = xyz where:

|xy| ≤ p — x and y are within the first p characters
|y| ≥ 1 — y is nonempty
xyⁱz ∈ L for all i ≥ 0 — pumping preserves membership

Contrapositive (what proofs use): If no such p exists → L is not regular.

Exam Format

The exam gives you:

A language L (claimed non-regular)
The beginning of a proof by contradiction: “Suppose L is regular, let p be the pumping length, consider w = [specific word]”
Your job: FINISH the proof, OR explain why this particular word choice CAN’T work

You do not choose the word. The setup is done. You write the punchline.

Grading Rubrics (all 4 exams)

Endterm 23–24 Q5 (4 pts) — CAN'T FINISH

L = {w ∈ {a,b,c}* | starts with a, c_a+c_b=c_c}. Word: w = (ac)(b)^p(c)^p

1 pt	Give a split. Write down explicit x, y, z (e.g. x = a, y = cb, z = b^p−1c^p).
1 pt	Give the split without a contradiction. The split must be one where pumping doesn’t break membership.
1 pt	Explain why the equality holds for any i. Show c_a(xyⁱz) + c_b(xyⁱz) = c_c(xyⁱz) for all i ≥ 0.
1 pt	Explain why the word starts with a for any i. Verify xyⁱz still begins with a for all i ≥ 0.

If you wrongly tried to finish the proof instead:

1 pt: For listing all splits
1 pt: For a contradiction in a split where one exists

Max 2/4 if you miss that the proof can’t be finished. Recognizing the failed word is worth double.

Resit 23–24 Q4 (5 pts) — CAN FINISH

L = {aⁿb^m | 0 ≤ n ≤ m}. Word: w = a^⌈p/2⌉b^⌈p/2⌉

1 pt	For giving at least one group of splits (e.g. all splits where y is only a’s).
1 pt	For all groups of splits (y = only a’s, y = a’s and b’s, y = only b’s).
1 pt	Contradiction where y = only a’s (i > 1 causes too many a’s).
1 pt	Contradiction where y = a’s and b’s (i > 1 causes wrong form, not ab).
1 pt	Contradiction where y = only b’s (i = 0 causes too few b’s).

Endterm 24–25 Q4 (3 pts) — CAN FINISH

L = {aⁿ | n is prime}. Word: w = a^q (smallest prime > p)

1 pt	For giving the correct group of splits (y = a^β with β > 0).
1 pt	For trying to find an i which makes the word not in the language.
1 pt	For a correct i (i = q+1 gives length q(1+β), which is composite).

Resit 24–25 Q4 (3 pts) — CAN FINISH

L = {a^mbⁿa^q | m·q ≥ n}. Word: w = ab^pa^p

1 pt	For giving the correct groups of splits (two cases: x is non-empty vs empty).
1 pt	Correct i and explanation when x is not empty (y = b^β, pump i=2: too many b’s).
1 pt	Correct i and explanation when x is empty (y = ab^α, pump i=0: m=0 so m·q=0 < n).

The Mechanic (step by step)

Step 1 — What must y consist of?

|xy| ≤ p forces xy into the first p characters of w.
|y| ≥ 1 means y is nonempty.

Therefore y consists entirely of whatever symbols appear in the first p positions of w. Enumerate all possible compositions of y.

Example: if w = a^pb^p, the first p characters are all a’s, so y = a^k for some k ≥ 1. Only one case.
If w = ab^pc^p, the first p characters are a, b, b, …, b — so y could be a^k, a^jb^k, or b^k. Multiple cases to check.

Step 2 — For each possible y, try pumping

For each case of y, compute xyⁱz and find an i that breaks membership in L.

Best values to try:

i = 0: removes y (string gets shorter)
i = 2: adds one copy of y (string gets longer)
i = p+1 or i = q+1: adds many copies (useful for prime/divisibility arguments)

Step 3 — Does pumping break ALL valid splits?

CAN finish — for every valid split (every possible y), you found an i that breaks membership.

Write out each case, show the contradiction for each. Proof complete. □

CAN’T finish — there exists some valid split where pumping preserves membership for all i.

Identify that split. Show xyⁱz ∈ L for all i. Explain why this word choice fails.

The exam trap

The “CAN’T finish” case is the trap. Most students assume every pumping lemma question ends with a contradiction. But if the exam gives you a bad word choice, one surviving split is enough to make the proof unfixable. You must recognize it, name the split, and explain why it survives.

Worked Example — CAN finish (Resit 24–25 Q4)

L = {a^mbⁿa^q | m·q ≥ n}, Σ = {a, b}

Word given: w = ab^pa^p (so m=1, n=p, q=p, and 1·p = p ≥ p ✓)

Step 1 — What must y be? First p characters of w = ab p a p are: a, b, b, \dots, b (1 ‘a’ then p-1 ‘b’s). Two possible compositions: Case 1: y = b β (pure b’s) Split: x = ab α, y = b β, z = b p-α-β a p . With α \geq 0, β \geq 1, α + β \leq p - 1. Pump with i = 2: xy 2 z = ab p+β a p . Check: m\cdotq = 1\cdotp = p < p+β = n. Not in L. ✓ Case 2: y = ab α (starts with a) Split: x = ε, y = ab α, z = b p-α a p . With 0 \leq α < p. Pump with i = 0: xz = b p-α a p = a 0 b p-α a p . Check: m\cdotq = 0\cdotp = 0 < p-α = n. Not in L. ✓ Both cases give contradictions. Proof complete. □

CAN finish. Every valid split leads to a contradiction when pumped.

Worked Example — CAN finish (Endterm 24–25 Q4)

L = {aⁿ | n is prime}, Σ = {a}

Word given: w = a^q where q is the smallest prime > p.

Step 1 — What must y be? Unary alphabet \to only one possibility: y = a k for some 1 \leq k \leq p. Step 2 — Pump and check xy i z = a q+(i-1)k . Need to find i where q + (i-1)k is not prime . Take i = q + 1: length = q + q\cdotk = q(1+k). Since k \geq 1, we have 1+k \geq 2. Since q \geq 3 (prime > p \geq 1), q(1+k) is a product of two factors both \geq 2 \to composite. Not in L. ✓ Only one case for y, and it gives a contradiction. Proof complete. □

CAN finish. Pump with i = q+1. Length becomes q(1+k), which is composite.

Worked Example — CAN’T finish (Endterm 23–24 Q5)

L = {w ∈ {a,b,c}* | w starts with a and c_a(w) + c_b(w) = c_c(w)}

Word given: w = acb^pc^p

Verify w \in L Starts with a ✓. Counts: c a = 1, c b = p, c c = p+1. Check: 1 + p = p+1 ✓ Step 1 — What must y be? First p characters of acb p c p : a, c, b, b, \dots, b. So |xy| \leq p means y is within “acbb\dotsb”. Possible compositions of y include: pure b’s, strings containing c and b, strings containing a, c, and b. Step 2 — Try the split x = a, y = cb This is valid: |xy| = 3 \leq p (for p \geq 3), |y| = 2 \geq 1. Pumped string: xy i z = a(cb) i b p-1 c p c a = 1 c b = i + (p - 1) c c = i + p c a + c b = 1 + i + p - 1 = i + p = c c ✓ for ALL i Starts with a ✓ for all i. So xy i z \in L for every i \geq 0.

Why it fails: y = cb adds one b and one c simultaneously. The condition c_a + c_b = c_c stays balanced no matter how many copies of “cb” you pump in or out. One surviving split is enough — the proof cannot be finished.

CAN'T finish. The split x=a, y=cb survives all pumping — adding copies of “cb” preserves the balance c_a + c_b = c_c.

A better word choice would force y into only one symbol type. For example w = ab^pc^p+1, where the first p characters are all in {a, b} — then pumping y can only change the b-count, breaking the balance.

Worked Example — CAN finish (Resit 23–24 Q4)

L = {aⁿb^m | 0 ≤ n ≤ m}, Σ = {a, b}

Word given: w = a^⌈p/2⌉b^⌈p/2⌉ (note: n = m = ⌈p/2⌉, so 0 ≤ n ≤ m ✓)

Step 1 — What must y be? First p characters of w: a ⌈p/2⌉ followed by b ⌊p/2⌋ . Three possible compositions for y: Case 1: y = a β (only a’s, β > 0) Split: x = a α, y = a β, z = a p/2 - α - β b p/2 . Pump with i = 2: a p/2 + β b p/2 . Now n = p/2 + β > p/2 = m. Not in L (n > m). ✓ Case 2: y = a α b β (mix of a’s and b’s, both \geq 1) Pump with i = 2: xy 2 z = a ... b ... a α b ... . The string is not of the form a*b* (a’s appear after b’s). Not in L. ✓ Case 3: y = b β (only b’s, β > 0) Split: x = a p/2 b α, y = b β, z = b p/2 - α - β . Pump with i = 0: a p/2 b p/2 - β . Now m = p/2 - β < p/2 = n. Not in L (n > m). ✓ All three cases give contradictions. Proof complete. □

CAN finish. This is the most involved exam instance with 3 separate split groups (5 pts total). Each group needs its own contradiction argument.

Practice Problems

Q1 — Classic

L = {aⁿbⁿ | n ≥ 0}. Word: w = a^pb^p. Can you finish?

Solution

Yes. y = a^k (since |xy| ≤ p, y is all a’s). Pump with i=2: a^p+kb^p. Since k ≥ 1, p+k > p, so the number of a’s exceeds the number of b’s. Not in L. ✓

Q2 — Doubles

L = {ww | w ∈ {a,b}*}. Word: w = a^pba^pb. Can you finish?

Solution

Yes. y = a^k (first half only, since |xy| ≤ p means y is within the initial a^p block). Pump with i=0: a^p−kba^pb. The first half is shorter than the second half — can’t be of form ww. (More precisely: |xy⁰z| = 2p+2−k which is even only if k is even, but even then the two halves differ.) ✓

Q3 — Unequal (tricky)

L = {a^mbⁿ | m ≠ n}. Word: w = a^pb^p+p!. Can you finish?

Solution

Yes. y = a^k. Pump with i = p!/k + 1: number of a’s = p + (p!/k)·k = p + p!. Total = a^p+p!b^p+p!. Equal! Not in L.

(p!/k is an integer because 1 ≤ k ≤ p, so k divides p!.) ✓

Q4 — Matching ends

L = {aⁿb^mcⁿ | n, m ≥ 0}. Word: w = a^pc^p. Can you finish?

Solution

Yes. y = a^k. Pump with i=0: a^p−kc^p. Now the a-count is p−k and the c-count is still p. Since m=0 (no b’s), we need equal a’s and c’s: p−k ≠ p. Not in L. ✓