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

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.

The equations force $m=4r$, $n=3r$, $k=5s$, and $l=2s$. Hence the language isIt is context-free; one explicit context-free grammar is

This language is not context-free. Let $p$ be a proposed pumping length and choose $n$ with $3^n\ge p$. In any pumping decomposition of the unary word $a^{3^n}$, pumping once more increases its length by an integer $d$ with $1\le d\le p$. 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.