Browse Books

Reviewer: Robert Stewart Roos

The latest edition of Linz’s theory textbook follows the same outline as the previous one: it begins with a chapter on mathematical preliminaries; moves through the Chomsky hierarchy (regular, context-free, and recursively enumerable languages, with a brief mention of context-sensitive languages); and concludes with one chapter each on the topics of undecidability, alternate models of computation, and complexity classes. The presentation is fairly conventional: introduce the new concept, give formal definitions, provide examples, give mathematical justifications (usually complete proofs, although some proofs are omitted or given in outline only), and end with a set of exercises. Solutions to some of the exercises appear in the appendix. While such an approach tends to be a bit dry, it is fine for instructors who are accustomed to this format, and who can infuse the material with sufficient excitement and enthusiasm. The presentation is fairly straightforward and readable, especially for what is essentially a mathematics text. The author identifies the book’s intended audience as sophomore or junior computer science/computer engineering students, with some background in programming, data structures, and discrete mathematics. For students likely to pursue more advanced study in theoretical topics, the presentation is appropriate; for students who are more inclined to pursue software development or other applications, the motivation for some topics is lacking. To take just one example, Linz mentions the vi editor as a program that uses regular operators. Perhaps students would be more pleased to learn about the existence of regular expression packages in scripting languages such as Perl and Python, or would appreciate seeing examples of the Unix grep command for file searching. More than anything else, the book needs to provide readers with a broader framework that naturally motivates the many topics covered. Instructors looking for a general reference on automata and formal languages, or a textbook for a mathematically sophisticated audience, should take note that Linz’s book lacks a comprehensive bibliography (the one-page list of references consists primarily of other theory textbooks). Purists might complain about the absence of the Myhill-Nerode theorem in the optional section on state minimization of finite automata. There is nothing about Ogden’s lemma, Moore versus Mealy machines, and a number of other topics that used to be standard in texts on the theory of computation. Cook’s theorem is stated, but not proved. These observations should not be taken as criticisms of the book’s suitability as an introductory text, but are aimed at readers looking for a more comprehensive treatment of the theory of computation. Overall, the work is appropriate for the author’s stated purpose: a textbook for an introductory undergraduate course on the theory of computation—provided that the students have sufficient mathematical preparation. Online Computing Reviews Service