Kybernetika 30 no. 2, 177-186, 1994

Syntactic complexity of regulated rewriting

Alexander Meduna, Cynthia J. Crooks and Milan Šárek

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.

Classification:

68Q42, 68Q45, 68Q50