I read from this question that counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol).

My question is counter machine means counter coexist with stack? I mean "DFA $+ 1$ counter" is same thing with "DFA $+1$ stack" . For example to generate this language $\{a^n b^n \mid n\geq 0\}$ we need counter + stack.

I also from that question Languages recognized by one counter automata form a proper subset of the context free languages. What does it mean? Could you give one example.


1 Answer 1


You can recognize $\{a^nb^n\}$ with just a counter (which is incremented by an $a$ and decremented by a $b$). No additional stack is needed. (If you used a stack, it would only contain $a$s; in general a counter is functionally equivalent to a stack whose alphabet consists of only one symbol.)

The answer to the question you link to provides an example of a deterministic context free language which cannot be recognised by a one-counter automaton: $\{a^nb^ma^mb^n\}$.

  • $\begingroup$ But "proper subset of the context free languages." this is not understanding.. Give one example which proper is what $\endgroup$
    – Punia
    Oct 15, 2021 at 17:47
  • $\begingroup$ @punia: $A$ is a proper subset of $B$ means that everything in $A$ is also in $B$, but at least one thing in $B$ is not in $A$. The answer gives an example of such a thing. $\endgroup$
    – rici
    Oct 15, 2021 at 17:50
  • $\begingroup$ This is possible $\{a^nb^m\}$ could be proper subset of $\{a^nb^ma^mb^n\}$ ? $\endgroup$
    – Punia
    Oct 15, 2021 at 17:53
  • $\begingroup$ @punia: that's not what this is about (although it's true). The claim is that the set of languages recognisable with a one-counter automaton is a subset of the set of languages recognisable with a context-free grammar. It says nothing about individual languages in those sets. (A set of languages is a set of sets.) $\endgroup$
    – rici
    Oct 15, 2021 at 17:57
  • $\begingroup$ please could you explain with example.. I am struggling to understand.. Please $\endgroup$
    – Punia
    Oct 15, 2021 at 18:04

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.