Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-1/4g/b/i/solution
Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 1 4G b i Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
This language is not context-free. Suppose it were, and define the homomorphismThen closure under inverse homomorphism and intersection of a context-free language with a regular language would makecontext-free. The equality holds because the midpoint of a square with four nonempty alternating runs must lie between its second and third runs.
Apply the pumping lemma for context-free languages to . A pumpable window of length at most meets at most two adjacent blocks. Pumping changes at least one block but cannot reach its equal-count partner two blocks away, so either the counts or the counts cease to agree. This contradiction proves the claim.
New to topics? Read the docs here!