On Internal Contextual Grammars with Subregular Selection Languages

摘要

In this paper, we study the power of internal contextual grammars with selection languages from subfamilies of the family of regular languages. If we consider families F_n which are obtained by restriction to n states or nonterminals or productions or symbols to accept or to generate regular languages, we obtain four infinite hierarchies of the corresponding families of languages generated by internal contextual grammars with selection languages in F_n.