3
$\begingroup$

Consider an extension of finite-state machines that utilizes a finite set $C$ of counters. Let's call them counter automata. Before execution, each counter $c\in C$ is set to zero. Every transition, aside from reading a character (possibly $\epsilon$), performs a counter operation – it either increments or decrements some counter $c$ by one ($c{+}{+}$ and $c{-}{-}$, respectively). Decrementation of a counter is forbidden if the counter is set to zero. Acceptation is done by accepting states, regardless of counter values. Alphabet is of finite size.

Is every context-free language accepted by a counter automaton? Is every language accepted by counter automata a context-sensitive one?

Please note that counter automata differ from counter machines (at least I can't prove that they're equal). The counters mustn't go below zero and there's basically only JUMP NOT ZERO operation available, aside from INCREMENT and DECREMENT.

I think that we can simulate a finite stack using a finite number of counters. We'd remember both the top and the bottom of the stack in states, and counter values would represent symbols on stack. Unfortunately, this stack would have fixed size. I don't know how to continue.

$\endgroup$
  • $\begingroup$ I can't get LaTeX to work :( $\endgroup$ – Janet Drais Jun 18 '16 at 19:59
  • $\begingroup$ Welcome! We have a short guide to LaTeX on the site. Alternatively, if your problem was that $c++$ looks awful ($c++$), it's because LaTeX puts spaces around the plus signs, as you'd expect to see in "$1+2$". To stop it doing that, you need to put braces around the plusses: $c{+}{+}$ ($c{+}{+}$). $\endgroup$ – David Richerby Jun 18 '16 at 20:25
4
$\begingroup$

These counter automata have power incomparable to pushdown automata. In particular they are strictly weaker than counter machines as they have no proper zero test (if zero then .. else ..). Technically they are known as partially blind multicounter. Blind as they cannot act on zero, partially as they store only nonnegative numbers, and block when a counter is less than zero. As a language accepting device they are equivalent to Petri nets. They have been studied for instance by Greibach.

$\endgroup$
  • $\begingroup$ FYI, Georg Zetzsche studies these and other automata in his PhD thesis. In particular, it's interesting that blindness does indeed change the power. $\endgroup$ – Raphael Jun 18 '16 at 21:56

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.