Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages

Abstract

The family of recursively enumerable languages is characterized by scattered context grammars with four nonterminals. Moreover, this family is characterized by scattered context grammars with three nonterminals if these grammars start their derivations from a word rather than a symbol. Three open problem areas are suggested

Keywords:

• Descriptional complexity
• scattered context grammars
• reduced number of nonterminals
• recursively enumerable languages

C.R.Categories:

• F.4.2.1.