ON THE EXISTENCE OF GENERATORS FOR CERTAIN AFL,
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 18, 1970
- Accession Number
- AD0708494
Entities
People
- Gene F. Rose
- Seymour Ginsburg
Organizations
- System Development Corporation