On Subregular Selection Languages in Internal Contextual Grammars

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ₙ which are obtained by restriction to n states, nonterminals, productions, or symbols to accept or to generate a regular language, we obtain four infinite hierarchies of the corresponding families of languages generated by internal contextual grammars with selection languages in Fₙ. Moreover, we present some results on the power of internal contextual grammars with finite, monoidal, nilpotent, combinational, definite, ordered, regular commutative, regular circular, regular suffix-closed, and union-free selection languages.