Accession Number : AD0693576

Title :   PRINCIPAL AFL,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s) : Ginsburg,Seymour ; Greibach,Shelia

Report Date : 07 APR 1969

Pagination or Media Count : 55

Abstract : A (full) principal abstract family of languages(AFL) is a (full) AFL generated by a single language, i.e., it is the smallest (full) AFL containing the given language. In the present paper, a study is made of such AFL. First, an AFA (abstract family of acceptors) characterization of (full) principal AFL is given. From this result, many well-known families of AFL can be shown to be (full) principal AFL. Next, a representation theorem for each language in a (full) principal AFL is given involving the generator and one application each of concatenation, star, intersection with a regular set, inverse homomorphism, and a special type of homomorphism. Finally, it is shown that if LL1 and LL2 are (full) principal AFL, then so are (a) the smallest (full) AFL containing (the intersection of L1 and L2/L1 in LL1, L2 in LL2) and (b) the family obtained by substituting epsilon-free languages of LL2 into languages of LL1. (Author)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, THEORY), PROGRAMMING LANGUAGES, SET THEORY, MAPPING(TRANSFORMATIONS), GROUPS(MATHEMATICS), GRAMMARS, THEOREMS, AUTOMATA

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE