Scattered Context Generators of Sentences with Their Parses

The paper discusses the use of scattered context grammars to generate their sentences together with the corresponding parses -- that is, the sequences of labels denoting productions whose use leads to the generation of the corresponding sentences. It is proved 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. The same result can be proved if we use canonical versions of scattered context generators.