Abstract
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.
Research supported by the Natural Sciences and Engineering Research Council of Canada grants.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Ginsburg and M. Harrison, Bracketed context-free languages, J. Comput. System Sci. 1 (1967) 1–23.
R. McNaughton, Parenthesis grammars, J. Assoc. Comput. Mach. 14 (1967) 490–500.
V. Niemi, A normal form for structurally equivalent E0L grammars. In: “Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology”, G. Rozenberg and A. Salomaa (eds.), Springer-Verlag, 1992, pp. 133–148.
T. Ottmann and D. Wood, Defining families of trees with E0L grammars, Discrete Applied Math. 32 (1991) 195–209.
T. Ottmann and D. Wood, Simplifications of E0L grammars. In: “Lindenmayer Systems: Impacts on Theoretical Computer Science, Computer Graphics, and Developmental Biology”, G. Rozenberg and A. Salomaa (eds.), Springer-Verlag, 1992, pp. 149–166.
M. Paull and S. Unger, Structural equivalence of context-free grammars, J. Comput. System Sci. 2 (1968) 427–463.
M. Penttonen, One-sided and two-sided context in formal grammars, Inform. Control 25 (1974) 371–392.
G. Rozenberg and A. Salomaa, The Mathematical Theory of L Systems. Academic Press, New York, 1980.
A. Salomaa, Formal Languages. Academic Press, New York, 1973.
K. Salomaa and S. Yu, Decidability of structural equivalence of E0L grammars, Theoret. Comput. Sci. 82 (1991) 131–139.
J. W. Thatcher, Tree automata: an informal survey. In: “Currents in the Theory of Computing”, A. V. Aho (ed.), Prentice Hall, Englewood Cliffs, NJ, 1973, pp. 143–172.
D. Wood, Theory of Computation. John Wiley & Sons, New York, 1987.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Salomaa, K., Wood, D., Yu, S. (1993). Structural Equivalence and ETOL grammars. In: Ésik, Z. (eds) Fundamentals of Computation Theory. FCT 1993. Lecture Notes in Computer Science, vol 710. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57163-9_37
Download citation
DOI: https://doi.org/10.1007/3-540-57163-9_37
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57163-6
Online ISBN: 978-3-540-47923-9
eBook Packages: Springer Book Archive