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

A context-free grammar with start symbol $P$, terminal alphabet $\{0,1\}$, and the following productions generates all binary palindromes:Each production preserves the palindrome property: it either supplies a central string of length zero or one, or wraps the same symbol around a shorter palindrome. This proves soundness by structural induction on the parse tree.

Conversely, any palindrome of length at least two has equal first and last symbols. Remove them to obtain a shorter palindrome, apply mathematical induction on length, and then use the corresponding wrapping production. The three base cases are $ϵ$, $0$, and $1$, proving completeness.

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.