= 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
$$
A=\{\varepsilon\}.
$$
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$. Thus
$$
B=\{w0:w\in\mathbb B\},
$$
the set of nonempty binary words ending in $0$.
Back to article page
