Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 120 / 3 / f / Solution

For $a\in \{0,1\}$ define a typed transition term $D_a:\sigma \to \sigma$ by a nested Boolean choice:Here a Church Boolean acts as an if-then-else operator. The assumed behavior of $e{q}_{\sigma }$ gives $D_a{q}_i{\equiv }_{\beta }{q}_{\delta (q_i,a)}$.

For $w=a_1\cdots a_k$, putand use $ϵ=\lambda x.x$. Induction on the word length gives