Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 1 / 12J (Automata and Formal Languages)

The upper register index is the largest register number occurring in an instruction of $P$, with value zero if only register $0$ is used. A configuration records the current state and the contents of every register up to that index.

For input $\vec{w}$, let $C(0,M,\vec{w})$ be the initial configuration: the designated initial state, the words of $\vec{w}$ in the input registers, and the empty word in every remaining register. Recursively, if $C(t,M,\vec{w})$ is halting, keep it fixed; otherwise let $C(t+1,M,\vec{w})$ be the unique configuration into which $M$ transforms it. The resulting sequenceis the computation sequence.

Choose an input word $w$ of length at least $n+1$. The final value $f_{M,1}(w)={\chi }_L(w)$ has length at most one. Every symbol initially in register $0$ must either be deleted or transferred elsewhere, and either action begins with a remove instructionNo other instruction can lower the length of register $0$. Consequently at leastsuch remove instructions occur in this computation. Since words of arbitrary length exist, the assertion follows.

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

Consider computations while a terminal block of $b$'s is removed from register $0$. Until that block has disappeared, the available instruction and next state depend on the current state and on the visible $b$, not on the untouched prefix $x$.

Take a block longer than $|Q|$. Record the state after each successive $b$ has been removed. Two records have the same state $q$, by the pigeonhole principle. If the corresponding removed tail lengths are $k\ne \ell$, the same finite instruction sequences work in front of every prefix $x$. Thus there are fixed times $t,t^{\prime }$ such thatfor every word $x$.

Suppose a zero-register machine decided $L=\{a^n{b}^n:n>0\}$, and choose $k\ne \ell$ as in part (d). Take $m\ge \max \{k,\ell \}$ and setThenwhereasPart (d) puts both computations into the identical configuration $(q,x)$. Determinism forces their subsequent computations and outputs to agree, a contradiction. ThereforeThis is the one-register separation for equal block lengths.