Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-1/12j/c/solution
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 1 12J c Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
The finite control first rejects the empty word. While the next input symbol is , remove it from register and append one marker to register . On seeing the first , enter a second phase. For every removed from register , remove one marker from register ; reject if a marker is unavailable or if an is encountered in this phase. Accept exactly when both registers become empty simultaneously.
The first phase stores precisely the number of 's, and the second compares it with the number of 's. Register is the only scratch register, so the construction is a one-register-machine computation in the question's terminology. Therefore
New to topics? Read the docs here!