Preface | p. ix |
Review of formal languages and automata theory | p. 1 |
Sets | p. 1 |
Symbols, strings, and languages | p. 1 |
Regular expressions and regular languages | p. 3 |
Finite automata | p. 4 |
Context-free grammars and languages | p. 8 |
Turning machines | p. 13 |
Unsolvability | p. 17 |
Complexity theory | p. 19 |
Exercises | p. 21 |
Projects | p. 26 |
Research problems | p. 26 |
Notes on Chapter 1 | p. 26 |
Combinatorics on words | p. 28 |
Basics | p. 28 |
Morphisms | p. 29 |
The theorems of Lyndon-Schutzenberger | p. 30 |
Conjugates and borders | p. 34 |
Repetitions in strings | p. 37 |
Applications of the Thue-Morse sequence and squarefree strings | p. 40 |
Exercises | p. 43 |
Projects | p. 47 |
Research problems | p. 47 |
Notes on Chapter 2 | p. 47 |
Finite automata and regular languages | p. 49 |
Moore and Mealy machines | p. 49 |
Quotients | p. 52 |
Morphisms and substitutions | p. 54 |
Advanced closure properties of regular languages | p. 58 |
Transducers | p. 61 |
Two-way finite automata | p. 65 |
The transformation automaton | p. 71 |
Automata, graphs, and Boolean matrices | p. 73 |
The Myhill-Nerode theorem | p. 77 |
Minimization of finite automata | p. 81 |
State complexity | p. 89 |
Partial orders and regular languages | p. 92 |
Exercises | p. 95 |
Projects | p. 105 |
Research problems | p. 105 |
Notes on Chapter 3 | p. 106 |
Context-free grammars and languages | p. 108 |
Closure properties | p. 108 |
Unary context-free languages | p. 111 |
Ogden's lemma | p. 112 |
Applications of Ogden's lemma | p. 114 |
The interchange lemma | p. 118 |
Parikh's theorem | p. 121 |
Deterministic context-free languages | p. 126 |
Linear languages | p. 130 |
Exercises | p. 132 |
Projects | p. 138 |
Research problems | p. 138 |
Notes on Chapter 4 | p. 138 |
Parsing and recognition | p. 140 |
Recognition and parsing in general grammars | p. 141 |
Earley's method | p. 144 |
Top-down parsing | p. 152 |
Removing LL(1) conflicts | p. 161 |
Bottom-up parsing | p. 163 |
Exercises | p. 172 |
Projects | p. 173 |
Notes on Chapter 5 | p. 173 |
Turing machines | p. 174 |
Unrestricted grammars | p. 174 |
Kolmogorov complexity | p. 177 |
The incompressibility method | p. 180 |
The busy beaver problem | p. 183 |
The Post correspondence problem | p. 186 |
Unsolvability and context-free languages | p. 190 |
Complexity and regular languages | p. 193 |
Exercises | p. 198 |
Projects | p. 200 |
Research problems | p. 200 |
Notes on Chapter 6 | p. 200 |
Other language classes | p. 202 |
Context-sensitive languages | p. 202 |
The Chomsky hierarchy | p. 212 |
2DPDAs and Cook's theorem | p. 213 |
Exercises | p. 221 |
Projects | p. 222 |
Research problems | p. 222 |
Notes on Chapter 7 | p. 223 |
Bibliography | p. 225 |
Index | p. 233 |
Table of Contents provided by Ingram. All Rights Reserved. |