自动机理论、语言和计算导论PDF电子书下载

第1章 自动机：方法与体验 1

1.1　为什么研究自动机理论 1

1.1.1　有穷自动机简介 1

1.1.2　结构表示法 3

1.1.3　自动机与复杂性 3

1.2　形式化证明简介 3

1.2.1　演绎证明 4

1.2.2　求助于定义 6

1.2.3　其他定理形式 7

1.2.4　表面上不是“如果－则”命题的定理 9

1.3　其他的证明形式 9

1.3.1　证明集合等价性 9

1.3.2　逆否命题 10

1.3.3　反证法 12

1.3.4　反例 12

1.4　归纳证明 13

1.4.1　整数上的归纳法 13

1.4.2　更一般形式的整数归纳法 16

1.4.3　结构归纳法 16

1.4.4　互归纳法 18

1.5　自动机理论的中心概念 19

1.5.1　字母表 19

1.5.2　串 20

1.5.3　语言 21

1.5.4　问题 21

1.6　小结 23

1.7　参考文献 24

第2章 有穷自动机 25

2.1　有穷自动机的非形式化描述 25

2.1.1　基本规则 26

2.1.2　协议 26

2.1.3　允许自动机忽略动作 27

2.1.4　整个系统成为一个自动机 29

2.1.5　用乘积自动机验证协议 30

2.2　确定型有穷自动机 30

2.2.1　确定型有穷自动机的定义 31

2.2.2　DFA如何处理串 31

2.2.3　DFA的简化记号 32

2.2.4　把转移函数扩展到串 33

2.2.5　DFA的语言 35

2.2.6　习题 35

2.3　非确定型有穷自动机 37

2.3.1　非确定型有穷自动机的非形式化观点 37

2.3.2　非确定型有穷自动机的定义 38

2.3.3　扩展转移函数 39

2.3.4　NFA的语言 39

2.3.5　确定型有穷自动机与非确定型有穷自动机的等价性 40

2.3.6　子集构造的坏情形 43

2.3.7　习题 45

2.4　应用：文本搜索 46

2.4.1　在文本中查找串 46

2.4.2　文本搜索的非确定型有穷自动机 46

2.4.3　识别关键字集合的DFA 47

2.4.4　习题 49

2.5　带ε转移的有穷自动机 49

2.5.1　ε转移的用途 49

2.5.2　ε-NFA的形式化定义 50

2.5.3　ε闭包 51

2.5.4　ε-NFA的扩展转移和语言 52

2.5.5　消除ε转移 53

2.5.6　习题 54

2.6　小结 55

2.7　参考文献 55

第3章 正则表达式与正则语言 57

3.1　正则表达式 57

3.1.1　正则表达式运算符 57

3.1.2　构造正则表达式 59

3.1.3　正则表达式运算符的优先级 60

3.1.4　习题 61

3.2　有穷自动机和正则表达式 61

3.2.1　从DFA到正则表达式 62

3.2.2　通过消除状态把DFA转化为正则表达式 65

3.2.3　把正则表达式转化为自动机 69

3.2.4　习题 72

3.3　正则表达式的应用 73

3.3.1　UNIX中的正则表达式 73

3.3.2　词法分析 74

3.3.3　查找文本中的模式 76

3.3.4　习题 77

3.4　正则表达式代数定律 77

3.4.1　结合律与交换律 78

3.4.2　单位元与零元 78

3.4.3　分配律 79

3.4.4　幂等律 79

3.4.5　与闭包有关的定律 79

3.4.6　发现正则表达式定律 80

3.4.7　检验正则表达式代数定律 81

3.4.8　习题 82

3.5　小结 83

3.6　参考文献 84

第4章 正则语言的性质 85

4.1　证明语言的非正则性 85

4.1.1　正则语言的泵引理 85

4.1.2　泵引理的应用 87

4.1.3　习题 88

4.2　正则语言的封闭性 89

4.2.1　正则语言在布尔运算下的闭包 89

4.2.2　反转 93

4.2.3　同态 94

4.2.4　逆同态 96

4.2.5　习题 99

4.3　正则语言的判定性质 102

4.3.1　在各种表示之间转化 102

4.3.2　测试正则语言的空性 104

4.3.3　测试正则语言的成员性 104

4.3.4　习题 105

4.4　自动机的等价性和最小化 105

4.4.1　测试状态的等价性 105

4.4.2　测试正则语言的等价性 107

4.4.3　DFA最小化 108

