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
