16 of 17 people found the following review helpful
One step forward, two steps back,
By A Customer
This review is from: Introduction to Automata Theory, Languages, and Computation (2nd Edition) (Hardcover)
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.