本书精辟地阐述了计算课程的入门理论，简明地解释了复杂的思想并且提供了坚实的数学基础知识。作者提供了直观的证明，同时避免过多数学细节，这样学生就能够集中精力理解基本理论。许多精心选择的例子在几种上下文中重复出现，这样学生就能够通过对比式的研究加强理解。
　　本书主要特点如下：
　　简单明了地解释复杂的概念。
　　提供了各种难度的练习题。

无

Peter Linz：Peter Linz:　　Peter Linz 加利福尼亚大学戴维斯分校计算机科学系的荣誉教授，研究重点是：开发数值分析理论，以构建可靠的数值方法并将其用于科学计算中的问题求解环境的设计。Linz教授的相关著作还有 Exploring Numerical Methods: An Introduction to Scientific Computing。

Chapter 1 Introduction to the Theory of Computation
　　　　　1.1 Mathematical Preliminaries and Notation
　　　　　1.2 Three Basic Concepts
　　　　　1.3 Some Applications

Chapter 2 Finite Automata　　　　　　　
　　　　　2.1 Deterministic Finite Accepters
　　　　　2.2 Nondeterministic Finite Accepters
　　　　　2.3 Equivalence of Deterministic and Nondeterministic Finite Accepters
　　　　　2.4 Reduction of the Number of States in Finite Automata

Chapter 3 Regular Languages and Regular Grammars　　　　　　　　
　　　　　3.1 Regular Expressions
　　　　　3.2 Connection Between Regular Expressions and Regular Languages
　　　　　3.3 Regular Grammars

Chapter 4 Properties of Regular Languages
　　　　　4.1 Closure Properties of Regular Languages　　　　　　
　　　　　4.2 Elementary Questions about Regular Languages
　　　　　4.3 Identifying Nonregular Languages

Chapter 5 Context-Free Languages　　　　　　
　　　　　5.1 Context-Free Grammars　　　　　　　
　　　　　5.2 Parsing and Ambiguity　　　　　　
　　　　　5.3 Context-Free Grammars and Programming Languages　　　　　　

Chapter 6 Simplification of Context-Free Grammars and Normal Forms　　　
　　　　　6.1 Methods for Transforming Grammars　　　　　　　
　　　　　6.2 Two Important Normal Forms　　
　　　　　6.3 A Membership Algorithm for Context-Free Grammars　　　　　　　

Chapter 7 Pushdown Automata　　　　　　　
　　　　　7.1 Nondeterministic Pushdown Automata　　　　　　　
　　　　　7.2 Pushdown Automata and Context-Free Languages　　　　　　
　　　　　7.3 Deterministic Pushdown Automata and Deterministic Context-Free Languages　　　　　　
　　　　　7.4 Grammars for Deterministic Context-Free Languages　　　　　　

Chapter 8 Properties of Context-Free Languages　　　　　　
　　　　　8.1 Two Pumping Lemmas
　　　　　8.2 Closure Properties and Decision Algorithms for Context-Free
Languages　　　　　　　　

Chapter 9 Turing Machines　　　　　　　
　　　　　9.1 The Standard Turing Machine　　　　　　　　
　　　　　9.2 Combining Turing Machines for Complicated Tasks　　
　　　　　9.3 Turing’s Thesis　　

Chapter 10 Other Models of Turing Machines　　　　　　　
　　　　　10.1 Minor Variations on the Turing Machine Theme　
　　　　　10.2 Turing Machines with More Complex Storage　
　　　　　10.3 Nondeterministic Turing Machines
　　　　　10.4 A Universal Turing Machine　　　　　　　　
　　　　　10.5 Linear Bounded Automata　　　　　　　

Chapter 11 A Hierarchy of Formal Languages and Automata　　　　　　　
　　　　　11.1 Recursive and Recursively Enumerable Languages　　　　　　
　　　　　11.2 Unrestricted Grammars　　　　　　　
　　　　　11.3 Context-Sensitive Grammars and Languages　　　　　　
　　　　　11.4 The Chomsky Hierarchy　　　　　　　　　　　　　　　

Chapter 12 Limits of Algorithmic Computation
　　　　　12.1 Some Problems That Cannot Be Solved By Turing Machines　　　　　　　
　　　　　12.2 Undecidable Problems for Recursively Enumerable Languages
　　　　　12.3 The Post Correspondence Problem
　　　　　12.4 Undecidable Problems for Context-Free Languages
　　　　　　　　
Chapter 13 Other Models of Computation
　　　　　13.1 Recursive Functions
　　　　　13.2 Post Systems
　　　　　13.3 Rewriting Systems

Chapter 14 An Introduction to Computational Complexity
　　　　　14.1 Efficiency of Computation
　　　　　14.2 Turing Machines and Complexity
　　　　　14.3 Language Families and Complexity Classes
　　　　　14.4 The Complexity Classes P and NP

Answers to Selected Exercises
References
Index