Generation of sentences with their parses : the case of propagating scattered context grammars

Abstract

Propagating scattered context grammars are used to generate their sentences together with their parses - that is, the sequences of labels denoting productions whose use lead 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.