The textbook for CS154

This year the textbook will be This book covers all the topics one would want to cover in this course, except that is is a bit skimpy on complexity theory outside the P and NP issue. I think it reads really well. The information density is not high; you can easily work through 50 pages in one go. Although this is for most students an advantage, it means that you have to leaf through many pages when making a summary of the core issues.

The main novelty of this book in comparison with other texts, is that it presents a lot of concepts that are generally treated on an ad hoc basis, as instances of a more abstract theory. (I.e. there is a general concept of a machine that specializes to the classical finite automata, pushdown automata, Turing machines, etc. There is also a general notion of simulation that replaces various ad hoc strategies for proving machines equivalent.) This makes it easier to see the connections between various parts of the course, and also simplifies some proofs. On the other hand, it can be argued that some energy devoted towards analyzing abstract concepts could have been saved when dealing with the concrete instantiations separately.

If, for a change of viewpoint, you like to see a more standard approach to the subject matter of this course, consult one of:

The first two are classic textbooks for courses like CS154. The last has the advantage that is real easy reading; however, it does not cover all topics of the course.
Rob van Glabbeek