# Context-free and context-sensitive grammars in FSM with counters

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.

• I can't get LaTeX to work :( Commented Jun 18, 2016 at 19:59
• 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{+}{+}$). Commented Jun 18, 2016 at 20:25