Structural equivalence and ET0L grammars

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.

Authors

• Kai Salomaa
• Derick Wood
• Yu Sheng State Key Laboratory of Multimodal Artificial Intelligence Systems,Institute of Automation, Chinese Academy of Sciences, Beijing, China School of Artificial Intelligence, University of Chinese Academy of Sciences, Beijing, China

Keywords

No keywords are indexed for this paper.