Structural equivalence and ET0L grammars. (English) Zbl 0794.68093

Ésik, Zoltán (ed.), Fundamentals of computation theory. 9th international conference, FCT ’93, Szeged, Hungary, August 23-27, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 710, 430-439 (1993).
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. This is in contrast to the decidability result for the E0L case. In fact, we show that structural equivalence is undecidable for propagating ET0L grammars even when 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.
For the entire collection see [Zbl 0875.00104].


68Q42 Grammars and rewriting systems