Accession Number : AD0697426

Title :   FULL AFLS AND NESTED ITERATED SUBSTITUTION,

Corporate Author : HARVARD UNIV CAMBRIDGE MASS DIV OF ENGINEERING AND APPLIED PHYSICS

Personal Author(s) : Greibach,Sheila A.

Report Date : AUG 1969

Pagination or Media Count : 41

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.

Descriptors :   (*COMPUTATIONAL LINGUISTICS, *CONTEXT FREE GRAMMARS), SET THEORY, PROGRAMMING LANGUAGES, AUTOMATA, GROUPS(MATHEMATICS), THEOREMS

Subject Categories : Linguistics
      Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE