 Solution

ID: 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

P

, terminal alphabet

{0, 1}

, and the following productions generates all binary palindromes:

P ⟶ ϵ ∣ 0 ∣ 1 ∣ 0 P 0 ∣ 1 P 1.

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

 New to topics? Read the docs here!