Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 10 / a / ii / Solution

Use start symbol $S$ and an auxiliary symbol $A$ in the context-free grammarThe symbol $A$ generates exactly $\{0,1{\}}^{\ast }$, so every generated string has the three explicitly displayed ones. Conversely, any string with at least three ones can be split at any three of them as $u_{0}1u_{1}1u_{2}1u_3$, and each $u_j$ can be generated by $A$. This proves both inclusions. For example,by taking the four $A$ substrings to be $00$, $0$, $1$, and $0$ respectively.