= Solution
Choose a language $L\subseteq\{0,1\}^*$ that is not recursively enumerable; such a language exists because there are uncountably many languages but only countably many algorithms. Form $\widehat L$ as in part (d), which satisfies the pumping lemma.
If a grammar generated $\widehat L$, enumerate its terminal derivations and retain precisely words of the form $2v$ with $v\in\{0,1\}^*$. Since such a word contains only one separator,
$$
2v\in\widehat L\quad\Longleftrightarrow\quad v\in L.
$$
This would enumerate $L$, a contradiction. Hence $\widehat L$ is the required language.
Back to article page
