An Introduction to the Theory of Formal Languages and Automata

| Max Planck Institute for Psycholinguistics, Nijmegen
PaperbackAvailable
ISBN 9789027232502 | EUR 29.00 | USD 43.95
 
e-Book
ISBN 9789027290076 | EUR 29.00 | USD 43.95
 
The present text is a re-edition of Volume I of Formal Grammars in Linguistics and Psycholinguistics, a three-volume work published in 1974. This volume is an entirely self-contained introduction to the theory of formal grammars and automata, which hasn’t lost any of its relevance. Of course, major new developments have seen the light since this introduction was first published, but it still provides the indispensible basic notions from which later work proceeded. The author’s reasons for writing this text are still relevant: an introduction that does not suppose an acquaintance with sophisticated mathematical theories and methods, that is intended specifically for linguists and psycholinguists (thus including such topics as learnability and probabilistic grammars), and that provides students of language with a reference text for the basic notions in the theory of formal grammars and automata, as they keep being referred to in linguistic and psycholinguistic publications; the subject index of this introduction can be used to find definitions of a wide range of technical terms. An appendix has been added with further references to some of the core new developments since this book originally appeared.
[Not in series, 143]  2008.  xi, 139 pp.
Publishing status: Available
Table of Contents
Preface
ix–xi
Chapter 1. Grammars as formal systems
1–7
Chapter 2. The hierarchy of grammars
9–32
Chapter 3. Probabilistic grammars
33–48
Chapter 4. Finite automata
49–67
Chapter 5. Push-down automata
69–83
Chapter 6. Linear-bounded automata
85–93
Chapter 7. Turing machines
95–107
Chapter 8. Grammatical inference
109–123
Historical and bibliographical remarks
125–127
Appendix: Some references to new developments
129–130
Bibliography
131–133
Index of authors
135
Index of subjects
137–139
“[A] wonderful resource for linguistics students, especially those interested in syntax and semantics, and students from computer science interested in computational linguistics (also called natural language processing). This book will surely help to revive the strong connections between these two disciplines, which have been on the wane since the mid-1990s.”
Cited by

Cited by other publications

Abid, Muhammad Rizwan, Emil M. Petriu & Ehsan Amjadian
2015. Dynamic Sign Language Recognition for Smart Home Interactive Application Using Stochastic Linear Formal Grammar. IEEE Transactions on Instrumentation and Measurement 64:3  pp. 596 ff. Crossref logo
Asano, Rie, Pia Bornus, Justin T. Craft, Sarah Dolscheid, Sarah E. M. Faber, Viviana Haase, Marvin Heimerich, Radha Kopparti, Marit Lobben, Ayumi M. Osawa, Kendra Oudyk, Patrick C. Trettenbrein, Timo Varelmann, Simon Wehrle, Runa Ya, Martine Grice & Kai Vogeley
2018. Spring School on Language, Music, and Cognition. Music & Science 1  pp. 205920431879883 ff. Crossref logo
Buckingham, Hugh W. & Sarah S. Christman
2010. Charles Darwin and the Evolution of Human Grammatical Systems. Journal of the History of the Neurosciences 19:2  pp. 121 ff. Crossref logo
Nowak, Iga & Giosuè Baggio
2017. Developmental Constraints on Learning Artificial Grammars with Fixed, Flexible and Free Word Order. Frontiers in Psychology 8 Crossref logo

This list is based on CrossRef data as of 23 january 2020. Please note that it may not be complete. Sources presented here have been supplied by the respective publishers. Any errors therein should be reported to them.

Subjects
BIC Subject: CFK – Grammar, syntax
BISAC Subject: LAN009000 – LANGUAGE ARTS & DISCIPLINES / Linguistics / General
U.S. Library of Congress Control Number:  2008027330