Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 4 / 4I (Automata and Formal Languages)

Run the algorithms for $f(n)$ and $g(n)$ and output their XOR. Closure of computable functions under composition makes $f+g$ computable.

No. Let $X_f=\mathbb{N}$ and let $X_g=K$ be an r.e. undecidable set. Both are r.e., but $X_{f+g}=\mathbb{N}\setminus K$ is not r.e.; otherwise $K$ would be decidable.

No. Context-free languages are not closed under symmetric difference (a standard counterexample is obtained from the two CFLs enforcing respectively equality of the first two and last two blocks in $a^{\ast }{b}^{\ast }{c}^{\ast }$). Transport such a pair through the bijection $\beta$; pointwise addition corresponds exactly to symmetric difference.