Which languages are recognized by one-counter machines?

Problem Detail: 

Counter machines with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation. However, I have not seen a formal analysis of which languages can be recognized by a one-counter machine. Are these languages equivalent to the context-free languages (perhaps by some clever construction relating them to PDAs), or are they an entirely different class of languages?

Asked By : templatetypedef

Answered By : Vor

A one counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). Languages recognized by one counter automata form a proper subset of the context free languages.

For example a 1-counter automata can recognize the language $\{a^nb^n\}$ which is not regular, but cannot recognize the language $\{a^nb^ma^mb^n\}$ which is context free and can be recognized by a 2-counter automata, too.

If k-DCA is a deterministic k-counter automata, and k-NCA is a nondeterministic k-counter automata, then we have the following proper inclusions:

DFA (regular languages) $\subset$ 1-DCA $\subset$ 2-DCA

1-DCA $\subset$ 1-NCA

If we don't allow $\epsilon$ transitions (switch to real time) then k-DCA $\subset$ k'-DCA for k < k'.

Just for completion: there are languages that are context free but cannot be recgnized by counter automatas (k-DCA with k $\geq$ 2) (for example $\{ww^R\}$), and languages recognized by counter automatas that are not context free (for example $\{a^nb^nc^n\}$). A counter automata (in particular a two counter automata) can be Turing complete only if its input and output are properly encoded (see Wikipedia entry for details).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7574