SUMMARY.md

Summary

• 0 Introduction
  • 0.1 Automata, Computability, and Complexity
  • 0.2 数学概念和术语
  • 0.3 定义，定理，证明
  • 0.4 证明方法

Part 1

• 1 Regular Languages
  • 1.1 Finite Automata
  • 1.2 Nondeterminism
  • 1.3 Regular Expressions
  • 1.4 Nonregular Languages
• 2 Context-Free Languages
  • 2.1 Context-Free Grammars
  • 2.2 Pushdown Automata
  • 2.3 Non-Context-Free Languages
  • 2.4 Deterministic Context-Free Languages

Part 2: Computability Theory

• 3 The Church-Turing Thesis
  • 3.1 Turing Machines
  • 3.2 Variants of Turing Machines
  • 3.3 The Definition of Algorithm
• 4 Decidability
  • 4.1 Decidable Languages
  • 4.2 Undecidability
• 5 Reducibility
  • 5.1 Undecidable Problems from Language Theory
  • 5.2 A Simple Undecidable Problem
  • 5.3 Mapping Reducibility
• 6 Advanced Topics in Computability Theory

Part 3: Complexity Theory

• 7 Time Complexity
  • 7.1 Measuring Complexity
  • 7.2 The Class P
  • 7.3 The Class NP
  • 7.4 NP-completeness
  • 7.5 Additional NP-complete Problems