Introduction to Automata Theory, Languages, and Computation (2nd Edition)

This classic book on formal languages, automata theory, and computational complexity has been updated to present theoretical concepts in a concise and straightforward manner with the increase of hands-on, practical applications. This new edition comes with Gradiance, an online assessment tool developed for computer science.

Gradiance is the most advanced online assessment tool developed for the computer science discipline. With its innovative underlying technology, Gradiance turns basic homework assignments and programming labs into an interactive learning experience for students. By using a series of “root questions” and hints, it not only tests a student’s capability, but actually simulates a one-on-one teacher-student tutorial that allows for the student to more easily learn the material. Through the programming labs, instructors are capable of testing, tracking, and honing their students’ skills, both in terms of syntax and semantics, with an unprecedented level of assessment never before offered.

I would give four stars, should I keep in heavy account the radical changes they made over the first edition and that includes the removal of some stuff, important on my opinion. But ... this is just my opinion, and since it is a very well written and informative book (rich of many details that other texts lack of) and surely one of the bests in the area (I've had 4-5 books in my hands for this course), that's why I gave it 5 stars.


Need some challenge? Come here!   November 29, 2004
F. Li
13 out of 15 found this review helpful

I started to learn this course at the beginning of this semester and I just brought this book from Amazon in August.
I had no introductory course before but I was so curious about this subject so I am taking this graduate level course.
Now, I am in chapter 10, and I would like to give a review of this book.
This book is well organized, from the beginning to the end.
I have read almost each word in this book(including the extra ones in the box), and I would like to say: It is worth to do that.
Although sometimes the sentences are not very clear(maybe because I am an international student), but almost all the ideas are precious. So, please be patient when you are reading.
Trust me, if you do not have any related course before, you need time for it. but if you can understand all the contents in this book, and if you are more energetic, finishing most of the exercise with excalmatory marks, you will find your mind becomes so clear that is beyond your imagination.
For the tests, if there are some in your class, is only a half piece of cake. you will feel 100 points is just for the left hand(given the condition that you are a right-hander). :)
If you buy an international version, prepare to visit the book's website. and I will say this second edition seems to me the -1th edition because it contains all the errors listed on the website. Prepare you pen and become a co-auther of the book.
If you feel you need to improve your mathematics, take it, because reading this book can improve your mathematical thinking and proof ability tremendously.
If you feel all the course in your university is too easy and can not match your intelligence, take it, then you will find something interesting.


A book for computer scientists   April 14, 1999
10 out of 11 found this review helpful

A predecessor of the book was published in 1969 titled "Formal Languages and Their Relation to Automata." It was re-written in 1979. This is a classical textbook for last year undergraduate students or postgraduate students in computer science, especially those who are going to deal with computer languages, artificial intellegence, compiler design, computational complexity and so on. One of the author, J. E. Hopcroft, is the Turing Award winner of 1987.

I have both versions of the book and I'd like recommend every computer science student spend some time on reading it.


Very useful book for GRE CS Subject preparation (part III)   June 5, 2001
Mihailo Despotovic (Silicon Valley, CA USA)
7 out of 7 found this review helpful

I needed a book which would speed me up with my GRE computer science subject test (part III: Theory). Having non US and non english language based Bachelor Degrees in CS and Math, I needed something to both learn the more precise terminology and at the same time to gather my prevous knoweldge of the subject. After little bit of browsing and examining of reviews, book contents and browsing pages in bookstores, I decided to buy this one.

I admit that I had a solid knowledge of almost all chapters of the book and that the book might be hard to swallow for someone who is not a little bit familiar in mathematical logic and elementary math but otherwise, the book is excellent. Even authors admit that previous editions were more demanding and in this one they introduced many easier examples and appropriate pictures and diagrams so I really did not have any problems understanding every concept.

After each chapter exercises are given and while they are useful, I would prefer solutions embedded into the book (as in Knuth's Art of Programming). Rather that doing that, authors put solutions (to selected exercises) on their web page which is not bad but the book would be more complete (and probably more expensive) with solutions inside. I would pay $20 more for that version though...

I also must say that I really appreciate hard cover and excellent quality paper (these unfortunately raised the price)

Overall, this is an excellent book and if you are in a similar situation as me, I would recommend this one.


This is the book.   August 22, 2001
Bob Carpenter (New York, NY)
14 out of 17 found this review helpful

This is the one book that I refer to time and time again for all of my automata-theory needs. It covers all the fundamental theorems of finite-state automata such as determinization and the pumping lemma in a clear, concise manner. Excellent coverage of context-free grammars, with excursions into generative power, normalization and parsing. The book is rigorously mathematical, yet easy to understand.

I came to this book fifteen years ago as a grad student after reading Lewis and Papadimitriou (which is good, but overly detailed on notation where context would suffice), used it as a professor teaching automata theory at Carnegie Mellon, and now use it as a software engineer for a speech recognition company that builds grammars.