《计算机理论基础 影印版》求取 ⇩

Introduction1

1Sets,Relations,and Languages5

1.1 Sets5

1.2 Relations and functions9

1.3 Special types of binary relations13

1.4 Finite and infinite sets20

1.5 Three fundamental proof techniques23

1.6 Closures and algorithms30

1.7 Alphabets and languages42

1.8 Finite representations of languages47

References52

2Finite Automata55

2.1 Deterministic finite automata55

2.2 Nondeterministic finite automata63

2.3 Finite automata and regular expressions75

2.4 Languages that are and are not regular86

2.5 State minimization92

2.6 Algorithmic aspects of finite automata102

References110

3Context-free Languages113

3.1 Context-free grammars113

3.2 Parse trees122

3.3 Pushdown automata130

3.4 Pushdown automata and context-free grammars136

3.5 Languages that are and are not context-free143

3.6 Algorithms for context-free grammars150

3.7 Determinism and parsing158

References175

4.1 The definition of a Turing machine179

4Turing machines179

4.2 Computing with Turing machines194

4.3 Extensions of Turing machines200

4.4 Random access Turing machines210

4.5 Nondeterministic Turing machines221

4.6 Grammars227

4.7 Numerical functions233

References243

5Undecidability245

5.1 The Church-Turing thesis245

5.2 Universal Turing machines247

5.3 The halting problem251

5.4 Unsolvable problems about Turing machines254

5.5 Unsolvable problems about grammars258

5.6 An unsolvable tiling problem262

5.7 Properties of recursive languages267

References272

6Computational Complexity275

6.1 The class P275

6.2 Problems,problems...278

6.3 Boolean satisfiability288

6.4 The class NP292

References299

7NP-completeness301

7.1 Polynomial-time reductions301

7.2 Cook's Theorem309

7.3 More NP-complete problems317

7.4 Coping with NP-completeness333

References350

Index353