Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 12J / e / Solution

Choose a language $L\subseteq \{0,1{\}}^{\ast }$ that is not recursively enumerable; such a language exists because there are uncountably many languages but only countably many algorithms. Form $\hat{L}$ as in part (d), which satisfies the pumping lemma.

If a grammar generated $\hat{L}$, enumerate its terminal derivations and retain precisely words of the form $2v$ with $v\in \{0,1{\}}^{\ast }$. Since such a word contains only one separator,This would enumerate $L$, a contradiction. Hence $\hat{L}$ is the required language.