Introduction to the Theory of Computation, Second Edition Reviews

• Absolutely Amazing

  
  By A39UWP91J5MQGE on 2001-07-19
  When I picked up this book I thought, "You have to be kidding me." This book is very thin, and then a fair chunk of it is mathematics review for some of the formal arguments the book is going to be making later on. One wouldn't think there was much in this book.

  One would be wrong. This book goes into rather impressive depth on some rather abstract concepts of computer science without dabbling for too long in the details. It does the best job I've ever seen of explaining the Turing machine and how it relates to computability and decidablity.

  The exercises are both easy and insanely difficult - so you can basically chose your level and then go through the book, some of the problems are very hard, some are trivially easy, a great mix makes for great homework assignments.

  The "Proof Idea:" sections before every proof give you the underlying concepts in plain english that are about to be stated formally so you have a clue what's happening when the formal definitions start flying. These are priceless and should be included in every other book that uses formal proof techniques.

  The book reads fairly well on its own, or makes for a great class text book, which I used it for. As my professor said, "This is a good book because it doesn't have any extra words." but you don't seem to mind as you read it. Probably the best work on the science of computation in the world, certainly the best I've ever seen.
  
  

• Makes the study of Formal Langs amenable to bedtime reading!

  
  By A3I3FPEP3L4ISO on 2000-08-13
  Summary of this review: You'll find yourself getting interested in, and understanding, concepts, very easily, but if you're an advanced reader you'll often find (at the end of the chapters) that the more advanced topics/problems have been glossed over.

  If this is your assigned course textbook, you're lucky. If this is NOT your assigned textbook, USE it as your guide. It makes topics simpler and more intuitive. The way Sipser ropes down exotic theorems into straightforward, understandable logic is almost magical. The book scores in most areas: smoothness of flow, ease of understanding, order of presentation, motivational cues, and thoroughness in the areas covered.

  The problem with the book is in the number of topics covered, and in the number of examples. There are not sufficient examples in some cases, and not sufficient material in some cases. This is a small textbook. At the end of each chapter, Sipser often glosses over the more advanced issues. If doing a thorough study, one will frequently need a more complete reference.

  This will, of course, not be a problem if your course does not go beyond what is covered here: Finite Automata, Turing Machines, the relationship between the classes of languages, reducibility, and complexity theory.
  
  

• a lifesaver for all computer science majors!

  
  By on 1999-12-30
  I bought this book in a desperate attempt to pass a Theory of Computation course in which I was enrolled. I was stuck in the sad situation of having a non-English speaking, difficult to understand professor. In addition, the required text for the course was awful. Thanks to Sipser's book, I not only avoided dropping the course, but managed to get an A. (I'm not exagerating). Sipser's book is fantastic compared to others on the subject. It is written in easy to understand, plain, no-nonsense language. (Even the section on pumping lemma is understandable) I became aware of Sipser's book as a result of reading a customer's negative review of another (more expensive) book (Intro to Languages & theory of Computation by J. Martin) on the same subject. The reviewer suggested buying this book by Sipser instead, and that advice was excellent. (Many thanks to that reader, whoever you are!) If you are considering heading for the drop course line at the registrar's office, try this book before you give up and quit!
  
  

• Unbelievable

  
  By A261XOP640FCO8 on 2000-05-30
  Reading this book changed my entire set of beliefs regarding the importance and usefulness of computational theory (and math) in computer science. I have been programming since grade 7, yet only after reading this book do I feel like I really have a grasp of it on a fundamental level. Its like there was this whole other world under my nose that I caught passing glimpses of yet was never able to put together. Like in DOS: c:>dir *, why use a star character? Why is XML the way it is? The list goes on and on. This book tied *alot* of 'loose ends' for me.

  I always felt that being a cs-tist was about programming, object oriented design/analysis, design patterns, UML, etc.. And there is no doubt that mastery of these technologies are required of any good cs-tist. However, if you want to understand where all these technologies you use come from, how they connect, and to get a glimpse of where its all going, you must combine your current programming and trend following expertise with knowledge of the underlying theories of computation.

  This book should be required reading for all first year CS students so that they may get the 'big picture' right from the start and be able to see CS as a whole rather than a bunch of 'kinda related' courses. I see this book inspiring a whole generation of cs-tists - many of whom may have gone into other professions after reading books like 'Introduction to Automata Theory, Languages, and Computation' by Ullman, Hopcroft (a great, rigorous treatment of cs, but *not* a good book to learn from or be inspired by).

  Again, great book!
  
  

