<p>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).</p>

<p>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:</p>

<p>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$.</p>

CC BY-SA 4.0
2018-08-23T22:06:29.597Z
2018-08-23T22:11:31.503Z
2018-08-23T22:11:31.503Z
Georg Zetzsche
<p>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).</p>

<p>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?</p>

<p>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.</p>

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

<automata-theory><counter-automata>
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?
Jay Cab
# 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?

(Asked by: username_0 on 2018-08-23)

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$)?

**Tags:** automata-theory, counter-automata


---

## 1 answers

### Answer by username_1 on 2018-08-23. Score: 4 | Accepted answer

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$.


---

