How instances of Automaton(NPDA) read and write the stack

Question

I am reading a text book, Introduction of the theory of computation by Michael Siper. I do not understand the notion of NPDA well. One problem is that the definition of NPDA is not clear on how the stack is shared by possibly many instances of the NPDA at a same time.

Answer 1

In effect each instantiation of the NPDA has its own copy of the stack.

There are at least two ways to think about the operation of a non-deterministic automaton.

• You can think of a given input as (possibly) driving several different computations, each of which you consider separately. In that case you look at the set of final outcomes of these computations to determine whether any of them results in acceptance of the input.

• Alternatively, you can think of a given input as driving all of the possible computations simultaneously; it sounds as if this is what you’re doing. In that case you probably think of the automaton as being in several states simultaneously. You should also think of its stack as having several different compositions simultaneously, one for each ‘branch’ of the combined computation.