$q_4$ and $q_6$ in \[fig:A\]), whereby an increment of the counter in $\M$ results in a decrement of the counter in $\A$, and vice versa—once the cheat occurs, $\A$ can return to $q_0$ with no penalty, and since the counter in $\M$ is $0$, we are guaranteed that the counter in $\A$ did not decrease since leaving $q_0$, allowing $\A$ to continue the run.

Formally, we construct $\A$ from $\M$ as follows.

-   The alphabet $\Sigma$ of $\A$ consists of $\#$ and the descriptive commands for the counter machine $\M$ : , , , , , and for every line $i$ of $\M$, the commands , , , , and .

-   The initial state $q_0$ is accepting, it has a self transition over $\Sigma\setminus\{\#\}$ and nondeterministic transitions to the states $q_1\ldots q_6$ over $\#$, all with weight $0$.

-   There is a $heaven$ state, which is accepting, and has a self loop over $\Sigma$ with weight $0$.

-   The state $q_1$ is accepting and intuitively allows to accept short segments between consecutive $\#$’s: It has a self transition over $\Sigma\setminus\{\#\}$ and a transition to $heaven$ over $\#$, all with weight $-1$.

-   The state $q_2$ starts the command-checker gadget, 