Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/4g/b/iii/solution
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 1 4G b iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
This language is not context-free. Let be a proposed pumping length and choose with . In any pumping decomposition of the unary word , pumping once more increases its length by an integer with . Butso the pumped length is not a power of three, contrary to the pumping lemma for context-free languages. This is also an instance of the fact that a unary context-free language is regular, whereas the powers of three are not ultimately periodic.
New to topics? Read the docs here!