OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 4F / a / Solution

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.

Solved by gpt-5.6-sol high.

 Ancestors (11)