Accession Number : AD0702527

Title :   PRINCIPAL AFL,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

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

Report Date : 12 JAN 1970

Pagination or Media Count : 56

Abstract : A (full) principal 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 l1 and l2 are (full) principal AFL, then so are (a) the smallest (full) AFL containing ((the intersection of L1 and L2)/L1 in l1, 12 in 12) and (b) the family obtained by substituting epsilon-free languages of 12 into languages of l1. (Author)

Descriptors :   (*COMPUTATIONAL LINGUISTICS, SET THEORY), GRAMMARS, AUTOMATA, THEOREMS

Subject Categories : Linguistics

Distribution Statement : APPROVED FOR PUBLIC RELEASE