• Most appropriate for CS students

  
  By A3H4K34OZGOCM8 on 2006-05-31
  As a teacher of the subject, I have had the chance to evaluate numerous books on the theory of computation. Of all the available texts, I think this one is the most appropriate for CS students. In the past I taught out of Dexter Kozen's book, which is incredibly elegant, but had some resistance from the students. Thinking it over I decided that Kozen's text, although beautiful, may be better suited to students pursuing a degree in pure math. Sipser's book, on the other hand, is more gentle. I find that Sipser demands far less mathematical maturity from his readers, and thus allows the difficulty to be shifted from excessive formalism to the inherent challenges present in the material. In addition, following Sipser's treatment, I was able to cover finite state machines and pushdown automata in far less time, thus allowing me to concentrate on computability and beyond. The book really shines in its treatment of computability theory, eloquently directing attention to some of the most beautiful aspects.
  
  Another benefit of Sipser's book is the exercises, of which there are many more in this edition. Someone studying on their own should find the initial group of exercises in each section quite approachable. Even the more challenging problems are not incredibly hard, and typically draw their difficulty from the deeper themes of the chapter instead of obscure details.
  
  If you are looking for an enjoyable, well-paced book with an introduction to computability and complexity that is truly inspiring, this is the one for you. A mathematician looking for a bit more rigor may do better with Kozen.
  
  
• misleading
  By A3KJUNLS0S1VKP on 2004-12-16
  yeah, sure, Sipser manages to pack a lot of difficult stuff into a small book and makes it seem easy. think again, you'll find that's because he's not telling you the whole story! a lot of interesting materials are just skipped. For example, Greibach normal form of CFG is nowhere seen in the book, which makes Sipser's explaining of converting CFG to NPDA (lemma 2.13) very uninteresting. Compare with lecture 24 in Kozen's book, you'll see the difference. This book also lacks examples. Without seeing enough examples, you just won't grasp the concepts firmly. That's mainly the reason why the exercises and problems seem so difficult.
  
  I recommend Kozen's "Automata and Computability", Hopcroft and Ullman's "automata, languages, computation" and Papadimitriou's "computational complexity". but not this one.
  
  
• An excellent one-semester intro to theory of computation
  By A2TZ6DETANJ80Q on 2005-04-18
  The theory of computation represents a fascinating landscape that intersects computer science and mathematics and can be roughly divided into three overlapping areas: automata and formal languages, computability theory, and computational complexity. And there is enough interesting knowledge about each area to fill three books, each twice the size of this one. And because of this I find it remarkable that the author has succeeded in filling a slim volume with the essential theory and results from each area, in a style that not only seems very accessible and intuitive, but also demonstrates important relationships between the three areas. For example, most books on computability theory do not discuss automata outside of Turing machines, but in his book Sipser elegantly proves that the equivalence problem is decidable for deterministic finite automata, but undecidable for pushdown automata.
  
  Not only does the author have very good coverage of the three areas, but he also is able to strike a nice balance between mathematical rigor and intuitive understanding. His "proof idea" proof preambles greatly helped my students better understand the main ideas behind each result. In terms of coverage I found only a handful of introductory topics that were neglected: Greibach Normal Form, Rice and Rice-Shapiro Theorems, algebraic aspects of formal languages, Turing degrees, and perhaps context sensitive languages. With that said, remember that this book is just a semester-long introduction to a vast landscape. I recommend the following books for more depth: Peter Linz, "Introduction to Formal Languages and Automata"; Nigel Cutland, "Introduction to Computability Theory"; Christos Papadimitriou, "Computational Complexity".
  
  Another strength of the book is how the author distinguishes exercises and problems: "exercises" are similar to the worked out examples, and can be solved by following one of the presented examples, algorithms or theorems, while "problems" require significant expository writing and deeper insight. Most undergraduates should be able to handle the exercises, but will find the problems very challenging if not impossible, due to the fact that students at this level are mostly familiar with problems that can be solved in a few steps by following some algorithm. So these problems have the capability of developing student intellect, but if assigned in too large a quantity can break the spirit of the developing student. Have care!
  
  I congratulate Dr. Sipser on this fine book. May it inspire millions of readers to question the meaning of computation and explore its possibilities and limitations.
  
  
