Abstract
In this paper, we study the generative power of one-sided random context grammars working in a leftmost way. More specifically, by analogy with the three well-known types of leftmost derivations in regulated grammars, we introduce three types of leftmost derivations to one-sided random context grammars and prove the following three results. (I) One-sided random context grammars with type-1 leftmost derivations characterize the family of context-free languages. (II) One-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of recursively enumerable languages. (III) Propagating one-sided random context grammars with type-2 and type-3 leftmost derivations characterize the family of context-sensitive languages. In the conclusion, the generative power of random context grammars and one-sided random context grammars with leftmost derivations is compared.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Aho, A.V., Lam, M.S., Sethi, R., Ullman, J.D.: Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley, Boston (2006)
Aho, A.V., Ullman, J.D.: The Theory of Parsing, Translation and Compiling. Parsing, vol. I. Prentice-Hall, New Jersey (1972)
Baker, B.S.: Non-context-free grammars generating context-free languages. Information and Control 24(3), 231–246 (1974)
Cannon, R.L.: Phrase structure grammars generating context-free languages. Information and Control 29(3), 252–267 (1975)
Cojocaru, L., Mäkinen, E.: On the complexity of Szilard languages of regulated grammars. Tech. rep., Department of Computer Sciences, University of Tampere, Tampere, Finland (2010)
Cremers, A.B., Maurer, H.A., Mayer, O.: A note on leftmost restricted random context grammars. Information Processing Letters 2(2), 31–33 (1973)
Cytron, R., Fischer, C., LeBlanc, R.: Crafting a Compiler. Addison-Wesley, Boston (2009)
Dassow, J., Fernau, H., Păun, G.: On the leftmost derivation in matrix grammars. International Journal of Foundations of Computer Science 10(1), 61–80 (1999)
Dassow, J., Păun, G.: Regulated Rewriting in Formal Language Theory. Springer, New York (1989)
Fernau, H.: Regulated grammars under leftmost derivation. Grammars 3(1), 37–62 (2000)
Fernau, H.: Nonterminal complexity of programmed grammars. Theoretical Computer Science 296(2), 225–251 (2003)
Ferretti, C., Mauri, G., Păun, G., Zandron, C.: On three variants of rewriting P systems. Theoretical Computer Science 301(1-3), 201–215 (2003)
Freund, R., Oswald, M.: P Systems with Activated/Prohibited Membrane Channels. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 261–269. Springer, Heidelberg (2003)
Ginsburg, S., Spanier, E.H.: Control sets on grammars. Theory of Computing Systems 2(2), 159–177 (1968)
Kasai, T.: An hierarchy between context-free and context-sensitive languages. Journal of Computer and System Sciences 4, 492–508 (1970)
Lukáš, R., Meduna, A.: Multigenerative grammar systems. Schedae Informaticae 2006(15), 175–188 (2006)
Luker, M.: A generalization of leftmost derivations. Theory of Computing Systems 11(1), 317–325 (1977)
Matthews, G.H.: A note on asymmetry in phrase structure grammars. Information and Control 7, 360–365 (1964)
Maurer, H.: Simple matrix languages with a leftmost restriction. Information and Control 23(2), 128–139 (1973)
Meduna, A.: On the Number of Nonterminals in Matrix Grammars with Leftmost Derivations. In: Păun, G., Salomaa, A. (eds.) New Trends in Formal Languages. LNCS, vol. 1218, pp. 27–38. Springer, Heidelberg (1997)
Meduna, A.: Elements of Compiler Design. Auerbach Publications, Boston (2007)
Meduna, A., Goldefus, F.: Weak leftmost derivations in cooperative distributed grammar systems. In: MEMICS 2009: 5th Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, pp. 144–151. Brno University of Technology, Brno (2009)
Meduna, A., Techet, J.: Canonical scattered context generators of sentences with their parses. Theoretical Computer Science 2007(389), 73–81 (2007)
Meduna, A., Techet, J.: Scattered Context Grammars and their Applications. WIT Press, Southampton (2010)
Meduna, A., Škrkal, O.: Combined leftmost derivations in matrix grammars. In: ISIM 2004: Proceedings of 7th International Conference on Information Systems Implementation and Modelling, Ostrava, CZ, pp. 127–132 (2004)
Meduna, A., Zemek, P.: Nonterminal complexity of one-sided random context grammars. Acta Informatica 49(2), 55–68 (2012)
Meduna, A., Zemek, P.: One-sided random context grammars. Acta Informatica 48(3), 149–163 (2011)
Mihalache, V.: Matrix grammars versus parallel communicating grammar systems. In: Mathematical Aspects of Natural and Formal Languages, pp. 293–318. World Scientific Publishing, River Edge (1994)
Mutyam, M., Krithivasan, K.: Tissue P systems with leftmost derivation. Ramanujan Mathematical Society Lecture Notes Series 3, 187–196 (2007)
Păun, G.: On leftmost derivation restriction in regulated rewriting. Romanian Journal of Pure and Applied Mathematics 30(9), 751–758 (1985)
Rosenkrantz, D.J.: Programmed grammars and classes of formal languages. Journal of the ACM 16(1), 107–131 (1969)
Rozenberg, G., Salomaa, A. (eds.): Handbook of Formal Languages, vol. 1 through 3. Springer, Berlin (1997)
Salomaa, A.: Matrix grammars with a leftmost restriction. Information and Control 20(2), 143–149 (1972)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Meduna, A., Zemek, P. (2012). One-Sided Random Context Grammars with Leftmost Derivations. In: Bordihn, H., Kutrib, M., Truthe, B. (eds) Languages Alive. Lecture Notes in Computer Science, vol 7300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31644-9_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-31644-9_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31643-2
Online ISBN: 978-3-642-31644-9
eBook Packages: Computer ScienceComputer Science (R0)