4.4.4　为什么不能比最小DFA更小 110

4.4.5　习题 111

4.5　小结 112

4.6　参考文献 112

第5章 上下文无关文法及上下文无关语言 115

5.1　上下文无关文法 115

5.1.1　一个非形式化的例子 115

5.1.2　上下文无关文法的定义 116

5.1.3　使用文法来推导 118

5.1.4　最左推导和最右推导 119

5.1.5　文法的语言 120

5.1.6　句型 121

5.1.7　习题 122

5.2　语法分析树 124

5.2.1　构造语法分析树 124

5.2.2　语法分析树的产生 125

5.2.3　推理、推导和语法分析树 125

5.2.4　从推理到树 126

5.2.5　从树到推导 127

5.2.6　从推导到递归推理 129

5.2.7　习题 131

5.3　上下文无关文法的应用 131

5.3.1　语法分析器 131

5.3.2　语法分析器生成器YACC 133

5.3.3　标记语言 134

5.3.4　XML和文档类型定义 135

5.3.5　习题 140

5.4　文法和语言的歧义性 141

5.4.1　歧义文法 141

5.4.2　去除文法的歧义性 143

5.4.3　最左推导作为表达歧义性的一种方式 145

5.4.4　固有的歧义性 146

5.4.5　习题 147

5.5　小结 148

5.6　参考文献 148

第6章 下推自动机 151

6.1　下推自动机的定义 151

6.1.1　非形式化的介绍 151

6.1.2　下推自动机的形式化定义 152

6.1.3　PDA的图形表示 154

6.1.4　PDA的瞬时描述 154

6.1.5　习题 157

6.2　PDA的语言 158

6.2.1　以终结状态方式接受 158

6.2.2　以空栈方式接受 159

6.2.3　从空栈方式到终结状态方式 159

6.2.4　从终结状态方式到空栈方式 162

6.2.5　习题 163

6.3　PDA和CFG的等价性 164

6.3.1　从文法到PDA 164

6.3.2　从PDA到文法 167

6.3.3　习题 170

6.4　确定型PDA 171

6.4.1　确定型PDA的定义 171

6.4.2　正则语言与确定型PDA 172

6.4.3　DPDA与上下文无关语言 173

6.4.4　DPDA与歧义文法 173

6.4.5　习题 174

6.5　小结 175

6.6　参考文献 175

第7章 上下文无关语言的性质 177

7.1　上下文无关文法的范式 177

7.1.1　去除无用的符号 177

7.1.2　计算产生符号和可达符号 179

7.1.3　去除ε产生式 180

7.1.4　去除单位产生式 182

7.1.5　乔姆斯基范式 185

7.1.6　习题 189

7.2　上下文无关语言的泵引理 191

7.2.1　语法分析树的大小 191

7.2.2　泵引理的陈述 191

7.2.3　CFL的泵引理的应用 193

7.2.4　习题 195

7.3　上下文无关语言的封闭性 196

7.3.1　代入 196

7.3.2　代入定理的应用 198

7.3.3　反转 198

7.3.4　与正则语言的交 199

7.3.5　逆同态 202

7.3.6　习题 204

7.4　CFL的判定性质 205

7.4.1　在CFG和PDA之间互相转化的复杂性 205

7.4.2　变换到乔姆斯基范式的运行时间 207

7.4.3　测试CFL的空性 207

7.4.4　测试CFL的成员性 209

7.4.5　不可判定的CFL问题一览 211

7.4.6　习题 211

7.5　小结 212

7.6　参考文献 212

第8章 图灵机导引 215

8.1　计算机不能解答的问题 215

8.1.1　显示“hello,world”的程序 215

8.1.2　假设中的“hello,world”检验程序 217

8.1.3　把问题归约到另一个问题 219

8.1.4　习题 221

8.2　图灵机 221

8.2.1　寻求判定所有数学问题 222

8.2.2　图灵机的记号 222

8.2.3　图灵机的瞬时描述 223

8.2.4　图灵机转移图 225

8.2.5　图灵机的语言 227

8.2.6　图灵机与停机 228

8.2.7　习题 228

8.3　图灵机的程序设计技术 229

8.3.1　在状态中存储 230

8.3.2　多道 231

8.3.3　子程序 232

8.3.4　习题 234

8.4　基本图灵机的扩展 234

8.4.1　多带图灵机 234

8.4.2　单带图灵机与多带图灵机的等价性 235

8.4.3　运行时间与多带合一构造 236