• Great book
  By AOX78NO876580 on 2002-02-05
  Michael Sipser has an undoubted gift for writing on this subject. The book is a coincise and easy read. But be cautious, this doesn't mean superficial and poor. The book contains all the material needed for a good course on Theory of Computation and Complexity. Perhaps it has not plenty of details like other books as Hopcroft & Ullman or Kozen or Papadimitrou, but don't underestimate the vastity of the treated topics, what is important is that every time you finish a chapter, you have the sensation that you've learned what you should have to. And probably you did due to Sipser's writing style, provided that you can afford to skip "some" more detailed/advanced topics. Or you might just be looking for some further stuff like Myhill-Nerode or Rabin-Shepherdson theorems or Chomsky Hierarchy for example, and you would have to look elsewhere for them. However, I've never been told that the best book is the most complete one. As long as I've learned, the best book is the one that best fits your needs, and that fitting these needs it suceeds to transmit the knowledge you're looking for in an effective way. That's why if this stuff is not required by your course, you would be perfectly fine with this book in your hands.

  Proofs on theorems are given virtually always in two steps: first you're presented with the idea that lies behind the proof, and then you get the proof itself in a more rigorous fashion. Again, Sipser strikes here because it's harder NOT to understand one of his proofs than the contrary simply because the presentation is always clear and understandable.
  As a matter of fact, Sipser (as he point out in the preface) almost always avoid to overload proofs given by construction with more rigorous following proofs (e.g. induction on the constructed machine to prove its equivalence with ...). This has a strong impact on the attention you can keep when studying throghout a chapter: avoiding to dive into tedious details when the proof (by construction) has been clear enough help to keep you attention high and boredom away. This is a way of learning, an effective way.

  Sipser uses sometime a notation that's different from the somewhat standard one (e.g. the description of delta or transition function on various machines), but it is coherent throughout the whole book, and that's what does count, together with the note that this notation is noway more complex or hard to understand than the "standard" one.

  Should I name two books on Theory of Computation (not Complexity), one just a little less rigorous and one just a little more rigorous than this, I would suggest Coehn's "Introduction to computer Theory" and Kozen's "Automata and Computability" respectively.

  My conclusion is that this is a great book, worth the price (especially if confronted with others ...) and a stable place in my bookshelf.
  
  

• Excellent introduction to computer science theory
  By A2U4OQH5AWGMX9 on 2003-10-26
  This book is aimed as an introductory text book on computer science theory. The book is suited for both undergraduate and graduate studies. The first three chapters of the book, regular expressions, context free languages and the church-turing thesis are apt for an introductory class for the undergraduate level. The remaining 7 chapters provide more than enough content for advanced undergraduate or graduate studies.

  This is the first book on computer science theory that I have seen, which is actually written in understandable English. As compared to the previous introductory texts by Hopcroft or Papadimitriou, Sipser shuns writting the entire book using just symbols of formal mathematics. This is not to say that there is no formalism in the book. There is adequate use of formal mathematics in the proofs of the book, but not so much as to scare even in most intrepid readers like in previous books on this subject.The fact I liked most about this book is that every proof in the book is accompanied by a "Proof Idea" which explains using diagrams and plain english how exactly the proof works. This followed by the formal proof. The problems at the end of each chapter are fairly interesting, and some of the * marked problems can be fairly challenging for a first time student.

  Another amazing thing about this book is the amount of content it covers. I would have never expected a book of only 400 pages to cover computer science theory all the way from introductory undergraduate to advanced graduate levels. This is because, the author focusses only on core concepts and strives to make them as clear as possible. For example, this book has only one chapter on regular expressions, while every other book that I have seen has at least 3-4 chapters full of gory details. This is because Sipser does not go into the gory mechanical details of converting DFAs to NFAs, or writing Turing machines and so on, but instead explains just the important concepts and gives a few examples. Also a wealth of information is to be found in the problems at the end of the chapter. Many of these problems like the Myhill-Nerode theorem are of the kind you will find actually proved in other texts, but left as an excercise here. This is because they are relatively simple to prove once all the concepts are understood. Moreover an educator has the option of which of these problems they want to delve deeper into.

  Any student who studies or wishes to study computer science theory should definately get their hands on this book, irrespective of whether they have already used a different book.
  
  

