Does the size of the stack of a PDA matter?
- From: "Dillon" <dillongeo@xxxxxxxxx>
- Date: Sun, 13 Jul 2008 19:10:12 -0500
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
.
- Prev by Date: Re: Rice's theorem
- Next by Date: Re: Is this language context free?
- Previous by thread: TAUTOLOGY and SAT
- Next by thread: reducing the factorization decision problem to SAT?
- Index(es):