Customer Reviews

Introduction to Computer Theory

5 star:		(7)
4 star:		(3)
3 star:		(0)
2 star:		(0)
1 star:		(0)

 

 

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.

This book is great. It gives a completely different approach to atomata theory and computability than Aho and Ullman's book. The the latter has demostrations from an algebraic point of view, the former gives constructive demostrations which are usually more understandable to me. This is a great introduction to computer theory and I would recommend it instead of Aho's book as a first encounter with these themes.

This is a great book. I read the first edition many years ago, and it too was great. Everything is explained in order, and explained well - it is very accessable, even to the casual reader interested in the topics presented. It was through this book that I was able to actually write software that demonstrated Kleene's Theorem, (RE=NFA=DFA) converting between Regular Expressions, NFA's and DFA's.

Unlike many textbooks, reading this one is actually FUN. By the time I was done, I felt that I understood everything that was presented. That's how good this text is.

// CHRIS (Darien, Connecticut)

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.

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.

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!

This is one of the best textbooks I've ever read. It is CLEAR in the explanation of abstract theories and explains everything you'll ever need to know about pushdown automata theory, Turing theory, and more. This book is written in a language that can be understood by everybody and if that's not enough contains extremely helpful diagrams.

The only thing that is better than the book is to be in Dr. Cohen's class. Thank you, Dr. Cohen, for the unforgettable experience.

This book ended up being pretty out dated and boring. For my course it was only useful as a supplementary material. Fortunately the teacher's notes were designed in mind with this book being out dated, and the only reason it was chosen because it is thorough in its explanation.

this is good book with good exercise stuff but i want the answers for its exercise without answers it is incomplete can you please send me the answers if possible

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.