Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 4F (Automata & Formal Languages)

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$.

Use the same program as $N$, replacing only its first line by a test for a final $1$: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$. This is the characteristic function of $\{w1:w\in \mathbb{B}\}$.

Rename the old halt state $q_H$ as a nonhalting state $q_F$, including every occurrence of $q_H$ in the original program, and introduce a new halt state $q_H$. Attach the following output-flipping routine:Because the original machine computes a characteristic function, it reaches $q_F$ with register $0$ containing exactly $0$ or $1$. The routine tests that symbol, removes it, and appends its complement. It therefore halts with $1-{\chi }_X(w)={\chi }_{\mathbb{B}\setminus X}(w)$.