# Difference between Counter-machine and stack machine

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.

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\}$$.

• But "proper subset of the context free languages." this is not understanding.. Give one example which proper is what Commented Oct 15, 2021 at 17:47
• @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.
– rici
Commented Oct 15, 2021 at 17:50
• This is possible $\{a^nb^m\}$ could be proper subset of $\{a^nb^ma^mb^n\}$ ? Commented Oct 15, 2021 at 17:53
• @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.)
– rici
Commented Oct 15, 2021 at 17:57
• please could you explain with example.. I am struggling to understand.. Please Commented Oct 15, 2021 at 18:04