计算理论基础PDF电子书下载

第1章 数学基础 1

1.1 引言 1

1.2 集合 1

1.3 关系与图 3

1.4 函数与计数 7

1.5 证明技巧 14

1.6 本章总结与习题 22

本章习题 22

第2章 正则语言 26

2.1 引言 26

2.2 语言基础 26

本节习题 29

2.3 正则表达式 31

本节习题 32

2.4 正则语法 34

本节习题 37

2.5 确定性有限自动机（DFA） 38

本节习题 46

2.6 非确定性有限自动机（NFA） 47

本节习题 52

2.7 本章总结与附加思考题 54

附加思考题 54

第3章 等价 58

3.1 引言 58

3.2 NFA到DFA 58

本节习题 63

3.3 有限自动机与正则语法 64

本节习题 65

3.4 正则表达式到NFA 66

本节习题 68

3.5 NFA到正则表达式 69

本节习题 73

3.6 本章总结与附加思考题 75

附加思考题 76

第4章 正则语言的结构 78

4.1 引言 78

4.2 闭包性质 78

本节习题 81

4.3 非正则语言 82

本节习题 86

4.4 米歇尔-尼罗德定理 88

本节习题 92

4.5 状态最小化 92

本节习题 98

4.6 本章总结与附加思考题 99

附加思考题 100

第5章 上下文无关语言 105

5.1 引言 105

5.2 上下文无关语法 105

本节习题 108

5.3 分析树 110

本节习题 114

5.4 歧义 114

本节习题 117

5.5 消除／删除不良生成式 118

本节习题 121

5.6 范式 122

本节习题 128

5.7 本章总结与附加思考题 129

附加思考题 129

第6章 上下文无关语言的结构 132

6.1 引言 132

6.2 叠加自动机 132

本节习题 138

6.3 上下文无关语法与叠加自动机 140

本节习题 144

6.4 泵作用引理 145

本节习题 150

6.5 上下文无关语言的闭包性质 151

本节习题 153

6.6 确定型叠加自动机 154

本节习题 158

6.7 本章总结与附加思考题 159

附加思考题 159

第7章 可计算枚举语言 167

7.1 引言 167

7.2 非限制性语法 167

本节习题 169

7.3 图灵机 170

本节习题 174

7.4 接受与拒绝 174

本节习题 179

7.5 使用旧自动机 180

本节习题 187

7.6 多带图灵机 188

本节习题 191

7.7 非确定性图灵机和语法 192

本节习题 197

7.8 本章总结与附加思考题 198

附加思考题 198

第8章 非可计算枚举语言 201

8.1 引言 201

8.2 作为计算器的图灵机 201

本节习题 204

8.3 作为语言判定的图灵机 205

本节习题 209

8.4 存在多少图灵机 210

本节习题 213

8.5 接受问题 213

本节习题 217

8.6 乔姆斯基层次结构 217

本节习题 219

8.7 总结和附加问题 222

本节习题 222

第9章 算法可解性 229

9.1 引言 229

9.2 问题归约 230

本节习题 232

9.3 赖斯定理 234

本节习题 236

9.4 关于有限自动机 238

本节习题 239

9.5 关于叠加自动机 240

本节习题 244

9.6 关于波斯特对应问题 245

本节习题 249

9.7 关于逻辑理论 250

本节习题 255

9.8 其他有趣的问题 255

本节习题 257

9.9 总结和附加问题 258

本节习题 259

第10章 计算复杂性 267

10.1 引言 267

10.2 函数增长率 268

本节习题 271

10.3 复杂性类别 272

本节习题 275

10.4 空间复杂性 276

本节习题 278

10.5 时间复杂性 279

本节习题 283

10.6 NP类 284

本节习题 286

10.7 NP完整性 287

本节习题 291

10.8 某些NP完整问题 291

本节习题 298

10.9 解决NP完整问题 300

本节习题 303

10.10 本章总结与附加思考题 303

附加思考题 304

部分习题答案与提示 313

参考文献 334