自动机理论、语言和计算导论（原书第3版·典藏版）

作者: [美] 约翰·E. 霍普克罗夫特（John E. Hopcroft）

出版社: 机械工业出版社

出版时间: 2022-05

版次: 1

ISBN: 9787111704294

定价: 119.00

装帧: 其他

开本: 16开

纸张: 胶版纸

页数: 380页

字数: 552千字

分类: 计算机与互联网

8人买过

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

前言

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

5.3.3   标记语言134

5.3.4   XML和文档类型定义135

5.3.5   习题140

5.4   文法和语言的歧义性141

5.4.1   歧义文法141

5.4.
内容简介:
本书是关于形式语言、自动机理论和计算复杂性方面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明，使用图来帮助阐明思想，并包含了大量的难度各异的示例和习题，以便读者确认和加深对内容的理解。本书已被世界许多著名大学作为计算机理论课程的教材或教学参考书，适合作为高校计算机专业高年级本科生及研究生的教材，还可供从事理论计算工作的研究人员参考。
作者简介:
约翰·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颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
目录:
译者序

前言

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

5.3.3   标记语言134

5.3.4   XML和文档类型定义135

5.3.5   习题140

5.4   文法和语言的歧义性141

5.4.1   歧义文法141

5.4.