Closure of families of languages under substitution operators
David Jean Lewis · 1970
This paper treats the closure of families of formal languages under operators which may be viewed as substitution into a particular language. A language L over alphabet {a1,...,an} induces an n-place operator on languages by substitution of the n arguments Li for the symbols ai. For example, if L is regular, it induces an operator under which any full AFL is closed. In section two we find a large class of full AFL's which are closed under no other such operators than those induced by regular languages. Also, for any full AFL @@@@', let @@@@ be the class of languages which @@@@' is closed under substitution into. Then @@@@ is itself a full AFL and is closed under substitution. Finally we show that any substitution-closed full AFL @@@@ is obtained in this manner from some non-substitution-closed full AFL @@@@ (except when @@@@ is the universal family).