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

Take pumping length $p=1$. If a nonempty word $w\in \{0,1{\}}^{\ast }$, pump its first symbol; every pumped word remains in $\{0,1{\}}^{\ast }$. Otherwise write $w=u2v$ with $v\in L$. If $u\ne \epsilon$, pump the first symbol of $u$, leaving a word of the same form. If $u=\epsilon$, pump the initial $2$: deleting it leaves $v\in \{0,1{\}}^{\ast }$, while retaining one or more copies lets the last pumped $2$ serve as the separator. Thus every required pumped word belongs to $\hat{L}$.

Solved by gpt-5.6-sol high.