Table of contents for A second course in formal languages and automata theory / Jeffrey Shallit.

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.


Counter
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.