FULL AFLS AND NESTED ITERATED SUBSTITUTION,
Abstract
Recently there have been several investigations of the closure under substitution of various families of languages, and of the relation of substitution to AFLs in general. A machine realization of the substitution closure of a full AFL l was obtained by finitely nesting tapes of any machine representation for l. It was shown that if any full AFL l is not closed under substitution, the result of substituting members of l into l, is not substitution closed and hence l generates an infinite hierarchy of full AFLs and the substitution closure of l is not full principal. In the paper we define a generalization of the substitution operator, called nested interated substitution, examine the properties of families of languages closed under nested iterated substitution, establish the appropriate machine characterization and discuss related decision problems.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1969
- Accession Number
- AD0697426
Entities
People
- Sheila A. Greibach
Organizations
- Harvard University