• Appeals to novice and expert
  By AQHKMHVON6460 on 2006-02-28
  I have a long experience with software development, but not much background in computation theory, just fascinating tidbits I have picked up here and there. So, this book for the first time deepens and organizes for me this hightly abstract and difficult topic.
  
  Being a novice, I at first was afraid that the text of the book would be beyond my understanding. It was not. For sure, the proofs are difficult and may appeal to the person with a degree in computer science. But the copious diagrams, figures and tables are wonderful supplements to the understandable text. For the first time I really could grasp the subtleties of the finit automata, non-determinism, regular expressions, pushdown automata and other topics.
  
  Certainly I can recommend this book to the beginner at computation theory, and even to the more advanced student who may want to review the topic.
  
  
• Excellent accessible textbook on the theory of computation
  By A2E3F04ZK7FG66 on 2006-05-09
  The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. The field is divided into two major branches: computability theory and complexity theory, but both branches deal with formal models of computation, and both of these subjects are dealt with in this book. This is an important subject because no matter what leaps forward computers make, something that is proved undecidable and not computable will always be so, thus the theory behind this subject is very important.
  This book is the most readable text on the subject that I have found. If this is a textbook you have been assigned, you are indeed fortunate. If not, this is an outstanding supplement to clarify what is presented in more terse books on the subject. I present the book's contents in the context of the table of contents:
  Chapter 0 is an introduction of concepts and definitions in algorithms and mathematics that you will need know to succeed at understanding the concepts in the rest of this book.
  Chapter 1, "Regular Languages", starts by answering the question "What is a computer?". This begins with a discussion of the simplest of machines, the finite automaton, which is basically a state machine. It turns out that a language is regular if some finite automaton recognizes it. Simple examples that explain the concepts are given.
  Chapter 2, "Context-Free Languages", introduces the pushdown automaton, which is a finite automaton that can make use of a stack containing data in a binary form. The term "pushdown automata" currently refers to abstract computing devices that recognize context-free languages.
  Chapter 3, "The Church Turing Thesis", turns to a more powerful model of computing than has been presented so far called "The Turing Machine". The formal definition of a Turing Machine is given along with examples of problems that can be solved by Turing Machines that could not be solved by the less powerful models.
  Chapter 4, "Decidability", turns to the exploration of the limits of algorithmic solvability. Thus, algorithmic decidability is defined as follows: Given string w, does w belong to the language? The algorithm is not allowed to run into an infinite loop and has to produce a YES/NO answer for any input string after a finite amount of time. The importance of studying this is so that if you find a problem that is algorithmically unsolvable, you know that you must break the problem into smaller solvable portions if it is to be computable.
  Chapter 5, "Reducability", presents a means of proving that a problem is unsolvable. This is done by reducing the first problem into a second problem that can be used to solve the first problem. If this can be done, the first problem is solvable.
  Chapter 6, "Advanced Topics in Computability Theory", delves into several deeper aspects of computability theory. This includes the recursion theorem, logical theories, Turing reducibility, and descriptive complexity.
  Chapter 7, "Time Complexity", is a turn from the previous material. It discusses the idea that even though a problem may be computable in principle, it may not be solvable in practice due to the time required. This chapter attempts to quantify this idea and should be familiar material for any student of the theory of algorithms.
  Chapter 8, "Space Complexity", serves as a study of a further problem in computability. Inordinate amounts of memory requirements may make a problem insolvable in practice.
  Chapter 9,"Intractibility", adds mathematical rigor to the idea of a problem that is computable in theory but not in practice.
  Chapter 10, "Advanced Topics in Complexity Theory", contains sections on approximation algorithms, interactive proof systems, parallel computation, and cryptography from the standpoint of quantifying each problem's computability.
  This book is now in its second edition, but I have examined it and I cannot really figure out why. The material is virtually the same as the first edition. Thus, if you are just buying this book for self-teaching or as a supplement, save yourself some money and go with the first edition if you can find it used. There are no solutions to the exercises, but there are plenty of examples throughout the book. Also, this is such a common textbook, you can usually find the solutions to most of the exercises on the web. You should at least have had a course in discrete mathematics and knowledge of at least one programming language to succeed in understanding this book.
  
  
