01 / Classic Textbook Recommendation
Classic Textbook Recommendation
Who this book is for
Undergraduates taking a first course in theory of computation or formal languages, usually in the second or third year of a computer science degree. It is aimed at students who find terse, highly formal treatments difficult, since central ideas are introduced through motivating examples before the definitions and theorems are stated.
Prerequisites
Discrete mathematics, including sets, functions, relations, graphs and proof by induction, plus some programming experience.
What it covers
Mathematical preliminaries; deterministic and nondeterministic finite automata; regular languages, regular expressions and regular grammars; properties of regular languages and the pumping lemma; context-free languages and grammars, simplification and normal forms; pushdown automata; properties of context-free languages; Turing machines and the Turing thesis; other models of computation; recursively enumerable languages and the Chomsky hierarchy; limits of algorithmic computation; an introduction to complexity; and, new in this edition, applications to parsing.
How to use it
Read each section with its motivating example, then attempt the introductory exercises before the harder problems. Draw automata and trace their behaviour on sample inputs by hand or with a simulator. The parsing chapters can be read alongside a compilers course to see the theory applied.
Edition and sources
Seventh edition, published by Jones & Bartlett Learning in 2022 with a 2023 copyright date (ISBN 9781284231601); it adds three chapters on parsing. Bibliographic data for this record comes from the Jones & Bartlett Learning product page, cross-checked with Google Books.