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.
- R.W. Floyd & R. Beigel (1994): The Language of
Machines, Computer Science Press (Freeman). 706 pages. $60
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.
- J.E. Hopcroft & J.D. Ullman (1978): Introduction to Automata Theory,
Languages & Computation, Addison & Wesley. 418 pages. $47
- H.R. Lewis & C.R. Papadimitriou (1981): Elements of the Theory
of Computation, Prentice Hall. 466 pages. $76
- D. Kelley (1995): Automata & Formal Languages - An
Introduction, Prentice Hall. 240 pages. $52
Rob van Glabbeek