Introduction to Languages and the Theory of Computation presents for undergraduates the principal topics in the theory of computation. The first chapter lays out clearly the mathematical tools that will be used. The next few chapters survey the important models of computation, from finite automata to Turing machines, along with the languages corresponding to each model. Following the chapters on Turing machines and their languages, there is a detailed discussion of diagonalization, leading to a number of undecidable problems that illustrate fundamental limitations of the algorithmic method. The last two chapters are a presentation of Kleene’s approach to computable functions and an introduction to complexity and NP-completeness.

The discussion of induction in the first chapter emphasizes structural induction, which helps to clarify the various applications of induction in the text. In Chapters 2 and 3, the finite-automaton model of computation is presented first, and regular expressions and languages are then discussed along with the nondeterminism that simplifies the proof of Kleene’s Theorem. Real-life examples of both finite automata and regular expressions have been added. In the introduction to Turing machines, there is less attention to the “programming” details and more emphasis on the Church-Turing Thesis and the role of the Turing machine as a general model of computation. The chapter on computational complexity emphasizes polynomial-time decidability, the sets P and NP, and NP-completeness, and now includes a characterization of NP in terms of polynomial-time verifiability as well as an introductory example to clarify the proof of the Cook-Levin Theorem.

The fourth edition of Introduction to Languages and the Theory of Computation has been substantially rewritten, and the number of chapters has been reduced from fourteen to eleven. Like its predecessors, the fourth edition takes advantage of the clarity and efficiency of mathematical language, but it focuses on readability and removing obstacles to student understanding. Technical details are provided where they help to illuminate the arguments and minimized when all they add is completeness. Informal language makes the mathematical notation more approachable, but the author is careful not to erect barriers in the form of paragraphs of prose. Examples are modified and reorganized so that each builds on previous ones; complications that turn out to be peripheral to the subject are eliminated. Many exercises have been reworked, and the selection varies from elementary to challenging. The exposition is streamlined and improved, and the result is a shorter book that retains the rigor and topic selection of previous editions.