2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.