On the Existence of Generators for Certain Afl

摘要

It is shown that under mild conditions on a tape function f, the AFL generated by the languages accepted by f-tape-bounded (deterministic) Turing acceptors is generated by a single language, i.e., is principal. The same result holds for the AFL generated by the languages accepted by f-tape-bounded Turing acceptors with a (possibly unbounded) pushdown tape. From these results it follows that the AFL generated by writing pushdown-acceptor languages and the AFL generated by the twoway (deterministic)(nonerasing) stack-acceptor languages are principal. A modification of the main argument shows that the AFL generated by the two-way pushdown-acceptor languages is also principal. (Author)