Past exam of the mathematics course of the University of Cambridge 2018 ii Paper 1 4G b i Solution 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.