Rating: 
Summary: One step forward, two steps back
Review: This second edition of the classic text tries desperately to be more accessible to beginners than the first edition was, but the results are disappointing. In terms of clarity, the Sipser book still beats this one hands-down.The authors seem to have assumed that the more words they use to explain a concept, the easier it is to understand. Unfortunately the reverse is often true. For instance, in the beginning of the chapter on Turing machines is an extremely long, drawn-out example of an undecidable problem. The example is based on a C program that tries to solve Fermat's last theorem and prints "hello, world" when it finds an answer. If this sounds weird to you, you are not alone. I dare anyone who doesn't already comprehend undecidability to be enlightened by this example as it drags on for nearly 10 pages. That said, overall the book does a respectable job of presenting the material, and if you are patient enough to muddle through the murkier sections you will gain a solid understanding. I especially like the fact that solutions to selected exercises are available on the authors' web site. But if you have a choice, start with the Sipser book as an introduction, and pick up a used copy of the first edition of Hopcroft and Ullman to use as a reference. Use this second edition as a backup, for alternative explanations of key concepts, or for a broader set of exercises and problems.
Rating: 
Summary: Five-star reference, one-star textbook
Review: This slim volume is the standard reference for research in automata theory, languages, and computation (especially regular and context-free languages). For that, it gets five stars. As a textbook for students, however, it is dense, uneven, and confusing throughout. Generations of novice computer scientists have been soured forever on theory by being forced to endure this book in their undergraduate- and graduate-level theory courses. Conclusion: buy this book and keep it on your shelf, with the other essential references, but if you want to *learn* the material, look elsewhere -- for example, Michael Sipser's excellent new textbook, _Introduction to the Theory of Computation_.
Rating: 
Summary: Excellent introductory text, but has several weaknesses
Review: This was my textbook for an introductory course on Finite Automata and Languages - I enjoyed it a lot and I think that the chapters until the Turing Machines are covered very well, along with good examples. As one previous reviewer has already mentioned, the exercises can get very hard as compared to what's actually presented - this I found not too good. The topics of complexity classes and NP-Completeness, as well as the chapter on Turing Machines are rather succint and do not cover the full depth. Papadimitriou's "Computational Complexity" does a better job in this respect, even though it is not at all flawless. Some might say that there is a reason why this book is introductory, but I argue that instead of doing a poor job, the authors should have maybe just made another book dealing with the above-mentioned topics. PS: My professor told me that the first edition was much better - maybe you could find it somewhere in the library, if interested.
| 
