= Solution
Given a finite input word $w$, construct the typed term $\mathbf wq_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^*(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.
Back to article page
