Language classes generated by tree controlled grammars with bounded nonterminal complexity (Q443749)

Tree controlled grammars were introduced in [\textit{K. Čulik II.} and \textit{H. A. Maurer}, Computing 19, 129--139 (1977; Zbl 0363.68108)] as a pair \((G,R)\), where \(G\) is a context-free grammar and \(R\) is a regular control language containing words composed of the terminal and nonterminal alphabets of \(G\), and it is used to control the work of \(G\) by restricting the set of derivations which \(G\) is allowed to make. Only those words belong to the generated language which can be generated by the context-free grammar \(G\) having a derivation tree where, for all the strings obtained by reading from left to right, the symbols labeling the nodes which belong to the same level of the tree (with the exception of the last level) are elements of the regular set \(R\). The nonterminal complexity of tree controlled grammars was defined in [the first author et al., Theor. Comput. Sci. 412, No. 41, 5789--5795 (2011; Zbl 1234.68187)] as the sum of the number of nonterminals of the context-free grammar and the number of nonterminals which are necessary to generate the regular control language; it was shown that nine nonterminals are sufficient to generate any recursively enumerable language. In the present paper this bound is decreased from nine to seven, and other language classes are also considered from the point of view of nonterminal complexity with respect to tree controlled grammars. Regular, linear, and regular simple matrix languages are shown to be generated with three nonterminals which is an optimal bound since a regular language is presented which cannot be generated with two nonterminals. For context-free languages, on the other hand, four nonterminals are sufficient, although it is not known whether this bound can be decreased to three or not.