Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 4J / c / Solution

Assume that $L$ is context-free and let $p$ be its pumping length. Apply the pumping lemma for context-free languages toWrite $w=uvxyz$, with $|vxy|\le p$ and $|vy|>0$. The substring $vxy$ meets at most two of the three constant-letter blocks.

If $v$ and $y$ affect only the first block, only the middle block, or only the last block, pumping down immediately makes the final block length differ from the minimum of the first two lengths. If they meet the first and second blocks, pumping down decreases at least one of those block lengths while leaving the final length $p$, again violating the defining minimum.

It remains that they meet the second and third blocks. Let pumping change their lengths by $s$ and $t$, respectively. Pumping down fails unless $s=t$. If $s=t>0$, pumping up gives lengthswhose last entry is not $\min (p,p+s)=p$. Thus some pumping exponent always leaves $L$, contradicting the lemma. Hence