Does the size of the stack of a PDA matter?



Hi,

Consider a linear bounded pushdown automata (LBPDA) for which the size of
the stack is bounded by some constant multiple of the length of the input.
Is LBPDA's expressive power weaker than that of a normal PDA (i.e. a LBPDA
cannot express some languages that can be done by a PDA)? Or, do both of
these two computation model have the same expressive power? (Let's just
assume that both are nonderministic.)

Thanks,
Dillon


.