正版 自动机理论、语言和计算导论:典藏版 [美]约翰·E. 霍普克罗

译者序<br/>前言<br/>第1章 自动机：方法与体验 1<br/>1.1 为什么研究自动机理论 1<br/>1.1.1 有穷自动机简介 1<br/>1.1.2 结构表示法 3<br/>1.1.3 自动机与复杂性 3<br/>1.2 形式化证明简介 3<br/>1.2.1 演绎证明 4<br/>1.2.2 求助于定义 6<br/>1.2.3 其他定理形式 7<br/>1.2.4 表面上不是“如果-则”命题的<br/>定理 9<br/>1.3 其他的证明形式 9<br/>1.3.1 证明集合等价性 9<br/>1.3.2 逆否命题 10<br/>1.3.3 反证法 12<br/>1.3.4 反例 12<br/>1.4 归纳证明 13<br/>1.4.1 整数上的归纳法 13<br/>1.4.2 更一般形式的整数归纳法 16<br/>1.4.3 结构归纳法 16<br/>1.4.4 互归纳法 18<br/>1.5 自动机理论的中心概念 19<br/>1.5.1 字母表 19<br/>1.5.2 串 20<br/>1.5.3 语言 21<br/>1.5.4 问题 21<br/>1.6 小结 23<br/>1.7 参考文献 24<br/>第2章 有穷自动机 25<br/>2.1 有穷自动机的非形式化描述 25<br/>2.1.1 基本规则 26<br/>2.1.2 协议 26<br/>2.1.3 允许自动机忽略动作 27<br/>2.1.4 整个系统成为一个自动机 29<br/>2.1.5 用乘积自动机验证协议 30<br/>2.2 确定型有穷自动机 30<br/>2.2.1 确定型有穷自动机的定义 31<br/>2.2.2 DFA如何处理串 31<br/>2.2.3 DFA的简化记号 32<br/>2.2.4 把转移函数扩展到串 33<br/>2.2.5 DFA的语言 35<br/>2.2.6 习题 35<br/>2.3 非确定型有穷自动机 37<br/>2.3.1 非确定型有穷自动机的非形式化观点 37<br/>2.3.2 非确定型有穷自动机的定义 38<br/>2.3.3 扩展转移函数 39<br/>2.3.4 NFA的语言 39<br/>2.3.5 确定型有穷自动机与非确定型有穷自动机的等价性 40<br/>2.3.6 子集构造的坏情形 43<br/>2.3.7 习题 45<br/>2.4 应用：文本搜索 46<br/>2.4.1 在文本中查找串 46<br/>2.4.2 文本搜索的非确定型有穷自动机 46<br/>2.4.3 识别关键字集合的DFA 47<br/>2.4.4 习题 49<br/>2.5 带e 转移的有穷自动机 49<br/>2.5.1 e 转移的用途 49<br/>2.5.2 e-NFA的形式化定义 50<br/>2.5.3 e 闭包 51<br/>2.5.4 e-NFA的扩展转移和语言 52<br/>2.5.5 消除 e 转移 53<br/>2.5.6 习题 54<br/>2.6 小结 55<br/>2.7 参考文献 55<br/>第3章 正则表达式与正则语言 57<br/>3.1 正则表达式 57<br/>3.1.1 正则表达式运算符 57<br/>3.1.2 构造正则表达式 59<br/>3.1.3 正则表达式运算符的优先级 60<br/>3.1.4 习题 61<br/>3.2 有穷自动机和正则表达式 61<br/>3.2.1 从DFA到正则表达式 62<br/>3.2.2 通过消除状态把DFA转化为正则表达式 65<br/>3.2.3 把正则表达式转化为自动机 69<br/>3.2.4 习题 72<br/>3.3 正则表达式的应用 73<br/>3.3.1 UNIX中的正则表达式 73<br/>3.3.2 词法分析 74<br/>3.3.3 查找文本中的模式 76<br/>3.3.4 习题 77<br/>3.4 正则表达式代数定律 77<br/>3.4.1 结合律与交换律 78<br/>3.4.2 单位元与零元 78<br/>3.4.3 分配律 79<br/>3.4.4 幂等律 79<br/>3.4.5 与闭包有关的定律 79<br/>3.4.6 发现正则表达式定律 80<br/>3.4.7 检验正则表达式代数定律 81<br/>3.4.8 习题 82<br/>3.5 小结 83<br/>3.6 参考文献 84<br/>第4章 正则语言的性质 85<br/>4.1 证明语言的非正则性 85<br/>4.1.1 正则语言的泵引理 85<br/>4.1.2 泵引理的应用 87<br/>4.1.3 习题 88<br/>4.2 正则语言的封闭性 89<br/>4.2.1 正则语言在布尔运算下的封闭性 89<br/>4.2.2 反转 93<br/>4.2.3 同态 94<br/>4.2.4 逆同态 96<br/>4.2.5 习题 99<br/>4.3 正则语言的判定性质 102<br/>4.3.1 在各种表示之间转化 102<br/>4.3.2 测试正则语言的空性 104<br/>4.3.3 测试正则语言的成员性 104<br/>4.3.4 习题 105<br/>4.4 自动机的等价性和最小化 105<br/>4.4.1 测试状态的等价性 105<br/>4.4.2 测试正则语言的等价性 107<br/>4.4.3 DFA最小化 108<br/>4.4.4 为什么不能比最小DFA更小 110<br/>4.4.5 习题 111<br/>4.5 小结 112<br/>4.6 参考文献 112<br/>第5章 上下文无关文法及上下文无关语言 115<br/>5.1 上下文无关文法 115<br/>5.1.1 一个非形式化的例子 115<br/>5.1.2 上下文无关文法的定义 116<br/>5.1.3 使用文法来推导 118<br/>5.1.4 最左推导和最右推导 119<br/>5.1.5 文法的语言 120<br/>5.1.6 句型 121<br/>5.1.7 习题 122<br/>5.2 语法分析树 124<br/>5.2.1 构造语法分析树 124<br/>5.2.2 语法分析树的产生 125<br/>5.2.3 推理、推导和语法分析树 125<br/>5.2.4 从推理到树 126<br/>5.2.5 从树到推导 127<br/>5.2.6 从推导到递归推理 129<br/>5.2.7 习题 131<br/>5.3 上下文无关文法的应用 131<br/>5.3.1 语法分析器 131<br/>5.3.2 语法分析器生成器YACC 133<br/>5.3.3 标记语言 134<br/>5.3.4 XML和文档类型定义 135<br/>5.3.5 习题 140<br/>5.4 文法和语言的歧义性 141<br/>5.4.1 歧义文法 141<br/>5.4.2 去除文法的歧义性 143<br/>5.4.3 最左推导作为表达歧义性的一种方式 145<br/>5.4.4 固有的歧义性 146<br/>5.4.5 习题 147<br/>5.5 小结 148<br/>5.6 参考文献 148<br/>第6章 下推自动机 151<br/>6.1 下推自动机的定义 151<br/>6.1.1 非形式化的介绍 151<br/>6.1.2 下推自动机的形式化定义 152<br/>6.1.3 PDA的图形表示 154<br/>6.1.4 PDA的瞬时描述 154<br/>6.1.5 习题 157<br/>6.2 PDA的语言 158<br/>6.2.1 以终结状态方式接受 158<br/>6.2.2 以空栈方式接受 159<br/>6.2.3 从空栈方式到终结状态方式 159<br/>6.2.4 从终结状态方式到空栈方式 162<br/>6.2.5 习题 163<br/>6.3 PDA和CFG的等价性 164<br/>6.3.1 从文法到PDA 164<br/>6.3.2 从PDA到文法 167<br/>6.3.3 习题 170<br/>6.4 确定型PDA 171<br/>6.4.1 确定型PDA的定义 171<br/>6.4.2 正则语言与确定型PDA 172<br/>6.4.3 DPDA与上下文无关语言 173<br/>6.4.4 DPDA与歧义文法 173<br/>6.4.5 习题 174<br/>6.5 小结 175<br/>6.6 参考文献 175<br/>第7章 上下文无关语言的性质 177<br/>7.1 上下文无关文法的范式 177<br/>7.1.1 去除无用的符号 177<br/>7.1.2 计算产生符号和可达符号 179<br/>7.1.3 去除e产生式 180<br/>7.1.4 去除单位产生式 182<br/>7.1.5 乔姆斯基范式 185<br/>7.1.6 习题 189<br/>7.2 上下文无关语言的泵引理 191<br/>7.2.1 语法分析树的大小 191<br/>7.2.2 泵引理的陈述 191<br/>7.2.3 CFL的泵引理的应用 193<br/>7.2.4 习题 195<br/>7.3 上下文无关语言的封闭性 196<br/>7.3.1 代入 196<br/>7.3.2 代入定理的应用 198<br/>7.3.3 反转 198<br/>7.3.4 与正则语言的交 199<br/>7.3.5 逆同态 202<br/>7.3.6 习题 204<br/>7.4 CFL的判定性质 205<br/>7.4.1 在CFG和PDA之间相互转化的复杂性 205<br/>7.4.2 变换到乔姆斯基范式的运行时间 207<br/>7.4.3 测试CFL的空性 207<br/>7.4.4 测试CFL的成员性 209<br/>7.4.5 不可判定的CFL问题一览 211<br/>7.4.6 习题 211<br/>7.5 小结 212<br/>7.6 参考文献 212<br/>第8章 图灵机导引 215<br/>8.1 计算机不能解答的问题 215<br/>8.1.1 显示“hello, world”的程序 215<br/>8.1.2 假设中的“hello, world”检验程序 217<br/>8.1.3 把问题归约到另一个问题 219<br/>8.1.4 习题 221<br/>8.2 图灵机 221<br/>8.2.1 寻求判定所有数学问题 222<br/>8.2.2 图灵机的记号 222<br/>8.2.3 图灵机的瞬时描述 223<br/>8.2.4 图灵机转移图 225<br/>8.2.5 图灵机的语言 227<br/>8.2.6 图灵机与停机 228<br/>8.2.7 习题 228<br/>8.3 图灵机的程序设计技术 229<br/>8.3.1 在状态中存储 230<br/>8.3.2 多道 231<br/>8.3.3 子程序 232<br/>8.3.4 习题 234<br/>8.4 基本图灵机的扩展 234<br/>8.4.1 多带图灵机 234<br/>8.4.2 单带图灵机与多带图灵机的等价性 235<br/>8.4.3 运行时间与多带合一构造 236<br/>8.4.4 非确定型图灵机 237<br/>8.4.5 习题 239<br/>8.5 受的图灵机 240<br/>8.5.1 具有半无穷带的图灵机 240<br/>8.5.2 多堆栈机器 242<br/>8.5.3 计数器机器 244<br/>8.5.4 计数器机器的能力 244<br/>8.5.5 习题 246<br/>8.6 图灵机与计算机 247<br/>8.6.1 用计算机模拟图灵机 247<br/>8.6.2 用图灵机模拟计算机 248<br/>8.6.3 比较计算机与图灵机的运行时间 251<br/>8.7 小结 252<br/>8.8 参考文献 253<br/>第9章 不可判定性 255<br/>9.1 非递归可枚举语言 255<br/>9.1.1 枚举二进制串 256<br/>9.1.2 图灵机编码 256<br/>9.1.3 对角化语言 257<br/>9.1.4 证明Ld 非递归可枚举 258<br/>9.1.5 习题 258<br/>9.2 递归可枚举但不可判定的问题 259<br/>9.2.1 递归语言 259<br/>9.2.2 递归语言和递归可枚举语言的补 260<br/>9.2.3 通用语言 262<br/>9.2.4 通用语言的不可判定性 263<br/>9.2.5 习题 264<br/>9.3 与图灵机有关的不可判定问题 266<br/>9.3.1 归约 266<br/>9.3.2 接受空语言的图灵机 267<br/>9.3.3 莱斯定理与递归可枚举语言的性质 269<br/>9.3.4 与图灵机说明有关的问题 271<br/>9.3.5 习题 272<br/>9.4 波斯特对应问题 272<br/>9.4.1 波斯特对应问题的定义 273<br/>9.4.2 “修改过的”PCP 274<br/>9.4.3 PCP不可判定性证明之完成 276<br/>9.4.4 习题 281<br/>9.5 其他不可判定问题 281<br/>9.5.1 与程序有关的问题 281<br/>9.5.2 CFG歧义性问题 281<br/>9.5.3 表语言的补 283<br/>9.5.4 习题 285<br/>9.6 小结 285<br/>9.7 参考文献 286<br/>第10章 难解问题 289<br/>10.1 P类和NP类 289<br/>10.1.1 可在多项式时间内解答的问题 290<br/>10.1.2 例子：克鲁斯卡尔算法 290<br/>10.1.3 非确定型多项式时间 293<br/>10.1.4 NP例子：货郎问题 293<br/>10.1.5 多项式时间归约 294<br/>10.1.6 NP接近问题 295<br/>10.1.7 习题 296<br/>10.2 NP接近问题 297<br/>10.2.1 可满足性问题 297<br/>10.2.2 表示SAT实例 299<br/>10.2.3 SAT问题的NP接近性 299<br/>10.2.4 习题 304<br/>10.3 约束可满足性问题 304<br/>10.3.1 布尔表达式的范式 304<br/>10.3.2 把表达式转化成CNF 305<br/>10.3.3 CSAT的NP接近性 308<br/>10.3.4 3SAT的NP接近性 311<br/>10.3.5 习题 312<br/>10.4 其他的NP接近问题 312<br/>10.4.1 描述NP接近问题 313<br/>10.4.2 独立集问题 313<br/>10.4.3 顶点覆盖问题 316<br/>10.4.4 有向哈密顿回路问题 317<br/>10.4.5 无向哈密顿回路与TSP 322<br/>10.4.6 NP接近问题小结 323<br/>10.4.7 习题 323<br/>10.5 小结 326<br/>10.6 参考文献 326<br/>第11章 其他问题类 329<br/>11.1 NP 中的语言的补 330<br/>11.1.1 NP 补语言类 330<br/>11.1.2 NP接近问题与 NP 补 330<br/>11.1.3 习题 331<br/>11.2 在多项式空间内可解决的问题 331<br/>11.2.1 多项式空间图灵机 332<br/>11.2.2 PS 和 NPS 与前面定义的类的关系 332<br/>11.2.3 确定型多项式空间与非确定型多项式空间 333<br/>11.3 对 PS 接近的问题 335<br/>11.3.1 PS接近性 335<br/>11.3.2 带量词的布尔公式 336<br/>11.3.3 带量词的布尔公式的求值 337<br/>11.3.4 QBF问题的PS接近性 338<br/>11.3.5 习题 341<br/>11.4 基于随机化的语言类 342<br/>11.4.1 快速排序：随机算法举例 342<br/>11.4.2 随机化的图灵机模型 343<br/>11.4.3 随机化图灵机的语言 344<br/>11.4.4 RP 类 345<br/>11.4.5 识别 RP 语言 347<br/>11.4.6 ZPP 类 348<br/>11.4.7 RP 与 ZPP 之间的关系 348<br/>11.4.8 与 P 类和 NP 类的关系 349<br/>11.5 素数性测试的复杂性 349<br/>11.5.1 素数性测试的重要性 350<br/>11.5.2 同余算术简介 351<br/>11.5.3 同余算术计算的复杂性 352<br/>11.5.4 随机多项式素数性测试 353<br/>11.5.5 非确定型素数性测试 354<br/>11.5.6 习题 356<br/>11.6 小结 356<br/>11.7 参考文献 357<br/>索引 359

约翰·E.霍普克罗夫特（John E.Hopcroft），1986年图灵奖获得者、美国国家工程院院士、美国国家科学院院士、美国国家艺术与科学院院士、中国科学院外籍院士、美国康奈尔大学教授。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。他和Jeffrey D.Ullman一起获得2010年EEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。

本书是关于形式语言、自动机理论和计算复杂性方面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明，使用图来帮助阐明思想，并包含了大量的难度各异的示例和习题，以便读者确认和加深对内容的理解。本书已被世界许多有名大学作为计算机理论课程的教材或教学参考书，适合作为高校计算机专业高年级本科生及研究生的教材，还可供从事理论计算工作的研究人员参考。<br>