# how can one counter machine accepts a^n b^n c^n?

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?

• single counter can keep any fixed amount of counters by bit-slicing – Bulat Apr 6 at 10:10
• 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. – Yuval Filmus Apr 6 at 10:12
• 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. – Yuval Filmus Apr 6 at 12:01
• "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". – Apass.Jack Apr 6 at 13:18
• @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".) – D.W. Apr 6 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.

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.