Substitution and bounded languages

摘要

A full AFL is defined to be full-bounded if it can be generated by a set of boundedlanguages. It is shown that if ℳ is an AFL not consisting entirely of regular sets and if ℳ is contained in any full-bounded AFL, then ℳ is not closed under e-free substitution. Some typical consequences are that some context-free languages cannot be generated from any set of (not necessarily context-free) bounded languages by full AFL operations, or from any set of bounded context-free languages by full AFL operations and substitution.