《自动机理论、语言和计算导引》求取 ⇩

第一章 预备知识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)文法与DRDA322

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