On Subregular Selection Languages in Internal Contextual Grammars
Jürgen Dassow, Florín Manea, Bianca Truthe · Universitätsbibliothek Gießen · 2012
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 ${\cal F}_n$ 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 ${\cal F}_n$. 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.