Automata and Computability (Undergraduate Texts in Computer Science)

This book consists of lecture notes - in the old fashioned understanding of the word - that could be taken straight from the blackboard with a few expositions in between. The format has helped to keep the contents to a reasonable minimum, without the depth of the "Automata Theory, Languages, and Computation" book by Hopcroft and Ullman, but it also makes it exceptionally well suited to a course at the undergraduate / lower graduate level. A good student should be able to go through the text by her/him-self and get a good understanding of a philosophically important field within Computer Science.

I signed up for a grad course and needed a refresher on this stuff. I bought Sipser's book as an undergrad and have been going through it as well. The two sync up beautifully. The things I just wasn't getting from Sipser's book just kind of clicked when I read the descriptions in this book (and the other way around). If you're having trouble with the subject I highly recommend you go get both of them.

This textbook has been chosen as our undergraduate textbook for Foundations of Computer Science since 2000. It is a perfect book for students to review what was been taught during the lectures. The contents are divided into small sections that are easy for students to read -- unlike a big book in which a single chapter can be 100 pages long. You never get frustrated reading this book!

Clean, new and delivered quickly

Reading this textbook is a pleasure.

The chapters are based off of lectures for Kozen's Introduction to Theory of Computation course. The writing is clear and comprehensive in its mix of intuition, formalism and examples. Good on its own, also great alongside the Sipser text.

I started learning the theory of computation using Sipser's excellent textbook. The goal of his book is to show students "the big picture" of the area by explaining the materials in an intuitive manner. However, when I was reading the first two chapters of his book (i.e. on finite automata), often times I found myself asking questions like "why does this automaton recognize that language, as Sipser claimed?". Sometimes, Sipser gives only intuitive explanations to justify his claim, which in my opinion is not sufficient. This is when Kozen's book comes in. Kozen's book is rigorous, clear, and concise (as some of the previous reviewers have remarked). Everything is explained from the basic. In particular, you will see the value of structural inductions in the theory of computation, as it is used quite often to prove statements like "the automaton L recognizes the language A" and other constructive proofs in the book. The reader will also learn how abstract algebra (more precisely, monoid and semigroup theory) can be used to prove important results in the theory of computation, e.g., Parikh's theorem and it's consequence that context-free languages over a singleton alphabet must be regular. [As an aside, monoid theory has recently been used in the proof that the problem of determing whether two deterministic pushdown automata recognize the same language is decidable (the author of the paper was rewarded Godel's prize). I believe that some future breakthroughs in the theory of computation will employ tools from monoid and semigroup theory.] Further, Kozen did a superb job in explaining the materials. So long as you have taken some courses on discrete mathematics and know the principle of mathematical induction, the book will be a quite an easy read. The book also has a great set of homework exercises and "miscellaneous" exercises with solutions/hints. I have to admit that some of these exercises are quite tough (but fear not, as they have hints/solutions). On the other hand, Kozen intentionally omitted any chapters on complexity theory in this book.In conclusion, if you are learning the theory of computation and love mathematical rigor (as I do), I strongly recommend this book. This book can also be used as a great supplement to Sipser's excellent textbook.

Written with an audience of one class in mind, Professor Kozen writes a book which should be read by a much larger audience-namely, by anyone looking for a solid intoduction to the foundational aspects of theoretical computer science. The order in which the material is presented is perhaps the greatest strength of this text. Kozen starts with a treatment of Finite Automata, then makes a transition into Context Free Grammars, and finally to Turing Machines and a general exploration of computational undecidability. One weakness was that there was little in the way of applications. I think that the greatest understanding of how grammars and TM's work comes from actually using these structures in computer programs. A new edition of the book would benefit greatly from more programming assignments as well as a few chapters discussing areas of where these different machines are actually utilized and how they are so efficient.