Accession Number : AD0709416

Title :   ABSTRACT FAMILIES OF LANGUAGES GENERATED BY BOUNDED LANGUAGES,

Corporate Author : SYSTEM DEVELOPMENT CORP SANTA MONICA CALIF

Personal Author(s) : Goldstine,Jonathan

Report Date : 04 JUN 1970

Pagination or Media Count : 142

Abstract : An AFL is defined to be bounded if it is generated by a set of bounded languages. It is shown that the smallest full AFL containing a bounded AFL is itself a bounded AFL. An AFL is exhibited which is contained in a bounded AFL but which is not itself bounded. It is shown that a bounded AFL containing a non-regular set cannot be closed under substitution. If g is any set of bounded languages, it is shown that the smallest intersection closed AFL containing g cannot contain all recursively enumerable languages. In contrast, a one-letter language L is exhibited for which the smallest intersection closed full AFL containing L does contain all recursively enumerable languages. A set g of languages is independent if every proper subset of g fully generates a smaller full AFL then g does. It is shown that there exist infinite independent sets of languages. A representation in terms of multitape sequential transducers is given for each language in the smallest intersection closed (full) AFL containing a given language. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, MATHEMATICAL MODELS), (*COMPUTATIONAL LINGUISTICS, SET THEORY), AUTOMATA, MAPPING(TRANSFORMATIONS), THEOREMS

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE