Bibliographic record and links to related information available from the Library of Congress catalog.

**Note:** Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.

Contents Preface 1 Review of Formal Languages and Automata Theory 1.1 Sets 1.2 Symbols, strings and languages 1.3 Regular expressions and regular languages 1.4 Finite automata 1.5 Context-free grammars and languages 1.6 Turing machines 1.7 Unsolvability 1.8 Complexity theory 1.9 Exercises 1.10 Projects 1.11 Research problems 1.12 Notes on Chapter 1 2 Combinatorics on words 2.1 Basics 2.2 Morphisms 2.3 The theorems of Lyndon-Sch¿utzenberger 2.4 Conjugates and borders 2.5 Repetitions in strings 2.6 Applications of the Thue-Morse sequence and squarefree strings 2.6.1 The Tarry-Escott problem 2.6.2 Certain infinite products 2.6.3 Chess and music 2.6.4 The Burnside problem 2.7 Exercises 2.8 Projects 2.9 Research Problems 2.10 Notes on Chapter 2 3 Finite automata and regular languages 3.1 Moore and Mealy machines 3.2 Quotients 3.3 Morphisms and substitutions 3.4 Advanced closure properties of regular languages 3.5 Transducers 3.6 Two-way finite automata 3.7 The transformation automaton 3.8 Automata, graphs, and Boolean matrices 3.9 The Myhill-Nerode theorem 3.10 Minimization of finite automata 3.11 State complexity 3.12 Partial orders and regular languages 3.13 Exercises 3.14 Projects 3.15 Research problems 3.16 Notes on Chapter 3 4 Context-free grammars and languages 4.1 Closure properties 4.2 Unary context-free languages 4.3 Ogden's lemma 4.4 Applications of Ogden's lemma 4.5 The interchange lemma 4.6 Parikh's theorem 4.7 Deterministic context-free languages 4.8 Linear languages 4.9 Exercises 4.10 Projects 4.11 Research problems 4.12 Notes on Chapter 4 5 Parsing and Recognition 5.1 Recognition and parsing in general grammars 5.2 Earley's method 5.3 Top-down parsing 5.4 Removing LL(1) conflicts 5.5 Bottom-up parsing 5.6 Exercises 5.7 Projects 5.8 Notes on Chapter 5 6 Turing machines 6.1 Unrestricted grammars 6.2 Kolmogorov complexity 6.3 The incompressibility method 6.4 The busy beaver problem 6.5 The Post correspondence problem 6.6 Unsolvability and context-free languages 6.7 Complexity and regular languages 6.8 Exercises 6.9 Projects 6.10 Research problems 6.11 Notes on Chapter 6 7 Other Language Classes 7.1 Context-sensitive languages 7.2 The Chomsky hierarchy 7.3 2DPDA's and Cook's theorem 7.4 Exercises 7.5 Projects 7.6 Research problems 7.7 Notes on Chapter 7

Library of Congress Subject Headings for this publication:

Formal languages.

Machine theory.