On the Tape Complexity of Deterministic Context-Free Languages

Abstract

Let DSPACE(L(n)) denote the family of languages recognized by deterministic L(n)-tape bounded Turmg machines The pnnopal result described m this paper is the equivalence of the following statements (l) The determtmsttc context-free language L~ 2) (described m the paper) is m DSPACE(Iog(n)) (2) The simple LL(I) languages are m DSPACE(tog(n)) (3) The simple precedence languages are in DSPACE(Iog(n)). ( In a recent paper In this paper the tape complexity of determmisttc context-free languages is considered. It is shown that there is a single determmisttc context-free language L~ 2) which is recognized by a determinisUc [nondeterministic] log(n)-tape bounded Turing machine if, and only if, all deterministic context-free languages can be recognized by determmistic [nondetermimstic] log(n)-tape bounded Turing machines. Also, L~ 21 may be log(n)-tape reduced to a simple LL(I) language, as discussed by Korenjak and Hopcroft [221 and Aho and Ullman [2], and to a simple precedence language, as discussed by Wtrth and Weber It is shown, therefore, that these proper subfamilies of the deterministic context-free languages are as difficult to recognize as the complete family of deterministic context-free languages. Furthermore, tt is shown that Lt02) is recognized by a determmisttc log(n)-tape bounded Turmg machine if, and only if, the family of languages recogmzed by deterministic multlhead two-way pushdown automata m polynomml time is identical to