As the discipline of computer science matures, demand to introduce its basic theoretical foundations at the undergraduate level is growing. In this book, the author has succeeded in providing a delightful introduction to this area. The book is pedagogically sound and inviting. The basic ideas are motivated through and abstracted from practical problems. The style is informal, yet the book contains adequate theory suitable for junior- or senior-level courses.

After the introductory chapter, which defines the basic notions and concepts from discrete mathematics, the remainder of the book may be divided into three parts. Part 1, consisting of chapters 1, 2, and 3, introduces the basic concepts of finite automata, pushdown automata, Turing machines, the classes of languages accepted by these machines, and relationships between language classes. This part is replete with examples drawn from compiler design. Part 2 further analyzes Turing machines from the point of view of computability theory. This part, consisting of chapter 4, provides a solid introduction to recursive function theory and Turing computability. Part 3 introduces the notion of resource-bounded computations, in particular the P-class, the NP-class, and NP-completeness. Five short appendices and over 150 exercise problems extend the main development.