Past exam of the computer science course of the University of Oxford / 2015 / Concurrency / 1 / d / ii

In the displayed network, the first $k$ cells retain values and cell $k+1$ is still in its initial $\mathrm{Cell}$ state. It accepts only a value in $T$, so it cannot accept the incoming sentinel value. For $k=0$ the first cell blocks the external sentinel value; for $0<k<n$ a stored cell blocks while trying to pass it to an empty neighbour. ThusTo handle shorter inputs, add an empty-cell branch $l.end\to u.end\to \mathrm{STOP}$ to the initial state. An empty cell then terminates the downward scan and immediately returns an empty sequence. Earlier occupied cells append their retained values exactly as before; later cells need not participate. This works for every $0\le k\le n$, because the occupied prefix of the chain alone produces the required output. For $k=n$, the original sentinel-only tail still supplies the empty suffix. Every cell receives the same modification.