On the computational power of pushdown automata

摘要

We present a relation between the sets accepted by two-way pushdown automataand certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-symbol storage-tape alphabet. If for all but a finite number of n, T uses no more than log2tn storage cells when given an input of length n, then L is accepted by a twoway nondeterministic pushdown automaton. Thus, any nondeterministic tape complexity class L(n) such that supn→∞(L(n)/logn))=0 is a subfamily of the two-way nondeterministic pushdown automaton languages.