GENERATION OF SENTENCES WITH THEIR PARSES BY SCATTERED CONTEXT GRAMMARS ABSTRACT

This paper uses the propagating scattered context grammars to generate their language’s sentences together with their parses (the sequences of productions whose use lead to the generation of the corresponding sentences). It proves that for every recursively enumerable language, L, there exists a propagating scattered context grammar whose language consists of L’s sentences followed by their parses.