Accession Number : AD0693577
Title : ABSTRACT FAMILIES OF DETERMINISTIC LANGUAGES.
Descriptive Note : Scientific rept.,
Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF
Personal Author(s) : Chandler,William J.
Report Date : 05 MAY 1969
Pagination or Media Count : 79
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)
Descriptors : (*COMPUTATIONAL LINGUISTICS, AUTOMATA), PROGRAMMING LANGUAGES, SET THEORY, GROUPS(MATHEMATICS), GRAMMARS, THEOREMS, AUTOMATA
Subject Categories : Linguistics
Computer Programming and Software
Distribution Statement : APPROVED FOR PUBLIC RELEASE