Pages: 634 Format: Paperback Amazon Availability: Usually ships in 24 hours Customer Rating:
Also Shop International: (Not all items available internationally)
Introduction to Computer Theory Editorial Review: This text strikes a good balance between rigor and an intuitive approach to computer theory. Covers all the topics needed by computer scientists with a sometimes humorous approach that reviewers found "refreshing". It is easy to read and the coverage of mathematics is fairly simple so readers do not have to worry about proving theorems.
Customer Reviews: The most readable book on computation theory ever written I have taught a course in computation theory for computer science majors for almost two decades. Before the first time, I had never had any of the material in a course so I was required to learn the material on my own. This was the book that I used. For about a month, I set aside a block of time each day and went through the material section by section. When I had completed each section, I would work a few of the problems and would not move on until I understood what the answers should be.
The coverage is:
*) Deterministic and nondeterministic finite automata
*) Regular expressions
*) Context-free grammars and languages
*) Chomsky normal form
*) Pushdown automata
*) Turing machines
*) Post machines
*) The relationship between machines and computers
When it came time to teach the class for the first time, it all went very smoothly. This remains the most readable book for the self-study of computation theory that I have ever seen. Cohen has written a later, more concise edition and that is what I have been using as the text in my course.
Great introduction to theory of computing I read it during my undergraduate, it was the course book for the thoery of automata course. More recently when I tried the popular "Introduction to Automata Theory, Languages, and Computation" by Hopcroft et al. for the purpose of revising the concepts, I realized how great this book is. It is definitely a better book than Hopcroft et al's, with in-depth explanations of all topics, lots of examples and exercises and in a writing style very friendly for the novice readers. Very good work!
Excellent, Accessible Book This an excellent book. Basically, the whole point of it is to mathematically define what a computer is and prove that it works. The author does this by defining and manipulating mathematical alphabets and languages without resorting to any kind of advanced math. Starting from nothing, the whole thing leads up to Turing Machines. More specifically, according to the Preface, the goals of the book are:
"(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."
The author did a wonderful job of it. Plus, unlike almost all other computer/math books I've read, this book is almost enjoyable to read. Again, as stated in the Preface:
"This book is written for students with no presumed background of any kind. Every mathematical concept used is introduced from scratch. Extensive examples and illustrations spell out everything in detail to avoid any possibility of confusion."
Astonishingly, those are all true statements. At a guess, I'd say that almost anyone interested in computers could get through this book without undue stress. To make it more meaningful, I'd suggest (only suggest) prerequisites of having programmed a computer and knowing some discrete math. From that point of view, it's odd that as of last year, this book was used in Florida State University's (FSU's) COT 4420: "Theory of Computation" course, which, obviously, is a 4000 level course requiring various prerequisites that put it out of the reach of all but senior (or graduate) level students.
Now, with all that glowing out of the way, there are a couple of small problems with the book. The first is simply that the exercises don't have any solutions. For the self-studyer, that's a bad thing. In a school teaching environment, it's probably acceptable, though. The second problem is that after getting through the book, I simply have to ask: "So what? WHY should I learn this?" Again, in the Preface, the author states:
"Leaving aside the obvious worth of knowledge for its own sake, the terminology, notations, and techniques of Computer Theory are necessary in the teaching of courses on computer design, Artificial Intelligence, the analysis of algorithms, and so forth. Of all the programming skills undergraduate students learn, two of the most important are the abilities to recognize and manipulate context-free grammars and to understand the power of the recursive interaction of parts of a procedure. Very little can be accomplished if each advanced course has to begin at the level of defining rules of production and derivations."
But, in my experience, I have to say that except for one reference in one other book I've read, I've never seen any of this stuff used. Even more, I've never known anyone who even knew of anyone who used (or even knew of) any of it. EVERYTHING has been done at a much higher level of abstraction than alphabets, languages, and various levels of algorithms and machines up to Turing Machines. I'm not saying that the material in this book isn't used SOMEWHERE. But, I'd honestly have liked to have seen actual, specific, concrete cases: they'd be fascinating.
So, factoring those two nits in, I rate this book at 4 stars out of 5. If those two things don't bother you, then you could easily consider this a 5 star book.
Excellent I must say this is one of the best books I have ever read. The auther is humorous and insightful. He manages to take very abstract concepts and explain them in clear concrete terms and metaphors.
Discursive presentation. Helpful for novices. The book has one important attribute: it's clear, undoubtedly. Having a minimum of prerequisites, I think there's no way to not understand what Prof. Cohen says through its pages. It makes the job of learning this part of theory easier than any other text. But ... but I can't totally agree with Cohen's crusade against formalism. I agree that the first target of a book should be to clearly transmit the intended knowledge, and Cohen perfectly succeeds in this. But formalism too has its importance, thereafter. A compact and clear formalism helps to communicate efficiently, and moreover unambiguously. Like in mathematics, the first, important thing is to understand. Yet, there's no way for you to efficiently work with math without using any kind of formalism, should it be more or less "standard". That's it: a very powerful book for a "profound" understanding of the subject; a bit more of natural formalism would make it a "complete" understanding also, and the book a five stars one.
Closer Look
