1
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ single counter can keep any fixed amount of counters by bit-slicing $\endgroup$
    – Bulat
    Apr 6, 2019 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$ Apr 6, 2019 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$ Apr 6, 2019 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, 2019 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, 2019 at 16:47

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It sounds like they have a non-standard definition of one-counter automata. That's fine, as long as everyone understands which definition we are using in any particular context. $\endgroup$
    – D.W.
    Apr 7, 2021 at 18:58
  • $\begingroup$ @D.W. I have provided the book's details as Edit 1. $\endgroup$
    – Aryan
    Apr 8, 2021 at 4:05
  • 2
    $\begingroup$ Please do not use "Edit:". Instead, just edit your answer to include the necessary information. Future readers are typically not interested in the history of your post. $\endgroup$ Apr 8, 2021 at 6:54
  • 2
    $\begingroup$ Moreover, in order to allow text to be accessible to search engines and screen readers, please transcribe it rather than just posting an image. $\endgroup$ Apr 8, 2021 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.