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 / i / Solution

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.