cheating. We show that if it goes to $q_3..q_6$, it must return to $q_0$ before the next $\#$, while decreasing the value of $\A$’s counter, which can be done only $n$ times until the run stops.

If it goes to $q_3$, it must return to $q_0$ upon some , as it cannot continue the run on $\#$. Yet, as there is no cheating, it returns to $q_0$ when $x=0$, which implies that $\A$’s counter has the same value as when entering $q_3$, and due to the $-1$ weight of the transition to $q_0$, it returns to $q_0$ while decreasing the value of $\A$’s counter by $1$. An analogous argument follows if it goes to $q_5$.

If it goes to $q_4$, it must return to $q_0$ upon some , as it cannot continue the run on $\#$. Yet, as there is no cheating, it returns to $q_0$ while the value of $x$ is indeed strictly positive, which implies that the value of $\A$’s counter is smaller than the value it had when entering $q_4$, and therefore due to the $0$-weight transition to $q_0$, it returns to $q_0$ with a smaller value of $\A$’s counter. An analogous argument follows if it goes 