Appropriate for senior and graduate level courses in Computer Science Theory Automata and Theory of Computation. This is the long awaited Second Edition of Lewis and Papadimitriou''s best-selling theory of computation text. In this substantially modified edition the authors have enhanced the clarity of their presentation by making the material more accessible to a broader undergraduate audience with no special mathematical experience.