本书是关于形式语言、自动机理论和计算复杂性方面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明，使用图来帮助阐明思想，并包含了大量的难度各异的示例和习题，以便读者确认和加深对内容的理解。本书已被世界许多著名大学作为计算机理论课程的教材或教学参考书，适合作为高校计算机专业高年级本科生及研究生的教材，还可供从事理论计算工作的研究人员参考。
三位理论计算大师的巅峰之作，计算机理论课程经典教材
在1979年出版的本书第1版的前言中，Hopcroft和Ullman对于下面的事实感到惊诧不已：与1969年他们写第一本书时的情形相比，自动机这一专题已经有了突破性进展。的确，1979年版的书中包含许多在以前的著作中找不到的主题，篇幅增加了大约一倍。如果读者有兴趣把本书与1979年版的那本书做比较，就会发现，正如20世纪70年代的汽车那样，本书是“外看大，内看小”。从表面看起来像是退步，但是我们有理由对此变化感到高兴。
第一，在1979年，自动机和语言理论还是一个比较活跃的研究领域。那本书的主要目的是鼓励擅长数学的学生为这个领域做出新的贡献。然而今天，直接针对自动机理论的研究几乎已经销声匿迹（相反，更多的是对其应用的研究），因此也就没有理由继续保持1979年那本书的简洁和高度数学化的风格。
第二，近年来，自动机和语言理论的角色已经发生了很大的变化。在1979年，自动机还主要是研究生水平的专题，那时我们假定的读者是高年级研究生，特别是使用这本书后几章的那些读者。然而到了今天，它已经成为本科生课程的主要内容。正是基于这个原因，本书在编排时必须假定读者只有很少的预备知识，因此必须比前一版本的书提供更多的背景知识介绍和论证的细节。
第三，计算机科学在过去的几十年里已经发展到了几乎无法想象的程度。在1979年，我们可能会觉得经受得起下一轮技术考验的材料太少了，以至于排满课程计划都很难，然而今天，却有非常多的子科目在竞争本科生课程的有限空间。
第四，计算机科学如今已经发展成为更加职业化的科目，在许多学习它的学生中存在着严重的实用主义倾向。但我们仍然相信，自动机理论的方方面面是各种新兴学科的重要工具，并且也相信，无论学生多么倾向于只去学习那些最能直接赚钱的技术，但在典型的自动机课程中，那些理论的和有利于拓宽思维的习题依然可以保持其价值。然而，为了保证这个科目在计算机科学专业学生的课程表中继续占有一席之地，我们认为有必要在强调数学理论的同时强调应用。因此，我们把上一版中许多比较深奥的主题换成了本版中如何使用这些思想的例子。虽然自动机和语言理论在众多编译器上的应用如今已经广为人知，以至于这些内容通常已经包含在介绍编译技术的课程中，但是还存在一些较新的用途，包括用来验证协议的模型验证算法以及采用上下文无关文法的模式的文本描述语言等，本书对此进行了补充说明。
本书用法
本书适用于本科三年级以上学生的一季度或一学期的课程。在斯坦福大学，我们把这份讲义用在CS154课程（即自动机和语言理论课程）中。这是一门一季度的课程，Rajeev和Jeffrey都曾经教过。由于授课时间有限，第11章不包括在授课范围以内，其他一些材料（比如较难的多项式时间归约等内容）也省略了。本书的网站（参见下面）包括CS154课程的笔记和教学大纲等材料。
几年前我们发现，许多进入斯坦福大学的研究生都学过一门不包括难解性理论的自动机理论课程。由于斯坦福大学的全体教员相信，对于每一位计算机科学家来说，仅仅停留在知道“NP完全意味着需要花费很长时间”这一层面是远远不够的，充分了解这些思想是十分必要的，所以就有了另外一门课程CS154N，选这个课的学生可以只学习第8～10章。他们实际上学习的是CS154课程大约后三分之一部分的内容，以此来满足CS154N课程的要求。即使在今天，我们仍然发现，每个季度都有一些学生采取这种优化的课程选项。由于这样做几乎不需要额外的努力，所以我们推荐使用这种方法。
预备知识
为了最好地使用本书，读者应当学过一门关于离散数学（如图、树、逻辑、证明技巧等）的课程。我们还假设读者学过一些有关程序设计的课程，熟悉常见的数据结构、递归和主要系统组件（如编译器）的作用等。这些预备知识一般应当包含在大学一、二年级计算机科学课程计划中。
习题
本书包含大量的习题，几乎每个章节都有。我们将较难的习题或其中的某一部分用单个叹号标出，最难的则用两个叹号标出。
某些习题或其中的某一部分标有星号。对于这部分习题，其解答方法可以通过本书的网页获得。这些解答可以公开获得，只限于进行自我检查。需要注意的一点是，在少数情况下，习题B要求修改或改编对另一个习题A的解答。如果A的某些部分有解答，那么你就可以预期B的对应部分也有解答。
Gradiance 在线作业
本书第3版有一个新的特色，即增加了一套由Gradiance公司开发的在线作业系统。教师可以利用它给学生安排课后作业，或者给那些没有选课的学生提供一个特殊的综合课程（不是由老师申请开设的课程），使得他们可以利用这些课后作业作为练习和指导。Gradiance系统所提供的问题和普通问题的形式一样，但会对你提交的解决方案进行检查。如果你提交的答案不正确，系统将会提供一些针对性的建议或反馈意见，以帮助纠正你的解决方案。只要你的老师允许，就可以重复尝试，直到达到满意的分数为止。
所有在北美地区购买这本书第3版的读者，都将自动获得这项Gradiance在线作业服务的授权。更多的信息，请访问Addison-Wesley网站 www.aw.com/gradiance 或者发邮件给 computing@aw.com 。
万维网上的支持
本书的主页是http://www-db.stanford.edu/~ullman/ialc.html。其中包含带星号习题的解答、已知的勘误表、后备材料等。我们希望提供所教CS154课程的所有笔记材料，包括课后作业、习题解答和考试等。
致谢
Craig Silverstein关于“如何进行证明”的讲稿为本书第1章中的一些材料提供了借鉴。对本书第2版手稿（2000年）的评论和勘误来自Zoe Abrams、George Candea、Haowen Chen、Byong-Gun Chun、Jeffrey Shallit、Bret Taylor、Jason Townsend和Erik Uzureau等。
同时，我们也收到了很多有关本书第2版内容勘误的电子邮件，这些读者的名字已经写进了那一版本在线勘误表的致谢中。然而，我们还是希望把那些提出了书中出现的重大错误的人员公布出来，他们是：Zeki Bayram、Sebastian Hick、Kang-Rae Lee、Christian Lemburg、Nezam Mahdavi-Amiri、Dave Majer、A. P. Marathe、Mark Meuleman、Mustafa Sait-Ametov、Alexey Sarytchev、Jukka Suomela、Rod Topor、Po-Lian Tsai、Tom Whaley、Aaron Windsor 和Jacinth H. T. Wu。
非常感谢他们的帮助。当然，剩下的错误都由我们负责。
J. E. H.
R. M.
J. D. U.
纽约州，艾萨克；加州，斯坦福
计算机\计算理论
本书是关于形式语言、自动机理论和计算复杂性方面的经典教材，是三位理论计算大师的巅峰之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、图灵机、不可判定性以及难解问题等内容。
本书已被世界许多著名大学选为计算机理论课程的教材或教学参考书，适合作为高校计算机专业高年级本科生及研究生的教材，还可供从事理论计算工作的研究人员参考。
作者简介
约翰·E. 霍普克罗夫特（John E. Hopcroft） 1986年图灵奖获得者、美国国家工程院院士、美国国家科学院院士、美国国家艺术与科学院院士、中国科学院外籍院士、美国康奈尔大学教授。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。他和Jeffrey D. Ullman一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大学计算机科学系教授。他的研究兴趣包括数据库、数据挖掘、Web搜索和信息检索、机器人等。他于2009年6月意外身亡。
杰弗里·D. 乌尔曼（Jeffrey D. Ullman） 2020年图灵奖获得者、美国国家工程院院士、斯坦福大学计算机科学系名誉教授。他的研究兴趣包括数据库理论、数据库集成、数据挖掘、理论计算等。他和John E. Hopcroft一起获得2010年IEEE颁发的约翰·冯诺依曼奖。
[美]约翰·E.霍普克罗夫特(John E. Hopcroft）拉杰夫·莫特瓦尼（Rajeev Motwani）杰弗里·D.乌尔曼（Jeffrey D. Ullman) 著：约翰·E.霍普克罗夫特（John E. Hopcroft） 1986年图灵奖获得者、美国国家工程院院士、美国国家科学院院士、美国国家艺术与科学院院士、中国科学院外籍院士、美国康奈尔大学教授。他的研究兴趣集中在计算理论方面，尤其是算法分析、自动机理论等。他和Jeffrey D. Ullman一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
拉杰夫·莫特瓦尼（Rajeev Motwani） 斯坦福大学计算机科学系教授。他的研究兴趣包括数据库、数据挖掘、Web搜索和信息检索、机器人等。他于2009年6月意外身亡，享年47岁。
杰弗里·D.乌尔曼（Jeffrey D. Ullman） 2020年图灵奖获得者、美国国家工程院院士、斯坦福大学计算机科学系名誉教授。他的研究兴趣包括数据库理论、数据库集成、数据挖掘、理论计算等。他和John E. Hopcroft一起获得2010年IEEE颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
理论计算机科学是推动计算机技术向前发展的强大动力。自动机、形式语言、可计算性和相关方面内容构成的计算理论，是理论计算机科学的基础内容之一。学习、研究这些内容，不仅为进一步学习、研究理论计算机科学所必需，而且对增强形式化能力和推理能力有重要作用，这些能力对从事计算机技术中的软件形式化等研究，是不可缺少的。
本书是由John E. Hopcroft、Rajeev Motwani和Jeffrey D. Ullman三位计算机学者合作编写的，是非常著名的理论计算机科学著作之一，是世界各国广泛采用的计算机理论专业和计算机工程专业的优秀教材之一。它主要介绍形式语言、自动机、可计算性和相关方面内容，特别注意定义、定理的准确性和严格性，这有利于培养学生形式化和严格的数学推理的能力。本书第1版于1979年发行。第3版有一个新的特色，那就是增加了一套由Gradiance公司开发的在线作业系统。教师可以利用它给学生安排课后作业，或者给那些没有选课的学生提供一个特殊的综合课程（不是由老师申请开设的课程），使得他们可以利用这些课后作业作为练习和指导。然而遗憾的是，Gradiance在线作业系统只适用于购买原版教材的北美地区学生，中国学生还不能使用这个系统，因此，我们在翻译第3版的过程中，对涉及Gradiance系统的内容进行了删减。
这个译本是根据原书第3版翻译的。参加本书翻译工作的有：孙家，负责全书的详细修改和统稿；刘明浩，负责第1～3章及前言、目录的翻译；孙自然，负责第4、5章的翻译；王啸吟，负责第6、7章的翻译；王华，负责第8、9章的翻译；侯姗姗，负责第10、11章及索引的翻译。为了与本书第2版中译本使用的名词、术语保持统一，在翻译过程中我们参考了由刘田、姜晖和王捍贫完成的本书第2版中译本。
由于我们的能力有限，难免有不当之处，敬请读者不吝赐教。
译者序
前言
第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 识别关键字集合的DFA 47
2.4.4 习题 49
2.5 带e 转移的有穷自动机 49
2.5.1 e 转移的用途 49
2.5.2 e-NFA的形式化定义 50
2.5.3 e 闭包 51
2.5.4 e-NFA的扩展转移和语言 52
2.5.5 消除 e 转移 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 语法分析器生成器YACC 133
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 从文法到PDA 164
6.3.2 从PDA到文法 167
6.3.3 习题 170
6.4 确定型PDA 171
6.4.1 确定型PDA的定义 171
6.4.2 正则语言与确定型PDA 172
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 去除e产生式 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 “修改过的”PCP 274
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 把表达式转化成CNF 305
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 无向哈密顿回路与TSP 322
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 类 348
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
