Can a det. $k$-counter machine ($k \geq 2$) be simulated by a det. $k'$-counter machine using non-$\epsilon$-moves followed by $\epsilon$-moves?

Question

I have a question concerning deterministic $k$-counter machines, for $k \geq 2$. Recall that in this context, the determinism is expressed by the fact that the machine can never face a choice between either reading a (proper) symbol of its input alphabet, or reading $\varepsilon$ (i.e., the empty symbol). In other words, let's call a transition involving a non-empty input symbol a "regular transition", and a transition involving $\varepsilon$ an "$\varepsilon$-transition" (like as usual). The determinism condition simply states that the machine never has to choose between a regular or an $\varepsilon$-transition (cf. Book by Hopcroft, Motwani and Ullman 2001, p.349).

In this context, I would like to know if every $k$-counter machine $\mathcal{C}$, for $k \geq 2$, can be simulated by a $k'$-counter machine $\mathcal{C}'$ which, on every input, always uses regular transitions followed by $\epsilon$-transitions?

For the case of stacks machines with a stack alphabet larger than or equal to the input alphabet, I believe that the answer is yes. The idea would be to consider a machine $\mathcal{C}'$ which always begins by copying its input on a designated stack – using only regular transitions – and then works exclusively by considering this stack as a kind of input tape – using only $\epsilon$-transitions.

What about the case of $k$-counter machines ($k \geq 2$)?

Answer 1

No, that is not possible. There are languages accepted with $\varepsilon$-transitions that cannot be accepted if $\varepsilon$-transitions can only occur at the end (even if you allow nondeterminism in exchange for restricted $\varepsilon$ usage).

Take, for example, the language $L=\{w\#w \mid w\in\{a,b\}^*\}$. As a recursively enumerable language, it can be accepted by a determinisic 2-counter machine. A simple counting argument shows that this requires interspersed $\varepsilon$-transitions:

If $\varepsilon$-transitions occur only at the end, then after reading a word $w\#$, the machine can only produce counter values whose size is linear in $|w|$. In particular, there is a polynomial $p$ so that after reading a word $w\#$, the machine can be in at most $p(|w|)$ configurations. Thus, since there are exponentially many words of a given length, the machine can be tricked into accepting a word $w\#w'$ with $w'\ne w$.