
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 nonregular 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 oneletter 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