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?
$\begingroup$
$\endgroup$
2
asked Dec 24, 2012 at 0:20
-
3$\begingroup$ This book: books.google.co.uk/books/about/… by Jean Berstel goes into quite a lot of depth about one-counter languages and other subsets of context-free languages, but, it tends to be very difficult to actually track down a copy of it. $\endgroup$– Sam JonesCommented Dec 24, 2012 at 18:17
-
1$\begingroup$ @SamJones Indeed the famous book Transductions and Context-free Languages by Jean Berstel has gone out of print. The author has made available an electronic version of the most important chapters of the book. www-igm.univ-mlv.fr/~berstel/LivreTransductions/… $\endgroup$– Hendrik JanCommented Oct 4, 2016 at 17:03
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
10
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).
-
$\begingroup$ questions: (1) languages recognized by counter automatas that are not context free you mean not regular? (2) there is a hierarchy for DCA? Why? Aren't they all Turing equivalent (when $k\ge 2$). $\endgroup$ Commented Dec 24, 2012 at 11:23
-
$\begingroup$ (1) no I mean "that are not context free" (just pick a properly encoded context sensitive language that can be recognized by a k > 1 counter machine) (2) you are right, the hierarchy refers to real time DCA (I corrected the answer) $\endgroup$– VorCommented Dec 24, 2012 at 14:00
-
$\begingroup$ I seem to remember that there are differences between counters that are unbounded in both directions, and such that "bottom out" at zero? $\endgroup$– RaphaelCommented Jul 27, 2017 at 18:33
-
$\begingroup$ @Vor "Languages recognized by one counter automata form a proper subset of the context free languages. " - what does it mean? Please give one example. $\endgroup$– S. M.Commented Oct 15, 2021 at 15:46
-
$\begingroup$ @Punia: as said in the answer: $L = a^n b^m a^m b^n \in CF$, but a one counter automata cannot recognize $L$ $\endgroup$– VorCommented Oct 15, 2021 at 21:16
$\begingroup$
$\endgroup$
1
Counter automata were much studied in the ancient formal language past, in the context of AFA and AFL theory (abstract families of automata & languages) by US and French teams (Ginsberg, Greibach, ... , Nivat, Berstel, ...)
Counter automata are typically defined as finite state automata equipped with external memory, consisting of a natural number (or several if you have more than one counter). This number can be incremented, decremented, and (usually) tested for zero. A computation starts with zero and is only accepted when the counter is zero at the end, comparable to the pushdown empty stack acceptance.
If such a machine has at least two such counters then it is equivalent to a Turing machine, even in the deterministic case. The proof of this fact is by Minsky and can be found in the wikipedia article you linked. The model is of course related to the register machine mentioned in the same wikipedia page. The coding-problems mentioned in the wikipedia article are not important in this setting here as we consider automata with an input tape (after all we have to read an input string) whereas wikipedia on this page only assume counters.
This counter automaton can be seen as a special type of pda, having only one stack symbol, and a bottom-of-stack (that is never moved). This enables the automaton to test whether the counter/stack is zero, and act accordingly.
There are in fact three types of counter automata. So combine results wisely or you end up with contradictions (as happened me in the past). All three types are (strictly) included in the context-free languages for one-counter.
The type above stores an integer (or a natural number, that doesn't matter) and can test its contents beiing zero. Blind counter automata store an integer but cannot test for zero. They can expicitly count below zero though. Partially blind counter automata cannot test for zero, but store an natural number. If the machine tries to go below zero it halts without accepting. This is a natural storage type to model Petri nets. It also is ralated to the PDA, now with a single stack symbol without the special bottom marker (and hence the problem of testing for zero: we just get stuck when popping the last stack element). Sometimes the names of the families defined by the respactive counter models are OCL, ROCL and 1-BLIND.
All these families have been studied, they all are (but I am rusty in my AFA/AFL theory) principal full trios (=rational cones) which means they are closed under (inverse) morphisms and intersection with regular languages, and can be obtained using these operations starting with a single language. For the largest family OCL (with zero test) you can start with the language $(Dc)^*$ where $D = \{ w\in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$ is the "two sided Dyck language on on pair of brackets" (in terminology fitting the subject). There is important intuition related to this language. Symbols $a$ and $b$ reflect popping and pushing, $c$ is the zero test.
As an example of relevant research, Latteux etal have a nontrivial paper "The Family of One-Counter Languages is Closed Under Quotient" (which is actually about ROCL).
answered Dec 24, 2012 at 22:14
-
$\begingroup$ My question is 2 counter machine is equivalent to Turing machine. But $WW^r$ is accepted by Turing machine but not by 2 counter machine. So how could we say 2 counter machine is equivalent to Turing machine? $\endgroup$ Commented Jun 8, 2022 at 22:39