 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/4f/a/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

A language

L

satisfies the context-free pumping lemma if there is an integer

p \geq 1

such that every

z \in L

with

∣ z ∣ \geq p

has a decomposition

z = uv w x y

with

∣ v w x ∣ \leq p, ∣ vx ∣ \geq 1,

and

u v^{i} w x^{i} y \in L for every i \geq 0.

Every context-free language has this property, although the property by itself is not sufficient for context-freeness.

 New to topics? Read the docs here!