本书由计算机理论领域的知名权威Michaael Sipser所撰写。他以独特的视角，系统地介绍了计算机理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。约大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并对课堂测试题进行了全面的更新，每章末均有样例解答。
    本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

Preface to the First Edition
      To the student
      To the educator
      The first edition
      Feedback to the author
      Acknowledgments
Preface to the Sceond Edition（International）
  0  Introduction
    0.1  Automata,CompUTABILITY,and Complexity
      Complexity theory
      Computability theory
    0.2  Mathematical Notions and Terminology
      Sets
      Sequemces and tuples
      Functions and relations
      Graphs
      Strings and languges
      Boolean logic
      Summary of mathematical terms
    0.3  Definitions,Theorems,and Proofs
      Finding proofs
    0.4  Types of Proof
      Proof by construction
      Proof by construction
      Proof by induction
    Exercises,Problims,and Solutions
Part One:Automata and Languages
  1  Regular Languages
    1.1  Finite Automata
      Formal definition of afinite automaton
      Examples of finite automata
      Formal definition of computation
      Designign finite automata
      The regular operations
    1.2  Nondeteriminism
      Formal definition of a nondeterministic finite automaton
      Equivalence of NFAs and DFAs
      Closure under the regular operations
    1.3  Regular Expressions
      Formal definition of a regular expression
      Equivalence with finite automata
    1.4  Nonregular Languages
      The pumping lemma for regulan languages
      Exercises,Problems,and Solutions
  2  Context-Free Languages
    2.1  Conetxt-free Grammars
      Formal definition of a context-free grammar
      Examples of context-free grammars
      Designing context-free grammars
      Ambiguity
      Chomaky mormal form
    2.2  Pushdown Automata
      Formal definition of a pushdown automaton
      Examples of pushdown autonata
      Equivalence wish context-free grammars
    2.3  Non-context-free Languages
      The pumping lemma for context-free languages
    Exercises,Problems,and Solutions
Part Two:Computability Theory
Part Three:Computability Theory
Selected Bibliography
Index