Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-4/4h/b/solution
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 4 4H b Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
Let be the undecidable set denoted in the question. The language satisfies the pumping lemma for regular languages with pumping length one. For any nonempty , write with , its first symbol, and the remaining suffix.
If , then for every . Otherwise for some . If the chosen first symbol lies in , pumping it preserves the same final suffix . If , then : pumping down gives , while every positive pump gives and all but its last can be absorbed into . Thus every sufficiently long word has a valid pumping decomposition.
Nevertheless, if were regular language, closure under intersection would makeregular. A finite automaton deciding this unary language would decide whether by running it on , contradicting the halting problem. ThereforeThis is a nonregular language satisfying the pumping lemma.
New to topics? Read the docs here!