A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

摘要

In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with a reduced number of both nonterminals and context-sensing productions.