【文件属性】：
文件名称：Theory Of Computation
文件大小：1.25MB
文件格式：PDF
更新时间：2022-04-29 16:27:26
TCS 计算机科学
网络资源，仅为分享。
Introduction to Theory of Computation
Contents
Preface vi
1 Introduction 1
1.1 Purpose and motivation . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Complexity theory . . . . . . . . . . . . . . . . . . . . 2
1.1.2 Computability theory . . . . . . . . . . . . . . . . . . . 2
1.1.3 Automata theory . . . . . . . . . . . . . . . . . . . . . 3
1.1.4 This course . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Mathematical preliminaries . . . . . . . . . . . . . . . . . . . 4
1.3 Proof techniques . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.1 Direct proofs . . . . . . . . . . . . . . . . . . . . . . . 8
1.3.2 Constructive proofs . . . . . . . . . . . . . . . . . . . . 9
1.3.3 Nonconstructive proofs . . . . . . . . . . . . . . . . . . 10
1.3.4 Proofs by contradiction . . . . . . . . . . . . . . . . . . 11
1.3.5 The pigeon hole principle . . . . . . . . . . . . . . . . . 12
1.3.6 Proofs by induction . . . . . . . . . . . . . . . . . . . . 13
1.3.7 More examples of proofs . . . . . . . . . . . . . . . . . 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Finite Automata and Regular Languages 21
2.1 An example: Controling a toll gate . . . . . . . . . . . . . . . 21
2.2 Deterministic finite automata . . . . . . . . . . . . . . . . . . 23
2.2.1 A first example of a finite automaton . . . . . . . . . . 26
2.2.2 A second example of a finite automaton . . . . . . . . 28
2.2.3 A third example of a finite automaton . . . . . . . . . 29
2.3 Regular operations . . . . . . . . . . . . . . . . . . . . . . . . 31
2.4 Nondeterministic finite automata . . . . . . . . . .