Browse Books

Reviewer: Thomas T Sheehan

It can be reasonably argued that there are three major foundations of computer science: mathematical descriptions of computational devices, the limits of mechanical computation, and the specification of formal languages. It can further be reasonably argued that this book provides a very rigorous, undergraduate-level treatment of all three topics. I assume that the authors did write this text for junior-level courses in the computer science curriculum that are usually found under roughly the same name. If so, they have, for the most part, succeeded. I have one small reservation, and that is given in the final paragraph of this review. Alan Turing defined the limits of the computable in his 1936 paper, ?On computable numbers with an application to the Entscheidungsproblem? [1]. In that paper, Turing described a device that could read and write across an infinite tape, each square of which contained a symbol from some finite alphabet. The device, now referred to as a ?Turing machine,? could manipulate those symbols by some finite and explicit set of rules. Part of Turing?s claim was that anything a human could do by symbolic manipulation, using that set of rules, could also be done by the Turing machine. Underlying Turing machines, however, are simpler abstract computing devices, and the simplest of those, finite automata, are introduced in chapter 2 of this book. While they are relatively simple machines, finite automata form the foundation for many concrete and abstract applications. The state transition diagrams used to describe the dynamic behavior of a class in object-oriented analysis and design are based on finite automata. Finite automata, in turn, lie at the heart of more complex abstract computing devices, such as push-down automata, which are discussed in chapter 6. This discussion of abstract computational devices builds in complexity, leading to chapter 8, which contains a clear and detailed description of a Turing machine, and an introduction to the associated topic of describing the languages that can be defined by computational devices. The following chapter, chapter 9, is an equally lucid discussion of the problem of decidability, with a formal proof of the existence of a problem about Turing machines that no Turing machine can solve. But there are parallel tracks operating here. In chapter 3, the authors neatly tie the topic of abstract computing devices to the topic of regular expressions, which define exactly the same languages that the various forms of automata describe. This is followed, in chapter 4, by an exploration of the properties of those regular languages. And that discussion yields algorithms for answering important questions about automata. One of these, possibly the most important, is the question of minimization: finding an equivalent automaton with the fewest possible states. The following chapter treats context-free grammars, the larger class of languages that play a central role in compiler technology. The final chapters introduce the theory of ?intractability,? and the techniques for determining whether or not a problem can be solved in polynomial time. As promised, this last paragraph will offer my one criticism of an otherwise excellent text. The topics introduced require a great deal of mathematical maturity to appreciate, maturity beyond that found in a course in discrete mathematics. But all too often, computer science undergraduates are expected to deal with these concepts, armed only with that discrete mathematics course. The authors rightly devote several pages in the first chapter to the topic of inductive proofs. And, indeed, the succeeding chapters rely heavily on inductive proofs. But they also rely heavily on a non-trivial level of familiarity with set theory, and I think it would have been useful to offer a similar review of that topic. This shows most clearly in the treatment of homomorphisms, an important part of exploring the closure properties of regular languages, which could have benefited from a formal discussion of both isomorphism and Nerode¿s theorem. Finally, a less mathematically rigorous treatment of many of these topics can be found in ¿Introduction to Computer Theory,¿ by Daniel I. A. Cohen. This is not a criticism of Cohen, who, I think would agree with my assessment. Rather, it is offered as an option to those who would like a gentler introduction to these fundamental topics. Online Computing Reviews Service