自动机理论、语言和计算导论 原书第3版PDF|Epub|txt|kindle电子书版本网盘下载

自动机理论、语言和计算导论 原书第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

识别关键字集合的DFA47

习题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

语法分析器生成器YACC133

标记语言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

从文法到PDA164

从PDA到文法167

习题170

确定型PDA171

确定型PDA的定义171

正则语言与确定型PDA172

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

“修改过的”PCP274

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

把表达式转化成CNF305

CSAT的NP完全性308

3SAT的NP完全性311

习题312

其他的NP完全问题312

描述NP完全问题313

独立集问题313

顶点覆盖问题316

有向哈密顿回路问题317

无向哈密顿回路与TSP322

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