I recently encountered this book at a publisher's booth at a computer conference and read it on the ride back home. This morning I made a trip to the college bookstore and notified them that it is the textbook that I will be using in my computation theory class this spring.
The chapter titles are:

0) Introduction - this chapter contains the fundamental mathematical background of sets, functions, graphs and proofs. For most students, it could be skipped or skimmed.
1) Regular languages - this chapter is an introduction to deterministic and nondeterministic finite automata and regular expressions.
2) Context-free languages - an introduction to context-free grammars and pushdown automata.
3) The Church-Turing theses - an introduction to Turing machines and the variants, such as multiple tapes and nondeterministic Turing machines.
4) Decidability - the definition of decidability and how Turing machines and finite automata are used to prove or disprove if a language is decidable.
5) Reducibility - the definition of reducible and how Turing machines can be used to execute reductions.
6) The recursion theorem - an introduction to the recursion theorem and some applications to formal theories.
7) Time complexity - the first chapter in the coverage of algorithmic complexity, in this case execution time.
8) Space complexity - an examination of the complexity of algorithms from the perspective of the amount of memory required.
9) Intractability - an examination of the problems that can be solved in principle but not in practice.
10) Advanced topics in complexity theory - approximation algorithms, probabilistic algorithms, alternation, interactive proof systems, parallel computation and cryptography.

There is less coverage of grammars than most books, which is replaced by more in the area of algorithmic analysis. In my opinion, that is an appropriate tradeoff, the analysis of algorithms gives the students some understanding of how automata are applied in computer science.
Another excellent feature of this book is the solutions to selected exercises that appear at the end of the chapters. My estimate is that reasonably detailed solutions to approximately one-third of the problems are included. This allows the students to work extra problems by themselves, and helps the instructor if they are asked to do another example in class that they have not already worked through.
The exposition is very good; I am convinced that the students will be able to read the material on their own, which is one more reason why I adopted this book for my course.

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.

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.

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.

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.

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.

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.

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.

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.

Extremely well written. If you are a student you'll find it very easy to follow - particularly the proofs. Just buy it, i guarantee you will not be dissappointed.

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.

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.

Prof. Sipser gives a fabulous introduction to theoretical computer science. His clear and concise proofs are preceding by "Proof Ideas" that give a non-technical overview of the proof to follow. This makes the proofs far easier to follow. He strikes a perfect balance between concise mathematics and eloquent exposition, so the book neither intimidates the novice student nor bores the seasonsed mathematician. This is a model computer science/mathematics textbook!

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."

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.

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.

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.

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).

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.

This book is by far the best book that I read!!! It presents topics in a very interesting and readable way.

My advice is read this book if you an undergrad student, even though instructor might be using a different book. If you are a grad student this books makes an excellent reference for refreshing your knowledge of Computer Theory. Computer Theory is not my area of interest, but this book makes it very interesting and fun area; which is quiet unusual for Computer Theory books.

I am a grad student taking advanced "Computer Theory" class. I have bought couple books including this one, and checked out from library another 6. This book in an introductory book and it has excellent coverage of the basics, and it has some brief but very good coverage of advanced topics as well. I read this book every time to refresh my knowledge before I go on to more in depth topics. The only thing that I wish, is that the undergrad course that I have taken a number years ago was using this book; and/or I read this book when I was an undergrad.

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!

I think that this book is by far the best introductory text on theory of computation and complexity that I have read so far. I would recommend the aho ulmann book as a companion after having gone through this book to strengthen your knowledge. But, this book introduces stuff like never before. Simply amazing.. buy it even if you are planning to take a course and the instructor is using some other textbook, its that good!!

Sipser did a surprising and didactical synthesis on classic TC topics. And with wit, too! His work is not a boring opus. After years of strugle against texts by honorables like Hopcroft, Lewis & Papadimitriou etc., all important and fundamental but criptic authors, finally someone (that seems had been student someday) writes an understandable book. On library, it is the most looked for. (Obs.: I'm writing here not to add anithing to all that was already well said by other reviewers: it is just for a tribute to the author.)

This really is the clearest and, well, most beautiful theory textbook that I have ever read and used for teaching. Congratulations.

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.

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.

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.

I must concur with the majority of other reviewers, this is an excellent book. It was the textbook we used in a course I followed on complexity theory at university and I found the explanations of concepts remarkably clear and concise. Michael Sipser is one of the few authors of theoretical books around who has a firm and even natural grasp of writing text that explains completely, gets the point across easily and does so without drowning the reader in the sorts of details that should be banished to examples and sidenotes, but that find their way into the main text of so many other books. Highly recommended (by me, at least).

As a computer-engineering graduate, I've seen some of the definitions and theorems presented in this book. Just now - I really understand them fully!

The author really REALLY did a great job in clear, simple explenations.

What I liked most is the way the author presents his view on how problems should be approached, when to use this strategy and the useful examples - which really are explained step by step.
I didn't see anything "left to the reader" - so the examples really help out in understanding the fine details.

Sipser uses clear, short proofs to theorems - which makes them easy to understand and to remember, and I might even say intuitive.

Never have I studied a subject so fast, and so thoroughly as I did using Sipser's book.

A couple of years ago I simultaneously taught two Computability Theory courses. One was at the graduate level and used this book while the undergraduate course used another text. As I was a visitor, I did not have a role in selecting either text.

As the two courses progressed I began to wonder why the graduate text was so much better than the undergraduate text. Later, I checked out an Amazon review for the undergraduate text and discovered that the reviewer was as disgusted with it as I was with the book selected for the undergraduate course. Further, the reviewer specifically recommended this book.

This text really is geared for the advanced undergraduate or graduate student. However, it is beautifully thought out and written. Consequently, it is a far better undergraduate introductory text than several of the books which pretend to service this market.

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.

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.

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.

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!

It has been a privelage to use Sipser's book in 1998, during my final year - Bachelor of Science (Computer Science, Course: 'Formal Languages'). The book covers the subject of 'Formal Languages' brilliantly, using an extremely logical structure, easy-to-follow proofs, helpful Proof Ideas and a colourful text layout clearly indicating the different aspects of the subject matter.

The text IS as good as the best reviews make it out to be (ignore the single 1-star rating). Unfortunately, I do not have the book with me now, otherwise my praise would have taken up the whole 1000 word maximum of the review.