On the Tape Complexity of Deterministic Context-Free Languages
Ivan Hal Sudborough · Journal of the ACM · 1978
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)).(4) DSPACE(Iog(n)) is identical to the famdy of languages recogmzed by deterministic two-way multlhead pushdown automata m polynomml tmae These results are obtained by constructing a determlmstlc context-free language L~ 2~ which is log(n)-complete for the family of determlmstlc context-free languages In other words, a tape hardest deterministic context-free language is described The best upper bound known on the tape complexity of (deterministic) context-free languages is (log(n)) 2 KEY WORDS AND PHRASES deterministic context-free languages, tape complexity, stmple precedence languages, snnple LL(I) languages, Tunng machine, log(n)-tape reduclblhty, log(n) complete, polynomial time bounded multlhead pushdown automata, Dyck languages CR CATEGORIES 5 23, 5 25Lewis, Stearns, and Hartmanis [23] have described an algorithm to recognize every contextfree language by a deterministic (log(n))2-tape bounded Turing machine.In a recent paper [26] the author has shown that, if the context-free languages could be recogmzed by a determimstic log(n)-tape bounded Tunng machine, then nondetermmistic and deterministic L(n)-tape bounded complexity classes are identical, for L(n) >_ log(n).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 [28] and Aho and Ullman [2].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 General permission to make fair use in teaching or research of all or part of this material IS granted to individual readers and to nonprofit hbrarles actmg for them provided that ACM's copyright notice is given and that reference is made to the pubhcatlon, to its date of issue, and to the fact that reprinting pnvdeges were granted by permission of the Association for Computing Machinery To otherwise repnnt a figure, table, other substantial excerpt, or the entire work reqmres speofic permission as does republication, or systematic or multiple reproduction Some of these results were presented at the