Solution

ID: 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 homomorphism
Then closure under inverse homomorphism and intersection of a context-free language with a regular language would make
context-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!