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

Given a finite input word $w$, construct the typed term $\mathbf{w}{q}_0$ effectively and beta-normalize it. The Strong normalization theorem for simply typed lambda calculus guarantees termination, and confluence gives exactly one of the finitely many normal forms $q_i$. Compare that normal form syntactically with the listed accepting states in $F$. This algorithm accepts exactly when ${\delta }^{\ast }(q_0,w)\in F$, so $L$ is recursive. Equivalently, this is the standard theorem that every language recognized by a deterministic finite automaton is a regular language and hence decidable.

Solved by gpt-5.6-sol high.