• Very readable, diverse, and a little sparse
  By A336QE758AE53A on 2006-11-25
  This is a wonderful little gem of a book that presents the theory of computation in a fascinating way. It is targeted at advanced undergraduates in computer science, but assumes remarkably little prior knowledge, making it accessible to nearly anyone. The book covers a lot of ground, including the standard fare of automata, computability, and complexity results, plus some bonus material such as probablistic and parallel complexity, information theory, decidable logical theories, and other topics that are normally left out of introductory books. On top of this, the book is remarkably thin!
  
  The best attribute of Sipser's book, though, is the engaging style. This is an easy book to read. You will not feel like you're running into a brick wall, as is sometimes the case with books on abstract topics. It's not so much that the book is slow or gentle (it's really not) as that it is interesting, engaging, and has a knack for stopping short of getting too caught up in details. A number of small things -- the occasional amusing exercise, the "proof idea" sections, or helpful pictures -- add up to an enjoyable reading experience.
  
  Two cautions are appropriate to students considering this book. First, there are variations between authors in the definitions of various automata (especially PDAs). The differences are trivial, and more a matter of taste than of any real importance; but it could come up if you use Sipser as a supplement to a course that follows a different textbook. Second, the coverage of many topics in Sipser's book is brief and concise, sometimes more than you might like. Some important concepts (for example, pairwise distinguishability of strings) are only mentioned in exercises, not in the main chapter, so at least skim all the exercises even if you don't do them. The sketchy coverage is especially pronounced in advanced topics, so (as always) expect to do some filling in of concepts if you go on into further study of this area.
  
  
• The best!
  By ALIFLQ9OH738B on 2000-09-02
  I had this book in a computer theory course and I looked up similar books in the library looking for extra help and different perspectives. They were all horrible in comparison! No book can make this topic as easy as something hands-on like programming, but this one does the best I can imagine. The proofs are preceded by a "proof idea" that outlines what's going on before you get into the rigorous details. The writing is fluid and discusses the implications of the theorems and why they're important. This gives the reader an appreciation of the topic, which is a rare thing in something this arcane. Even if your course doesn't use this book, I recommend buying it as a supplement. I expect it to become a classic in the field.
  
  
• Technical and Thorough at the Expense of Readability
  By A36T0MYKF1TTUR on 2005-09-28
  This book, while generally pretty complete, seems to have trouble explaining the concepts in anything other than formal definitions and the few "user friendly" explanations that is does give leave quite a bit to be desired. This book would make a great reference for anyone already familiar with the concepts of computability but does little to accommodate readers that are new to the subject. There are some pretty good step by step explanations of more basic subjects like non-deterministic finite automata but the explanations that are given for more complicated topics are very flaky. Take the pumping lemma for example. The book gives a very brief overview, a more formal definition, and then (prematurely) jumps into examples. One key concept, "pumping length," is described simply as "a certain special value." Its meaning is vaguely hinted at on the next page but is never actually stated - formally or in plain English.
  
  
• Life saver
  By on 2000-03-21
  I used this book as a supplement in a college class. It was VERY helpful in understanding computability theory, Turing Machines, and finite languages. Everything is put forth in a straightforward easy to understand manner.

  The main thing that made this book stand out above the rest is that it's written in language that is easily understood, while other text books burden you down with a multitude of symbols and equations. The proof ideas are very helpfull in understanding concepts

  Thank you Mr. Sipser!
  
  

• The material is exposed very clearly
  By on 1999-08-28
  i haven't seen a book on computation theory as clear and easy as this one, it is full of illustrative examples, and PROOF IDEAS..The material is exposed so clearly, that you can read a great amount of material without stopping.. Thanks Michael Sipser for this great book..
  
  
• Clear, Precise, Enjoyable reading. Great Stuff!
  By on 1998-10-29
  One thing I really enjoy is how Sipser motivates every topic with real life examples, connects new topics with the already covered ones, in other words, makes it very easy to read and understand what is going on. This is in contrast to the Hopcroft and Ulman book which is very dry and dense, and in which a reader is not guided from topic to topic; topics are just covered, and the reader has a question ``why?'' (I may be wrong about this...) In any case, I think this is the only book to use both for a class and self-reading.
  
  
