This undergraduate textbook is designed for a course on the foundations of computer science (CS). Teaching such a course can be a challenging enterprise. Many students believe that what they learn in such a foundational course has nothing to do with their future work and, as a result, show little motivation and interest. To help with this difficult situation, instructors require motivational textbooks that are as clear and precise as possible. While this is difficult to achieve, undergraduate theory textbooks should be measured by this criteria.

CS foundational material undergoes very few changes. Hence, for a textbook to be helpful to an instructor, it should provide additional tools to help the instructor connect the material with recent developments in the field. Unfortunately, this textbook fails in this respect. While it is well written and easy to understand, it contains little else than a nice collection of theorems, proofs, and exercises that CS students are expected to know and/or know how to solve.

The book is divided into ten chapters, and each chapter is divided into several sections. The sections are relatively short, making them suitable for a one- or two-hour lesson plan.

The book follows a standard outline. Chapter 1 is “Mathematical Preliminaries.” Chapter 2 is “Regular Languages.” Chapter 3 handles equivalences between languages. Chapter 4 is “Structure of Regular Languages.” Chapter 5 is “Context-free Languages,” and chapter 6 discusses their properties. Chapter 7 and 8 deal with computably enumerable and noncomputably enumerable languages, respectively. Chapter 9 is “Algorithmic Solvability,” and chapter 10 is “Computational Complexity.” Due to chapter 10’s brevity, it seems to shortchange its difficult subject. Since it is very dense, it will be of limited value to many readers.

Overall, I recommend this book to instructors and students who are only looking for a clear, concise, and well-written introduction to the foundations of CS. However, the book does not encourage readers’ interest in the subject, if the motivation is not already there.