ABSTRACT FAMILIES OF DETERMINISTIC LANGUAGES.
Abstract
An abstract family of deterministic languages (AFDL) is defined herein as a family of languages closed under marked union, and inverse marked generalized sequential machine (a generalized sequential machine with a right endmarker) mapping. The notion of an abstract family of (one-way) deterministic acceptors (AFDA) is defined. The main result is that a family of languages is an AFDL if only there exists and AFDA which accepts exactly that family of languages. Thus the main result provides a characterization of the family of languages accepted by one-way deterministic acceptors in terms of certain closure properties. Certain subfamilies of AFDA with restructions on either the number of epsilon-moves or the length of the auxiliary memory are shown to yield AFDL. Finally it is shown that the three operations defining an AFDL are mutually independent. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 05, 1969
- Accession Number
- AD0693577
Entities
People
- William J. Chandler
Organizations
- System Development Corporation