Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 4F / a / Solution

The instruction $-(0,p,q)$ goes to $p$ if register $0$ is empty; otherwise it deletes the final letter and goes to $q$.

For $M$, an empty input goes directly from $q_S$ to $q_1$, where a $1$ is appended. On a nonempty input, state $q_0$ deletes every letter; once the register is empty it goes to $q_2$ and appends $0$. Hence

For $N$, the initial instruction tests whether the final letter is $0$. If it is, state $q_3$ deletes the entire word and then goes to $q_1$, producing $1$. Otherwise state $q_0$ deletes the entire word and goes to $q_2$, producing $0$. Thusthe set of nonempty binary words ending in $0$.