From the preface: “This book concentrates on the fundamental models for languages and computation together with their properties. The models are finite automata, regular expressions, context-free grammars, pushdown automat, Turing machines, and transducers. The properties that are presented are family relationships (the relative power of the models), closure properties, decidability properties, and complexity properties.
Throughout the text, algorithms are given in a PASCAL-like notation, since there is an emphasis on constructions and programming. There is also an emphasis on practical applications throughout the text; for example, finite automata and pattern matching, regular expressions and text editing, extended context-free grammars and syntax diagrams, finite transducers and data compression.
Each chapter terminates with a summary of the material, its history, and a springboard; the last two items include references to the current literature.
The text consists of four parts. Preliminaries are dealt with in Part I. Chapter 0 reviews sets, relations, graphs, functions, enumerability, and proof techniques. Chapter 1 introduces decision problems, formal languages, and their relationship.
Part II presents five models for languages and computation in Chapters 2- 6: finite automata, regular expressions, context-free grammars, pushdown automata, and Turing machines. Chapters 2-6 are written to be order- independent to a large extent. In Chapter 7 these models are adapted for relations and functions. It presents finite transducers (from finite automata), translation grammars (from context-free grammars), pushdown transducers (from pushdown automata), and Turing transducers (from Turing machines). Turing transducers give rise to Turing-computable functions, the largest known class of computable functions. Finally, primitive recursive functions and recursive functions are introduced as an alternative method of specifying functions.
Part III covers the fundamental properties of the models. Chapter 8 explores the relative expressive power of the models, that is, family relationships. Chapter 9 investigates how instances of each model can be formed using a building block approach, that is, the closure properties of the associated language families. Decision problems for the models are studied in Chapter 10. Both basic decidable and undecidable problems are considered.
Part IV explores some further topics in a single chapter, Chapter 11. The topics are NP-completeness, general grammars, and parsing.”