On the generation of sentences with their parses by propagating regular-controlled grammars

Abstract: The present paper explains how to transform any regular-controlled (context-free) grammar with appearance checking to a propagating regular-controlled (context-free) grammar with appearance checking whose language has sentences of the form , where and is a parse of  in . Consequently, for every recursively enumerable language , there exists a propagating regular-controlled grammar with appearance checking with of the above form so that results from by erasing all rules in . In addition, analogical results are established (a) in terms of these grammars without appearance checking and (b) in terms of these grammars that make only leftmost derivations. In the conclusion, we point out some consequences implied by the results achieved in this paper. [Copyright &y& Elsevier]