Introduction to the Theory of Computation

Rating:
Summary: misleading
Review: 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.