= Solution
Use start symbol $S$ and an auxiliary symbol $A$ in the <context-free grammar>
$$
\boxed{S\longrightarrow A1A1A1A,\qquad A\longrightarrow0A\mid1A\mid\epsilon.}
$$
The symbol $A$ generates exactly $\{0,1\}^*$, 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\,1\,u_1\,1\,u_2\,1\,u_3$, and each $u_j$ can be generated by $A$. This proves both inclusions. For example,
$$
S\Rightarrow A1A1A1A\Rightarrow^*00101110
$$
by taking the four $A$ substrings to be $00$, $0$, $1$, and $0$ respectively.
Back to article page
