Generative power of three-nonterminal scattered context grammars

摘要

This paper discusses the descriptional complexity of scattered context grammars with respect to the number of nonterminals. It proves that the three-nonterminal scattered context grammars characterize the family of recursively enumerable languages. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 7]