2
$\begingroup$

I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special kind of PDA where the stack alphabet consists of two symbols? Can we generalize like so: a k-counter automata is a PDA with k many symbols in the stack alphabet where k>0?

$\endgroup$
3
$\begingroup$

A two-counter automaton has two counters, so two push-downs, each with a single stack symbol (agaun ignoring bottom). Such an automaton is not equavalent to push-down automata.

Any PDA can be shown to be equivalent with a PDA with two different stack symbols, so in itself characterize the context-free languages.

Two-counter automata are much more powerful, they can simulate Turing machines, and hance form the recursively enumarable languages. The special bottom symbol is essential here. In that way the machine is able to do a zero test (i.e., check the contents of the counter is zero). The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...) in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).

$\endgroup$
2
  • 1
    $\begingroup$ Ah, so from what I understand, a k-counter automata requires k many PDAs to simulate it? $\endgroup$
    – ilikecats
    Feb 16 '15 at 1:07
  • 1
    $\begingroup$ Well, to be precise, a single machine with $k$ pushdowns attached. As we reach $\mathrm{RE}$ already for two pushdowns (or two counters) it suffices to have only two of them (rather than $k$). $\endgroup$ Feb 16 '15 at 10:46

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.