Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 4H / b

This language is context-free. It is the language of even-length palindromes over $\{a,b\}$, generated by the context-free grammarEvery derivation adds matching outer symbols, and removing the matching first and last symbols gives the converse induction.

This language is not context-free. Suppose it had pumping length $N$, and choose a prime $p>N$. Apply the pumping lemma to $w=0^p{1}^p$. Let $\alpha$ and $\beta$ be the total numbers of zeros and ones in the pumped pieces $v$ and $y$. If $\alpha \ne \beta$, pumping with $i=0$ produces unequal block lengths and leaves the language. If $\alpha =\beta$, then $|vy|>0$ forces $\alpha =\beta =d>0$. Pumping with $i=p+1$ produces equal block lengthswhich are composite. Every possible pumping decomposition fails, proving the equal prime block language is not context-free.

The equations $3m=4l$ and $2n=5k$ are equivalent tofor nonnegative integers $r,s$. Hence the language iswhich is the nested two-pair count language generated byIt is therefore context-free.