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

自动机理论、语言和计算导论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　识别关键字集合的DFA47

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　语法分析器生成器YACC133

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　从文法到PDA164

6.3.2　从PDA到文法167

6.3.3　习题170

6.4　确定型PDA171

6.4.1　确定型PDA的定义171

6.4.2　正则语言与确定型PDA172

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　“修改过的”PCP274

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　把表达式转化成CNF305

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　无向哈密顿回路与TSP322

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