Abstract:

The syntactic complexity of regulated grammars with respect to the number of nonterminals is investigated. Several characterizations of the family of recursively enumerable languages are established; most importantly, it is proved that this family is defined by programmed grammars with only seven nonterminals.