Context-Free Languages and Pushdown Automata | SpringerLink
Skip to main content
Springer Nature Link
Log in

Context-Free Languages and Pushdown Automata

  • Chapter
  • First Online:
Handbook of Formal Languages

Abstract

This chapter is devoted to context-free languages. Context-free languages and grammars were designed initially to formalize grammatical properties of natural languages [9]. They subsequently appeared to be well adapted to the formal description of the syntax of programming languages. This led to a considerable development of the theory.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. A. V. Aho and J. D. Ullman. The Theory of Parsing, Translation and Compiling., volume 1. Prentice-Hall, 1973.

    Google Scholar 

  2. J.-M. Autebert. Théorie des langages et des automates. Masson, 1994.

    Google Scholar 

  3. J.-M. Autebert, L. Boasson, and I. H. Sudborough. Some observations on hardest context-free languages. Technical Report 81–25, Rapport LITP, April 1981.

    Google Scholar 

  4. J. Berstel. Transductions and Context-Free Languages. Teubner Verlag, 1979.

    Book  Google Scholar 

  5. M. Blattner and S. Ginsburg. Canonical forms of context-free grammars and position restricted grammar forms. In Karpinski, editor, Fundamentals of Computing Theory, volume 56 of Lect. Notes Comp. Sei., 1977.

    MATH  Google Scholar 

  6. L. Boasson. Two iteration theorems for some families of languages. J. Comput. System Sei., 7(6):583–596, December 1973.

    Article  MathSciNet  Google Scholar 

  7. L. Boasson, J. P. Crestin, and M. Nivat. Familles de langages translatables et fermées par crochet. Acta Inform., 2:383–393, 1973.

    Article  Google Scholar 

  8. F. J. Brandenburg. On the intersection of stacks and queues. Theoret. Comput. Sci., 23:69–82, 1983.

    Article  MathSciNet  Google Scholar 

  9. N. Chomsky. On certain formal properties of grammars. Inform. and Control, 2:137–167, 1959.

    Article  MathSciNet  Google Scholar 

  10. N. Chomsky and M. P. Schützenberger. The algebraic theory of context-free languages. In P. Bradford and D. Hirschberg, editors, Computer programming and formal systems, pages 118–161. North-Holland (Amsterdam), 1963.

    Chapter  Google Scholar 

  11. S. V. Cole. Deterministic pushdown store machines and realtime computation. J. Assoc. Comput. Mach., 18:306–328, 1971.

    Article  MathSciNet  Google Scholar 

  12. B. Courcelle. On jump deterministic pushdown automata. Math. Systems Theory, 11:87–109, 1977.

    Article  MathSciNet  Google Scholar 

  13. A. Cremers and S. Ginsburg. Context-free grammar forms. J. Comput. System Sci., 11:86–117, 1975.

    Article  MathSciNet  Google Scholar 

  14. R. J. Evey. The theory and application of pushdown store machines. In Mathematical Linguistics and Automatic Translation, NSF-IO, pages 217–255. Harvard University, May 1963.

    Google Scholar 

  15. M. Fliess. Transductions de séries formelles. Discrete Math., 10:57–74, 1974.

    Article  MathSciNet  Google Scholar 

  16. R. W. Floyd. Syntactic analysis and operator precedence. J. Assoc. Comput. Mach., 10:313–333, 1963.

    Article  Google Scholar 

  17. S. Ginsburg. The Mathematical Theory of Context-Free Languages. McGraw-Hill, 1966.

    MATH  Google Scholar 

  18. S. Ginsburg, J. Goldstine, and S. Greibach. Some uniformely erasable families of languages. Theoret. Comput. Sci., 2:29–44, 1976.

    Article  MathSciNet  Google Scholar 

  19. S. Ginsburg and M. A. Harrison. Bracketed context-free languages. J. Comput. System Sei., 1:1–23, 1967.

    Article  MathSciNet  Google Scholar 

  20. S. Ginsburg and H. G. Rice. Two families of languages related to ALGOL. J. Assoc. Comput. Mach., 9:350–371, 1962.

    Article  MathSciNet  Google Scholar 

  21. S. Ginsburg and E. Spanier. Finite-turn pushdown automata. SIAM J. Control, 4:429–453, 1966.

    Article  MathSciNet  Google Scholar 

  22. S. Ginsburg and E. Spanier. Derivation-bounded languages. J. Comput. System Sei., 2:228–250, 1968.

    Article  MathSciNet  Google Scholar 

  23. S. Greibach. The hardest context-free language. SIAM J. Comput., 2:304–310, 1973.

    Article  MathSciNet  Google Scholar 

  24. S. A. Greibach. A new normal form theorem for context-free phrase structure grammars. J. Assoc. Comput. Mach., 12(1):42–52, 1965.

    Article  MathSciNet  Google Scholar 

  25. S. A. Greibach. Jump pda’s, deterministic context-free languages, principal afdl’s and polynomial time recognition. In Proc. 5th Annual ACM Conf. Theory of Computing, pages 20–28, 1973.

    MATH  Google Scholar 

  26. S. A. Greibach. Jump pda’s and hierarchies of deterministic cf languages. SIAM J. Comput., 3:111–127, 1974.

    Article  MathSciNet  Google Scholar 

  27. J. Gruska. A few remarks on the index of context-free grammars and languages. Inform. and Control, 19:216–223, 1971.

    Article  MathSciNet  Google Scholar 

  28. M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978.

    MATH  Google Scholar 

  29. J. E. Hoperoft and J. D. Ullman. Formal Languages and Their Relation to Automata. Addison-Wesley, 1969.

    Google Scholar 

  30. J. E. Hoperoft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979.

    MATH  Google Scholar 

  31. G. Hotz. Normal form transformations of context-free grammars. Acta Cybernetics, 4(1):65–84, 1978.

    MathSciNet  MATH  Google Scholar 

  32. G. Hotz and K. Estenfeld. Formale Sprachen. B.I.-Wissenschaftsverlag, 1981.

    MATH  Google Scholar 

  33. G. Hotz and T. Kretschmer. The power of the Greibach normal form. Elektron. Inforrnationsverarb. Kybernet., 25(10):507–512, 1989.

    MathSciNet  MATH  Google Scholar 

  34. D.E. Knuth. On the translation of languages from left to right. Inform. and Control, 8:607–639, 1965.

    Article  MathSciNet  Google Scholar 

  35. D. E. Knuth. A characterization of parenthesis languages. Inform. and Control, 11:269–289, 1967.

    Article  Google Scholar 

  36. A. J. Korenjack and J. E. Hoperoft. Simple deterministic languages. In Conference record of seventh annual symposium on switching and automata theory, pages 36–46, Berkeley, 1966.

    Google Scholar 

  37. W. Kuich. Formal power series, chapter 9. This volume.

    Google Scholar 

  38. P. M. Lewis and R. E. Stearns. Syntax-directed transduction. J. Assoc. Comput. Mach., 15(3):465–488, 1968.

    Article  Google Scholar 

  39. R. McNaughton. Parenthesis grammars. J. Assoc. Comput. Mach., 14(3):490–500, 1967.

    Article  Google Scholar 

  40. M. Nivat. Transductions des langages de Chomsky, Ch. VI,miméographié. PhD thesis, Université de Paris, 1967.

    Google Scholar 

  41. M. Nivat. Transductions des langages de Chomsky. Annales de l’Institut Fourier, 18:339–456, 1968.

    Article  MathSciNet  Google Scholar 

  42. M. Oyamaguchi. The equivalence problem for realtime dpda’s. J. Assoc. Corn-put. Mach., 34:731–760, 1987.

    Article  MathSciNet  Google Scholar 

  43. R. J. Parikh. On context-free languages. J. Assoc. Comput. Mach., 13:570–581, 1966.

    Article  MathSciNet  Google Scholar 

  44. D. L. Pilling. Commutative regular equations and Parikh’s theorem. J. London Math. Soc., 6:663–666, 1973.

    Article  MathSciNet  Google Scholar 

  45. D. J. Rosenkrantz. Matrix equations and normal forms for context-free grammars. J. Assoc. Comput. Mach., 14:501–507, 1967.

    Article  MathSciNet  Google Scholar 

  46. Jacques Sakarovitch. Pushdown automata with terminal languages. In Languages and Automata Symposium, number 421 in Publication RIMS, Kyoto University, pages 15–29, 1981.

    Google Scholar 

  47. A. Salomaa. Formal Languages. Academic Press, 1973.

    MATH  Google Scholar 

  48. M. P. Schützenberger. On context-free languages and pushdown automata. Inform. and Control, 6:217–255, 1963.

    Article  Google Scholar 

  49. G. Sénizergues. The equivalence and inclusion problems for NTS languages. J. Comput. System Sci., 31:303–331, 1985.

    Article  MathSciNet  Google Scholar 

  50. G. Sénizergues. Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages. Inform. Comput., 81:265–279, 1989.

    Article  MathSciNet  Google Scholar 

  51. E. Shamir. A representation theorem for algebraic and context-free power series in noncommuting variables. Inform. Comput., 11:39–254, 1967.

    MathSciNet  MATH  Google Scholar 

  52. S. Sippu and E. Soisalon-Soininen. Parsing Theory, Vol I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, 1988.

    Google Scholar 

  53. L. Valiant. The equivalence problem for deterministic finite turn pushdown automata. Inform. and Control, 25:123–133, 1974.

    Article  MathSciNet  Google Scholar 

  54. H. Wechler. Characterization of rational and algebraic power series. RA IRO Inform. Théor., 17:3–11, 1983.

    Article  MathSciNet  Google Scholar 

  55. M. K. Yntema. Inclusion relations among families of context-free languages. Inform. and Control, 10:572–597, 1967.

    Article  Google Scholar 

Download references

Authors
  1. Jean-Michel Autebert
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jean Berstel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luc Boasson
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Leiden University, P.O. Box 9512, Leiden, RA, NL-2300, The Netherlands

    Grzegorz Rozenberg

  2. Turku Centre for Computer Science Data City, Turku, FIN-20520, Finland

    Arto Salomaa

Rights and permissions

Reprints and permissions

Copyright information

© 1997 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Autebert, JM., Berstel, J., Boasson, L. (1997). Context-Free Languages and Pushdown Automata. In: Rozenberg, G., Salomaa, A. (eds) Handbook of Formal Languages. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-59136-5_3

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-59136-5_3

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-63863-3

  • Online ISBN: 978-3-642-59136-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation