It is mentioned in Which languages are recognized by one-counter machines? that one counter machine can accept $\{a^n b^n c^n\mid n\geq 0\}$. Can someone please explain how this is done?

  • $\begingroup$ single counter can keep any fixed amount of counters by bit-slicing $\endgroup$ – Bulat Apr 6 '19 at 10:10
  • $\begingroup$ According to the linked question, one-counter machines accept a subset of the context-free languages. In particular, they don’t accept non-context-free languages. $\endgroup$ – Yuval Filmus Apr 6 '19 at 10:12
  • $\begingroup$ The answer states that $a^nb^nc^n$ can be accepted by a counter machine; that machine would have to use more than one counter. $\endgroup$ – Yuval Filmus Apr 6 '19 at 12:01
  • 3
    $\begingroup$ "One counter machine" is ambiguous. As "one-counter machine", it means a counter machine that has one counter. As "one counter-machine", it means a counter machine that has one or more counters. Please edit your question to clarify. "one counter machine" should be avoided. Use either "a one-counter machine" or "a counter machine". Or use either "a one-counter automaton" or "a counter automaton". $\endgroup$ – John L. Apr 6 '19 at 13:18
  • 1
    $\begingroup$ @Bulat, no, that's actually not possible, because in counter machines, the only operations allowed on the counter are "increment", "decrement", and "compare to zero", so you can't implement bit-slicing. (There is no "extract the least significant bit" or "divide by zero".) $\endgroup$ – D.W. Apr 6 '19 at 16:47

Be careful where the hyphens are! One counter-machine can recognize $a^n b^n c^n$, but a one-counter machine cannot.

From the answer you linked to:

Languages recognized by one[-]counter automata form a proper subset of the context free languages.

(There's a proof for this, but it's long and boring, so I'm going to leave it out; you can find it online if you're interested.)

Since $a^n b^n c^n$ is not context-free, it cannot be recognized by a one-counter automaton.

It can, however, be recognized by a two-counter machine (a machine with two counters). The basic structure goes something like this:

  • When you see an $a$, increment $X$, increment $Y$
  • When you see a $b$, decrement $X$
  • When you see a $c$, decrement $Y$
  • Accept iff the letters are in the right order (a trivial state machine), AND $X = 0$, AND $Y = 0$

This is "one counter-machine" (in the sense that it's a single machine using counters). But you need at least two counters to do it.


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.