Bounded AFLs

摘要

A language is m-bounded if it is a subset of w1*…wm* for some words w1, …, wm. A study is made of the languages that can be generated from m-bounded languages by various operations. For each m, there is an (m+1)-bounded language that cannot be generated from m-bounded languages using only full AFL operations and substitution; and there is a context-free language that cannot be generated from any (not necessarily context-free) bounded languages. There is a context-sensitive language that cannot be generated from bounded languages using only AFL operations and intersection. But every language can be generated from one-letter languages using full AFL operations and intersection. Consequently, there is a way to code arbitrary languages into one-letter languages in such a way that the decoding process can be performed by means of full AFL operations and intersection, but the use of erasing is essential.