8.4.4　非确定型图灵机 237

8.4.5　习题 239

8.5　受限制的图灵机 240

8.5.1　具有半无穷带的图灵机 240

8.5.2　多堆栈机器 242

8.5.3　计数器机器 244

8.5.4　计数器机器的能力 244

8.5.5　习题 246

8.6　图灵机与计算机 247

8.6.1　用计算机模拟图灵机 247

8.6.2　用图灵机模拟计算机 248

8.6.3　比较计算机与图灵机的运行时间 251

8.7　小结 252

8.8　参考文献 253

第9章 不可判定性 255

9.1　非递归可枚举语言 255

9.1.1　枚举二进制串 256

9.1.2　图灵机编码 256

9.1.3　对角化语言 257

9.1.4　证明Ld非递归可枚举 258

9.1.5　习题 258

9.2　是递归可枚举但不可判定的问题 259

9.2.1　递归语言 259

9.2.2　递归语言和递归可枚举语言的补 260

9.2.3　通用语言 262

9.2.4　通用语言的不可判定性 263

9.2.5　习题 264

9.3　与图灵机有关的不可判定问题 266

9.3.1　归约 266

9.3.2　接受空语言的图灵机 267

9.3.3　莱斯定理与递归可枚举语言的性质 269

9.3.4　与图灵机说明有关的问题 271

9.3.5　习题 272

9.4　波斯特对应问题 272

9.4.1　波斯特对应问题的定义 273

9.4.2　“修改过的”PCP 274

9.4.3　PCP不可判定性证明之完成 276

9.4.4　习题 281

9.5　其他不可判定问题 281

9.5.1　与程序有关的问题 281

9.5.2　CFG歧义性问题 281

9.5.3　表语言的补 283

9.5.4　习题 285

9.6　小结 285

9.7　参考文献 286

第10章 难解问题 289

10.1　P类和NP类 289

10.1.1　可在多项式时间内解答的问题 290

10.1.2　例子：克鲁斯卡尔算法 290

10.1.3　非确定型多项式时间 293

10.1.4　NP例子：货郎问题 293

10.1.5　多项式时间归约 294

10.1.6　NP完全问题 295

10.1.7　习题 296

10.2　NP完全问题 297

10.2.1　可满足性问题 297

10.2.2　表示SAT实例 299

10.2.3　SAT问题的NP完全性 299

10.2.4　习题 304

10.3　约束可满足性问题 304

10.3.1　布尔表达式的范式 304

10.3.2　把表达式转化成CNF 305

10.3.3　CSAT的NP完全性 308

10.3.4　3SAT的NP完全性 311

10.3.5　习题 312

10.4　其他的NP完全问题 312

10.4.1　描述NP完全问题 313

10.4.2　独立集问题 313

10.4.3　顶点覆盖问题 316

10.4.4　有向哈密顿回路问题 317

10.4.5　无向哈密顿回路与TSP 322

10.4.6　NP完全问题小结 323

10.4.7　习题 323

10.5　小结 326

10.6　参考文献 326

第11章 其他问题类 329

11.1　NP中的语言的补 330

11.1.1　NP补语言类 330

11.1.2　NP完全问题与NP补 330

11.1.3　习题 331

11.2　在多项式空间内可解决的问题 331

11.2.1　多项式空间图灵机 332

11.2.2　PS和NPS与前面定义的类的关系 332

11.2.3　确定型多项式空间与非确定型多项式空间 333

11.3　对PS完全的问题 335

11.3.1　PS完全性 335

11.3.2　带量词的布尔公式 336

11.3.3　带量词的布尔公式的求值 337

11.3.4　QBF问题的PS完全性 338

11.3.5　习题 341

11.4　基于随机化的语言类 342

11.4.1　快速排序：随机算法举例 342

11.4.2　随机化的图灵机模型 343

11.4.3　随机化图灵机的语言 344

11.4.4　RP类 345

11.4.5　识别RP语言 347

11.4.6　ZPP类 347

11.4.7　RP与ZPP之间的关系 348

11.4.8　与P类和NP类的关系 349

11.5　素数性测试的复杂性 349

11.5.1　素数性测试的重要性 350

11.5.2　同余算术简介 351

11.5.3　同余算术计算的复杂性 352

11.5.4　随机多项式素数性测试 353

11.5.5　非确定型素数性测试 354

11.5.6　习题 356

11.6　小结 356

11.7　参考文献 357

索引 359