An Introduction to the Theory of Formal Languages and Automata (Not in series)

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. An Introduction to the Theory of Formal Languages and Automata 2 Title page 4 LCC data 5 Dedication 6 Table of contents 8 Preface 10 Chapter 1. Grammars as formal systems 14 Chapter 2. The hierarchy of grammars 22 Chapter 3. Probabilistic grammars 46 Chapter 4. Finite automata 62 Chapter 5. Push-down automata 82 Chapter 6. Linear bounded automata 98 Chapter 7. Turing machines 108 Chapter 8. Grammatical inference 122 Historical and bibliographical remarks 138 Appendix 142 Bibliography 144 Index of authors 148 Index of subjects 150 Willem J.m. Levelt. Includes Bibliographical References (p. [131]-133) And Index.