Introduction to Automata Theory, Languages, and Computation

(This is a review of the first edition of this book.)

This is another one of those rotten books that is difficult to read even when you already know the subject matter backward and forward.

One of the book's largest problems is its overuse of notation to the point of fetishization. Good notation is an aid to clarity and thought; the notation in this book is clotted and turgid.

The book also contains "applications" that aren't, overcomplicated examples of simple things, and makes the interesting parts dull. Its definition of NP-completeness is nonstandard and its explanation is confusing.

Recommended alternative: Introduction to the Theory of Computation, by Michael Sipser.

I need to make it clear right at the beginning that this is a review of the first (1979) edition of this book. It's my understanding that the second edition is better.
I knew that this book was going to be difficult; it's more advanced than I'm really capable of. Which made it all the more discouraging that very early on (page six), I came across a pretty serious typographical error. Now, with this particular error it was fairly easy for me to figure out what went wrong, and what the correct reading was. But now I have a problem: the next time I come across something that I don't understand, something that seems not to make sense, I won't know, I will have no way of knowing, whether it doesn't make sense because it's an error or if it show more doesn't make sense because I haven't worked hard enough to understand it.
Then I get to the exercises for chapter one. They give answers to selected exercises, those "whose solutions are particularly instructive". Well, the first exercise they give a solution to is of the "prove this statement is true" sort. And I'm pretty sure that, while the statement is true, the proof they offer in the solution is not complete.
These are problems that make this book highly frustrating for me. show less

A strong text, but quite formal. Not the most readable.

Este libro cubre todo lo referido a la teoría de autómatas existente. Con un tratamiento sólido en la construcción de pruebas, gran número de figuras y diagramas.