Introduction to Languages and the Theory of Computation (2nd edition)

By John C. Martin

McGraw-Hill, 1997

Review By Doug Baldwin

This is a more or less standard theory of computation textbook, distinguished by its very nice balance between mathematical rigor and intuitive comprehension. Like most books in this area, this one provides thorough coverage of finite automata and regular languages, push-down automata and context-free languages, and Turing machines, and introductory coverage of computability and computational complexity.

Introduction to Languages and the Theory of Computation stands out from its competitors in doing the math rigorously, while acknowledging that students will need help reading that rigor. For example, the book presents construction proofs as both an explanation of the construction and a complete proof that it produces the required object. Many other texts simply describe the construction and leave its correctness as a matter of faith. To make these proofs accessible, Martin takes pains to explain the key ideas underlying them, to explain the less obvious decisions within the proofs, to pose the problems that are being solved before diving into proofs, etc.

As a teacher of undergraduate theory of computation, I value mathematical rigor in it. The course is important not just for introducing students to important models of computation, but also for exposing them to important ways of thinking about computation. And theory of computation's most important lesson about thinking is that computation can be described formally, and that those formal descriptions support rigorous mathematical investigation, with often surprising results. Unfortunately, while Martin's mathematics is unusually accessible given its rigor, my students still have trouble following it. I can rely on them to learn the basic facts by reading the text, but I need to use class time to review and explain the proofs -- not a bad situation, but not as good as one might hope either.

If you want to teach a mathematically rigorous introduction to the theory of computation, concentrating on traditional automata and languages, then this book should be high on your list of candidate texts.