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