Would it be possible/legal to design a PDA that can use the stack as a way to keep track of the number of inputs seen? (i.e the size of the stack would act as some sort of counter).

What I was thinking:

  1. First transition would require you to push a "1" to the stack

  2. All future transitions would require you to pop the top of the stack (let's call this $x$) and push $x+1$ onto it.

The language of the stack would be the set of all natural numbers excluding 0.

I'm having trouble understanding whether the "push $x+1$" move would work

  • 2
    $\begingroup$ Stack alphabet of pda must be finite but in your case it's infinite. $\endgroup$ Commented Oct 27, 2019 at 1:35
  • $\begingroup$ Ooh very good point. Thanks! $\endgroup$
    – Anthony
    Commented Oct 27, 2019 at 2:08

1 Answer 1


Note that in your model, you only ever have a single item $x$ on the stack, namely the current number of inputs seen. Thus, you're not really using the stack.

This is sometimes called a register, and there are models called register machines, or sometimes cost register automata, introduced by Alur in 2011.

The power of this model, and certain algorithmic properties of it, depend on what you allow to do with the register. If you allow reading it's value and comparing it to e.g. 0, then very quickly things become undecidable. But if you only allow simpler things, you get all kinds of interesting models.


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.