ABSTRACT FAMILIES OF LANGUAGES GENERATED BY BOUNDED LANGUAGES,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 04, 1970
- Accession Number
- AD0709416
Entities
People
- Jonathan Goldstine
Organizations
- System Development Corporation