Please use this identifier to cite or link to this item:

Structural equivalence and ETOL grammars

Authors Salomaa, Kai
Wood, Derick
Yu, Sheng
Issue Date 1995-09
Summary For a given context-sensitive grammar G we construct ET0L grammars G_1 and G_2 that are structurally equivalent if and only if the language generated by G is empty, which implies that structural equivalence is undecidable for ET0L grammars. In contrast, structural equivalence is decidable for E0L grammars and for extended E0L grammars. In fact, we show that structural equivalence is undecidable for propagating ET0L grammars in which the number of tables is restricted to be at most two. A stronger notion of equivalence that requires the sets of syntax trees to be isomorphic is shown to be decidable for ET0L grammars.
Language English
Format Technical report
Files in this item:
File Description Size Format
tr9544.pdf 288690 B Adobe PDF