How can a one-counter machine accept $a^n b^n c^n$?

Question

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

Answer 1

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.

Answer 2

Dexter Kozen mentions, in his textbook Automata and Computability, that a counter automaton has a two-way read-only input head and counter. The counters store a non negative integer. In each step the automaton can independently increment, decrement or test for zero its counter and can move the input head in either direction. Here is the exact definition he uses:

A $k$-counter automaton is a machine equipped with a two-way read-only input head and $k$ integer counters. Each counter can store an arbitrary non-negative integer. In each step, the automaton can independently increment or decrement its counters and test them for $0$, and can move its input head once cell in each direction. It cannot write on the tape.

Your language is mentioned explicitly in the textbook:

One-counter automata are not as powerful as arbitrary TMs, although they can accept non-CFLs. For example, the set $\{a^nb^nc^n \mid n \geq 0\}$ can be accepted by a one-counter automaton.

I think the bidirectional nature of input head is what gives the automaton the power to check equality of the number of $a$'s and the number of $b$'s up to the $b$-$c$ border, then the input head goes back to the $a$-$b$ border and then checks for equality of the number of $b$'s and the number of $c$'s. If the string fails any of the above equality it rejects the string.