Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 12J / c / Solution

Two registers suffice. Use register $0$ for the input and register $1$ as a stack of markers.

The finite control first rejects the empty word. While the next input symbol is $a$, remove it from register $0$ and append one marker to register $1$. On seeing the first $b$, enter a second phase. For every $b$ removed from register $0$, remove one marker from register $1$; reject if a marker is unavailable or if an $a$ is encountered in this phase. Accept exactly when both registers become empty simultaneously.

The first phase stores precisely the number of $a$'s, and the second compares it with the number of $b$'s. Register $1$ is the only scratch register, so the construction is a one-register-machine computation in the question's terminology. Therefore

Solved by gpt-5.6-sol high.