 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-3/4f/b/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Use the same program as

N

, replacing only its first line by a test for a final

1

q_{S} q_{0} q_{1} q_{2} q_{3} q_{H} \mapsto ?_{1} (0, q_{3}, q_{0}) \mapsto - (0, q_{2}, q_{0}) \mapsto +_{1} (0, q_{H}) \mapsto +_{0} (0, q_{H}) \mapsto - (0, q_{1}, q_{3}) \mapsto ?_{ε} (0, q_{H}, q_{H}) .

If the input ends in

1

, the

q_{3}

loop erases it and eventually appends output

1

. Every other input, including the empty word, follows the

q_{0}

loop and produces

0

{w 1 : w \in B}

 New to topics? Read the docs here!