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

第一章 预备知识 1

1.1 字符串、字母表和语言 1

1.2 图和树 2

1.3 归纳证明 4

1.4 集合 5

1.5 关系 8

1.6 本书提要 10

第二章 有穷自动机和正规表达式 15

2.1 有穷状态系统 15

2.2 基本定义 18

2.3 非确定有穷自动机 22

2.4 具有？动作的有穷自动机 28

2.5 正规表达式 33

2.6 双向有穷自动机 43

2.7 具有输出的有穷自动机 51

2.8 有穷自动机的应用 55

第三章 正规集合的性质 67

3.1 正规集合的泵作用引理 67

3.2 正规集合的封闭性质 71

3.3 正规集合的判定算法 77

3.4 Myhill-Nerode定理和有穷自动机的最小化 79

第四章 上下文无关文法 94

4.1 动机和引言 94

4.2 上下文无关文法 96

4.3 派生树 100

4.4 上下文无关文法的简化 107

4.5 Chomsky范式 115

4.6 Greibach范式 118

4.7 固有多义上下文无关语言的存在性 123

第五章 下推自动机 134

5.1 非形式描述 134

5.2 定义 136

5.3 下推自动机和上下文无关语言 142

第六章 上下文无关语言的性质 156

6.1 关于CFL的泵作用引理 156

6.2 CFL的封闭性质 162

6.3 有关CFL的判定算法 171

7.1 引言 184

第七章 图灵机 184

7.2 图灵机模型 185

7.3 可计算语言和可计算函数 189

7.4 图灵机构造技术 192

7.5 图灵机的修改 200

7.6 Church假设 208

7.7 作为枚举器的图灵机 210

7.8 等价于基本模型的受限图灵机 214

第八章 不可判定性 222

8.1 问题 222

8.2 递归语言和递归可枚举语言的性质 224

8.3 通用图灵机和一个不可判定问题 227

8.4 Rice定理和某些其它的不可判定问题 232

8.5 Post对应问题的不可判定性 243

8.6 图灵机的有效计算和无效计算，证明CFL问题不可判定性的一个工具 253

8.7 Greibach定理 258

8.8 递归函数论初步 261

8.9 Oracle计算 264

第九章 Chomsky谱系 274

9.1 正规文法 274

9.2 无限制文法 278

9.3 上下文有关语言 282

9.4 语言类之间的关系 287

第十章 确定的上下文无关语言 294

10.1 DPDA的标准形式 295

10.2 DCFL在补运算下的封闭性 297

10.3 预测机 303

10.4 DCFL的其它封闭性质 308

10.5 DCFL的判定性质 312

10.6 LR(O)文法 314

10.7 LR(O)文法与DRDA 322

10.8 LR(K)文法 332

第十一章 语言族的封闭性质 343

11.1 三元族和完全三元族 343

11.2 广义时序机映射 345

11.3 三元族的其它封闭性质 351

11.4 抽象语言族 352

11.5 AFL运算的独立性 354

11.6 小结 355

第十二章 计算复杂性理论 362

12.1 定义 362

12.2 线性加速、带压缩和带数目的减少 365

12.3 谱系定理 374

12.4 复杂性量度间的关系 381

12.5 转换引理和非确定谱系 385

12.6 一般复杂性量度的性质，间隙定理、加速定理和并定理 389

12.7 公理化复杂性理论 399

第十三章 难解型问题 409

13.1 多项式时间和空间 409

13.2 某些NP完全问题 414

13.3 CO-？？类 437

13.4 PSPACE完全问题 439

13.5 对于？和NSPACE(logn)的完全问题 444

13.6 某些可证明的难解型问题 448

13.7 对于带Oracle的图灵机的？=？？问题：辨别是否？=？？时我们能力的限度 463

第十四章 其它重要语言类集锦 481

14.1 辅助下推自动机 481

14.2 栈自动机 486

14.3 加标语言 496

14.4 发展系统 498

14.5 小结 500

参考文献 504

汉英名词索引 519