The author of this textbook states his goals thus:

(1) to introduce a student of Computer Science to the need for and the working of mathematical proof; (2)to develop facility with the concepts, notations, and techniques of the theories of Automata, Formal Languages, and Turing machines; and (3) to provide historical perspective on the creation of the computer with a profound understanding of some of its capabilities and limitations.

Without a doubt, Cohen has reached the second goal. I cannot imagine a more readable presentation of the required course on computability. The section titled “Automata Theory” contains chapters on languages, recursive definitions, regular expressions, finite automata, transition graphs, Kleene’s theorem, nondeterminism, finite automata with output, regular languages, nonregular languages, and decidability. Under “Pushdown Automata Theory,” we find chapters on context-free grammars, trees, regular grammars,  Chomsky  normal form, pushdown automata, context-free languages, non–context-free languages, intersection and complement, parsing, and decidability. Under “Turing  Theory,”  the chapters cover Turing machines, Post machines,  Minsky’s  theorem, variations on the Turing machine, recursively enumerable languages, the encoding of Turing machines, the Chomsky hierarchy, and computers. Although this represents a lot of material (“as much of the foundation of this subject as [Cohen has] ever been able to cover in a one-year undergraduate introductory course”), the author concedes that this revision “is still far from a comprehensive account of the discipline.”

As to the first goal, it is certainly true that this volume is mathematically undemanding, but Cohen overstates his case when he claims that “this book is written for students with no presumed background of any kind.” Even if that statement is taken to refer only to mathematical background, it is obviously too broad. In any case, the question is whether one can gain an appreciation of mathematical proof in a diluted mathematical context.

The book is deficient in meeting the third goal of providing a larger perspective. While it offers a good guide to the trees, any image of the forest is often obscured. The chapter introductions are typically too brief. The chapters lack conclusions; they simply end abruptly, not with a bang but with a whimper. The concluding chapter does not provide a conclusion to the book as a whole, other than to say that its subject has retained “its Old World charm.”

Each chapter except the first is followed by exercises, but no solutions are provided. An instructor’s manual is available. The book concludes with a briefly annotated one-page bibliography and a table of theorems, but the main text lacks references.

While this volume does not live up to some of its author’s claims, it provides a good treatment of some formalisms that make up a standard part of the computer science curriculum.