• Theory for the Rest of Us
  By on 1998-10-06
  Finally, a clearly-written, concise, and thorough introduction to the essentials of the theory of computation. Beautifully designed, written, and illustrated, this book fills a long-standing need, acutely felt by students forced to use dense reference books (like Hopcroft and Ullman) in order to learn the material. Focusing on essential areas (regular and context-free languages, the Church-Turing Thesis, NP-Complete problems) and dropping deadwood (context-sensitive languages, index languages), this book efficiently guides readers through the material that they need to know, without getting bogged down in irrelevant details. The "Proof Idea" concept is especially refreshing, helping students focus on the meat of a proof, rather than the irrelevant details. I highly recommend this book to teachers, students, and anyone else interested getting a fundamental background in the theory of computation.
  
  
• An Excellent Text
  By A3LZZW3I4N2T5O on 2002-05-13
  I have (comparatively) minimal background in math and only as much programming/compsci as I've managed to teach myself, and yet this book was very approachable and digestable. Sipser has managed to couch even the more difficult material in ways meaningful to non-academics. All you really need is what some books refer to as "Mathematical maturity", ie. you can think symbolically and are more intrigued by new mathematical/logical concepts than you are intimidated.

  For budding CompSci majors or programmers, I highly recommend this book as an introduction to the theoretical topics involved in Computer Science.
  
  

• Terrible, Unbelievably Confusing
  By on 2003-02-09
  I'm confused about how this book got such a good rating. Hmmm. Personally, I think it is the absolute worst book that I have ever read, or should I say "tried" to read. Seldom can I read a page (after chapter 2), or even a paragraph for that matter, without having to read it again . . . and again, trying to figure out what Sipser is trying to say. The book is incredibly difficult to read, has very few "down to earth" examples, and many important topics are ommited - left for the reader as "exercises." For those of you who think I am just a slow learner, my gpa is in excess of 3.9 after more than 5 years of college (I am working on a second degree in Computer Science). If I didn't have to read this book for my Theory class at UGA, I would certainly either send it back for a refund, or throw it in the circular filing cabinet, where I think it belongs. It is obvious that my instructor has never read this book!
  
  
• A book for students looking to go into Grad School only!
  By AI8CH8A9B2YTX on 2005-12-13
  This is a book that should only be read by students if it is required for a course or if they are looking to go to grad school for computer science. This is very dry book on the theory that computer science is based on. This includes: nonderterministic finite automaton, context-free grammars, NP versus P, and most importantly the halting problem. If you don't know what these are you should consider yourself lucky. This is a very overpriced book that is only priced that way because college students are forced to buy it. Don't buy this book unless you really need it.
  
  
• A very good book for beginners on Theory of Computation
  By A1LBNMP46W9L8H on 2002-07-27
  Every Computer Science who wants to do Theory of Computation should have this book. Theory of Computation is not that easy to grasp at first, but after a while you'll like it. However, this book doesn't have a solution companion book, which is very frustrating because no one should expect a senior student to know the right answer to some of the questions in the book as the solutions are tricky sometimes.

  However, this is the only good book on Theory of Computation for beginners, sadly so. It's just not good enough to earn a 5-star.

  I struggled when doing the course with this book because as I was trying to do the questions in the book, I had no references whether I was on the right track or not. And trust me, without the solution book, some instructors don't know how to solve some of the questions either, thus don't expect a student to do it all.

  I don't like the idea of holding back the solution book but only instructors have access to it. What good is it if students can't check or learn from the solution.

  If you have any other good book on Theory of Computation that has an accompanying solution book, please email me, I'll be much interested because Theory of Computation is what I want to pursue in Grad school.
  
  

• Probably the best computation theory text for students
  By on 2004-03-13
  In my opinion this is one of the best written books in the CS discipline, a must have for every computer scientist. The topics are presented clearly, with emphasis in understanding the concept, which most of the times is missed in other books amongst the equation line up of theorems that nobody will further investigate. Probably not comprehensive enough for a researcher of the field, but definately the right text to start on the subject and comprehend the basics, which is more than most students in the CS field will need.
  
  
