what is the effect of adding another stack to a PDA

Question

does it increase the power of a push down automata? or does it have no effect on the power of the PDA ?

score 3 · Accepted Answer · answered Dec 18 '11 at 07:45

3

Having two (or more) stacks in a PDA is equivalent to having a Turing machine. See Problem 1.b here.

answered Dec 18 '11 at 07:45

bzc

1 Answers1