A geometric hierarchy of languages

摘要

This paper proves the existence of a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context-free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the next larger family. The families of the hierarchy have properties analogous to those of the context-free family, in particular decidability properties are the same and on one symbol alphabets, member languages are regular. The geometric pumping lemma within the context-free languages generalizes to yield analogous results for the other families. In fact, this latter property is responsible for the existence of the hierarchy.