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

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

为什么研究自动机理论 1

有穷自动机简介 1

结构表示法 3

自动机与复杂性 3

形式化证明简介 3

演绎证明 4

求助于定义 6

其他定理形式 7

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

其他的证明形式 9

证明集合等价性 9

逆否命题 10

反证法 12

反例 12

归纳证明 13

整数上的归纳法 13

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

结构归纳法 16

互归纳法 18

自动机理论的中心概念 19

字母表 19

串 20

语言 21

问题 21

小结 23

参考文献 24

第2章 有穷自动机 25

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

基本规则 26

协议 26

允许自动机忽略动作 27

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

用乘积自动机验证协议 30

确定型有穷自动机 30

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

DFA如何处理串 31

DFA的简化记号 32

把转移函数扩展到串 33

DFA的语言 35

习题 35

非确定型有穷自动机 37

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

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

扩展转移函数 39

NFA的语言 39

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

子集构造的坏情形 43

习题 45

应用：文本搜索 46

在文本中查找串 46

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

识别关键字集合的DFA 47

习题 49

带ε转移的有穷自动机 49

ε转移的用途 49

ε-NFA的形式化定义 50

ε闭包 51

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

消除ε转移 53

习题 54

小结 55

参考文献 55

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

正则表达式 57

正则表达式运算符 57

构造正则表达式 59

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

习题 61

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

从DFA到正则表达式 62

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

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

习题 72

正则表达式的应用 73

UNIX中的正则表达式 73

词法分析 74

查找文本中的模式 76

习题 77

正则表达式代数定律 77

结合律与交换律 78

单位元与零元 78

分配律 79

幂等律 79

与闭包有关的定律 79

发现正则表达式定律 80

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

习题 82

小结 83

参考文献 84

第4章 正则语言的性质 85

证明语言的非正则性 85

正则语言的泵引理 85

泵引理的应用 87

习题 88

正则语言的封闭性 89

正则语言在布尔运算下的封闭性 89

反转 93

同态 94

逆同态 96

习题 99

正则语言的判定性质 102

在各种表示之间转化 102

测试正则语言的空性 104

测试正则语言的成员性 104

习题 105

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

测试状态的等价性 105

测试正则语言的等价性 107

DFA最小化 108

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

习题 111

小结 112

参考文献 112

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

上下文无关文法 115

一个非形式化的例子 115

上下文无关文法的定义 116

使用文法来推导 118

最左推导和最右推导 119

文法的语言 120

句型 121

习题 122

语法分析树 124

构造语法分析树 124

语法分析树的产生 125

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

从推理到树 126

从树到推导 127

从推导到递归推理 129

习题 131

上下文无关文法的应用 131

语法分析器 131

语法分析器生成器YACC 133

标记语言 134

XML和文档类型定义 135

习题 140

文法和语言的歧义性 141

歧义文法 141

去除文法的歧义性 143

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

固有的歧义性 146

习题 147

小结 148

参考文献 148

第6章 下推自动机 151

下推自动机的定义 151

非形式化的介绍 151

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

PDA的图形表示 154

PDA的瞬时描述 154

习题 157

PDA的语言 158

以终结状态方式接受 158

以空栈方式接受 159

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

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

习题 163

PDA和CFG的等价性 164

从文法到PDA 164

从PDA到文法 167

习题 170

确定型PDA 171

确定型PDA的定义 171

正则语言与确定型PDA 172

DPDA与上下文无关语言 173

DPDA与歧义文法 173

习题 174

小结 175

参考文献 175

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

上下文无关文法的范式 177

去除无用的符号 177

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

去除ε产生式 180

去除单位产生式 182

乔姆斯基范式 185

习题 189

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

语法分析树的大小 191

泵引理的陈述 191

CFL的泵引理的应用 193

习题 195

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

代入 196

代入定理的应用 198

反转 198

与正则语言的交 199

逆同态 202

习题 204

CFL的判定性质 205

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

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

测试CFL的空性 207

测试CFL的成员性 209

不可判定的CFL问题一览 211

习题 211

小结 212

参考文献 212

第8章 图灵机导引 215

计算机不能解答的问题 215

显示“hello,world”的程序 215

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

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

习题 221

图灵机 221

寻求判定所有数学问题 222

图灵机的记号 222

图灵机的瞬时描述 223

图灵机转移图 225

图灵机的语言 227

图灵机与停机 228

习题 228

图灵机的程序设计技术 229

在状态中存储 230

多道 231

子程序 232

习题 234

基本图灵机的扩展 234

多带图灵机 234

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

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

非确定型图灵机 237

习题 239

受限制的图灵机 240

具有半无穷带的图灵机 240

多堆栈机器 242

计数器机器 244

计数器机器的能力 244

习题 246

图灵机与计算机 247

用计算机模拟图灵机 247

用图灵机模拟计算机 248

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

小结 252

参考文献 253

第9章 不可判定性 255

非递归可枚举语言 255

枚举二进制串 256

图灵机编码 256

对角化语言 257

证明Ld非递归可枚举 258

习题 258

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

递归语言 259

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

通用语言 262

通用语言的不可判定性 263

习题 264

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

归约 266

接受空语言的图灵机 267

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

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

习题 272

波斯特对应问题 272

波斯特对应问题的定义 273

“修改过的”PCP 274

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

习题 281

其他不可判定问题 281

与程序有关的问题 281

CFG歧义性问题 281

表语言的补 283

习题 285

小结 285

参考文献 286

第10章 难解问题 289

P类和NP类 289

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

例子：克鲁斯卡尔算法 290

非确定型多项式时间 293

NP例子：货郎问题 293

多项式时间归约 294

NP完全问题 295

习题 296

NP完全问题 297

可满足性问题 297

表示SAT实例 299

SAT问题的NP完全性 299

习题 304

约束可满足性问题 304

布尔表达式的范式 304

把表达式转化成CNF 305

CSAT的NP完全性 308

3SAT的NP完全性 311

习题 312

其他的NP完全问题 312

描述NP完全问题 313

独立集问题 313

顶点覆盖问题 316

有向哈密顿回路问题 317

无向哈密顿回路与TSP 322

NP完全问题小结 323

习题 323

小结 326

参考文献 326

第11章 其他问题类 329

NP中的语言的补 330

Np补语言类 330

NP完全问题与Np补 330

习题 331

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

多项式空间图灵机 332

ps和Nps与前面定义的类的关系 332

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

对ps完全的问题 335

PS完全性 335

带量词的布尔公式 336

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

QBF问题的PS完全性 338

习题 341

基于随机化的语言类 342

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

随机化的图灵机模型 343

随机化图灵机的语言 344

Rp类 345

识别Rp语言 347

Zpp类 348

Rp与Zpp之间的关系 348

与p类和Np类的关系 349

素数性测试的复杂性 349

素数性测试的重要性 350

同余算术简介 351

同余算术计算的复杂性 352

随机多项式素数性测试 353

非确定型素数性测试 354

习题 356

小结 356

参考文献 357

索引 359