Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 4H b Solution Created 2026-09-24 Updated 2026-10-05
Let be the diagonal halting set, which is undecidable. The pumping argument below actually holds for every subset ; nonregularity needs the stated convention, or at least a set of exponents whose unary language is nonregular.
The pumping lemma for regular languages holds with pumping length one. For an accepted nonempty word, pump its first symbol. A word containing only s remains in even if that symbol is deleted. If there is a zero and a nonempty prefix before its last zero, pumping the first symbol leaves the last zero and its following ones unchanged. If the word is , pumping its initial zero produces ; this is accepted for , and for it belongs to . In every case the pumped substring is nonempty and lies in the first position.
If were a regular language, closure under intersection would makeregular. A finite-state automaton for this intersection would decide membership of in the diagonal halting set by reading , a contradiction. Thus satisfies the pumping lemma but is not regular, under the usual meaning of . If were arbitrary, the printed conclusion would be false, for example for .