• Excellent Primer!
  By A2M4PQPBV45U71 on 2004-10-26
  This book is unbelievably effective at getting the students prepared for what Computer Science it's all about. This semester I had the luck to get a great professor who has made clear that mathematics, vis a vis computers, it's not about "pushing symbols" or numbers. It's about understanding what a computer is in its innermost form. This book accomplishes that marvelously. As an undergraduate Computer Science student I find this book to be enlightening. It's one of the best, if not the best, book in the field. The coherence and candid and unassuming tone of the author makes the book much more approachable than most books in the subject. He, the author, understood that most CS people were getting "thrown off" by the lingo and the mathematical assumptions made by so many other authors in the field.
  As a refutal to one reviewer: The fact that this book does not have a solution manual is what makes it SO great! Guess what? In real life, in mathematics there is NO solutions manual! You have to find it by yourself. Most problems in mathematics go without solution for ages, until one person has the epiphany and solves it. Most mathematicians, in as hard as they work and as smart as they are, never discover new proofs or new theories. It's irresponsible to lambast this volume just because "it does not have a solution manual."
  
  
• well-organized, progressive, and understandable
  By A3VI92LMCZW05I on 2007-01-06
  As an intro to the theoretical background to computer science goes, this book is about as readable and approachable as you can get.
  
  It gives a very thorough treatment of the whole theoretical basis, from regular languages and pumping lemmas out through Turing machines and related issues, and on to some interesting language classes (like NP and PSpace-complete).
  
  If there's a single sticking point with the book, it's that it insists on a very strict formalism (ie: everything is proof-based) -- something necessary for the topic, but it sometimes renders the material a bit hard to digest.
  
  
• dont buy this version
  By A15WJ0AS28VMH4 on 2007-10-28
  Go buy an international version which is a lot cheaper than this, and they have the same contents. This version is also printed in Black and White and the paper is really cheap. Don't make a mistake like me buying same product for 90$ more. Again, the only difference between hardcover and softcover(international ver) is the price.
  
  
• A Near Perfect Computer Theory Textbook
  By A24C43KQ4I7BN6 on 2004-01-03
  This book is suitable for beginners and graduate students who want to explor the theory of computation . It explains the hard theory and logic by easy sentences and words. Even if you use English as foreign language , you can read this book by yourself and understand its contents easily. This book is near perfect.
  
  
• Great book on the subject
  By A3UF0JU2TVCC49 on 2006-12-27
  If you are interested in or for other reasons must read a book on this subject, this is the book. I took a class last semester which used Hopcroft as the text and I found myself often turning to this book for better understanding. This book is more intuitive and thus a bit less formal than Hopcroft but when trying to learn, understanding is better than mathematical formalism. If you are new to the subject, Sipser is the book to begin with.
  
  
• An EXCELLENT Automata/Theory of Computation book
  By A44C4V0NMLKC0 on 2003-11-04
  This book is one of the best written books on Automata/Theory of Computation that I have ever seen. It is a great introduction to the subject. It's also a great way to review the key topics.

  One of the greatest things about this book is its focus on developing an intuitive understanding of the concepts and proofs. Other books do a better job of formal proofs but this book is light years ahead of any other in terms of helping you develop an intuitive understanding of why a given proof or construction is correct. It's a lot better than the memorize/regurgitate model necessitated by the emphasis on minutiae of other books.

  Lastly, this book provides great tips on how to approach problem solving (especially proofs).
  
  

• Introduction to the Theory of Computation
  By A1URXUA0SXBMCW on 2004-09-09
  This book is terrible as a text book. The chapters give very simplistic examples, then the problems at the end of the chapters are very difficult. There is no solutions manual, so there is no way to know if you are doing the problems correctly. Let's face it, Automata theory is math, who ever heard of a college level math book without a solutions manual.
  
  

• Introduction to Algorithms
• Artificial Intelligence: A Modern Approach (2nd Edition) (Prentice Hall Series in Artificial Intelligence)
• Introduction to Automata Theory, Languages, and Computation (3rd Edition)
• Operating System Concepts (7th Edition)
• Computers and Intractability: A Guide to the Theory of NP-Completeness (Series of Books in the Mathematical Sciences)