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
Published with GitBook
3 The Church-Turing Thesis
3 The Church-Turing Thesis
既然有非CFL的language，比如
{
a
i
b
i
c
i
}
\{a^ib^ic^i\}
{
a
i
b
i
c
i
}
，就引入一个更强大的computer model.
results matching "
"
No results matching "
"