\rangle} + \sum_{i=1}^{|x|=n} (-1)^{x[i]} {\left(  -\frac{1}{2} {\langle p_3,i-k \rangle} + \frac{1}{2} {\langle p_4,i-k \rangle}  \right)}.$$ Here the first three terms are trivial since (i) $ {\langle p_0,0 \rangle} $ never leaves itself, and, (ii) the values of $ p_1 $ and $ p_2 $ are never changed and the counter value is decreased for each symbol 2 ($ k $ times in total).

In order to verify the last term, we closely look into the step when reading an arbitrary input symbol, say $ w[j] $ ($ 1 \leq j \leq n $). Suppose that $ t \in \{0,\ldots,j-1 \} $ symbols 2 have been read until now. We calculate the final counter values of the configurations with states $ p_3 $ and $ p_4 $ that are created from $ {\langle p_1,-t \rangle} $ in this step.

-   If $ w[j] $ is $ 0 $ or $ 1 $, then the following configurations are created: $$-\frac{1}{2} {\langle p_3,-t+1 \rangle} + \frac{1}{2} {\langle p_4,-t+1 \rangle} \mbox{ or } \frac{1}{2} {\langle p_3,-t+1 \rangle} - \frac{1}{2} {\langle p_4,-t+1 \rangle},$$ respectively. In the remaining part of the computation, $ k-t $ symbols 2 and $ n-j-(k-t) $ symbols 0 or 1 are 