Abstract
This chapter covers the basics of formal language theory. It covers all the notions that are necessary to follow the rest of this book. Apart from the classical rudiments, however, the chapter covers several lesser-known areas of this theory, such as parallel grammars, because these areas are also needed to fully grasp some upcoming topics discussed in this book. The chapter consists of four sections.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsNotes
- 1.
Let us note that the notion of a parse represents a synonym of several other notions, including a derivation word, a Szilard word, and a control word.
Bibliography
N. Chomsky, Three models for the description of language. IRE Trans. Inf. Theory 2(3), 113–124 (1956)
N. Chomsky, On certain formal properties of grammars. Inf. Control 2, 137–167 (1959)
A. Church, A note on the entscheidungsproblem. J. Symb. Log. 1(1), 40–41 (1936)
A. Church, An unsolvable problem of elementary number. Am. J. Math. 58(2), 345–363 (1936)
J. Dassow, G. Păun, Regulated Rewriting in Formal Language Theory (Springer, Berlin, 1989)
S. Ginsburg, S.A. Greibach, M. Harrison, One-way stack automata. J. ACM 14(2), 389–418 (1967)
D. Kolář, A. Meduna, Regulated pushdown automata. Acta Cybernetica 2000(4), 653–664 (2000)
H.C.M. Kleijn, G. Rozenberg, On the generative power of regular pattern grammars. Acta Informatica 20, 391–411 (1983)
A.A. Markov, The theory of algorithms. Am. Math. Soc. Trans. 2(15), 1–14 (1960)
A. Meduna, Automata and Languages: Theory and Applications (Springer, London, 2000)
A. Meduna, Simultaneously one-turn two-pushdown automata. Int. J. Comput. Math. 2003(80), 679–687 (2003)
A. Meduna, Two-way metalinear PC grammar systems and their descriptional complexity. Acta Cybernetica 2004(16), 385–397 (2004)
A. Meduna, Formal Languages and Computation: Models and Their Applications (Taylor & Francis, New York, 2014)
P. Prusinkiewicz, M. Hammel, J. Hanan, R. Měch, L-systems: From the theory to visual models of plants, in Proceedings of the 2nd CSIRO Symposium on Computational Challenges in Life Sciences (CSIRO Publishing, Collingwood, Victoria, Australia, 1996)
P. Prusinkiewicz, A. Lindenmayer, The Algorithmic Beauty of Plants (Springer, New York, 1990)
E. Post, Formal reductions of the general combinatorial decision problem. Am. J. Math. 65(2), 197–215 (1943)
H. Rogers, Theory of Recursive Functions and Effective Computability (MIT Press, Cambridge, 1987)
G. Rozenberg, A. Salomaa, Mathematical Theory of L Systems (Academic Press, Orlando, 1980)
G. Rozenberg, A. Salomaa, The Book of L (Springer, New York, 1986)
G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1: Word, Language, Grammar (Springer, New York, 1997)
A. Salomaa, Formal Languages (Academic Press, London, 1973)
A.M. Turing, On computable numbers, with an application to the entscheidungsproblem. Proc. Lond. Math. Soc. 42(2), 230–265 (1936)
D. Wood, Theory of Computation: A Primer (Addison-Wesley, Boston, 1987)
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this chapter
Cite this chapter
Meduna, A., Soukup, O. (2017). Formal Language Theory: Basics. In: Modern Language Models and Computation. Springer, Cham. https://doi.org/10.1007/978-3-319-63100-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-63100-4_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-63099-1
Online ISBN: 978-3-319-63100-4
eBook Packages: Computer ScienceComputer Science (R0)