Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 1 / 4G / b / i / Solution

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^p{b}^p{c}^p{d}^p$. A pumpable window of length at most $p$ 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 $a,c$ counts or the $b,d$ counts cease to agree. This contradiction proves the claim.