扫一扫
关注中图网
官方微博
本类五星书更多>
-
>
决战行测5000题(言语理解与表达)
-
>
软件性能测试.分析与调优实践之路
-
>
第一行代码Android
-
>
深度学习
-
>
Unreal Engine 4蓝图完全学习教程
-
>
深入理解计算机系统-原书第3版
-
>
Word/Excel PPT 2013办公应用从入门到精通-(附赠1DVD.含语音视频教学+办公模板+PDF电子书)
自动机理论、语言和计算导论(原书第3版·典藏版) 版权信息
- ISBN：9787111704294
- 条形码：9787111704294 ; 978-7-111-70429-4
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>
自动机理论、语言和计算导论(原书第3版·典藏版) 内容简介
本书是关于形式语言、自动机理论和计算复杂性方面的经典之作。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。本书在定义和证明中使用了很多细节和直观说明，使用图来帮助阐明思想，并包含了大量的难度各异的示例和习题，以便读者确认和加深对内容的理解。本书已被世界许多有名大学作为计算机理论课程的教材或教学参考书，适合作为高校计算机专业高年级本科生及研究生的教材，还可供从事理论计算工作的研究人员参考。<br>
自动机理论、语言和计算导论(原书第3版·典藏版) 目录
译者序
前言
第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.
前言
第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.
展开全部
自动机理论、语言和计算导论(原书第3版·典藏版) 作者简介
约翰·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颁发的约翰·冯诺依曼奖，以表彰其“为自动机和语言理论领域奠定基础，以及对理论计算机科学的许多开创性贡献”。
书友推荐
- >
回忆爱玛侬
回忆爱玛侬
¥23.0¥32.8 - >
伯纳黛特,你要去哪(2021新版)
伯纳黛特,你要去哪(2021新版)
¥15.9¥49.8 - >
中国人在乌苏里边疆区:历史与人类学概述
中国人在乌苏里边疆区:历史与人类学概述
¥35.5¥48.0 - >
人文阅读与收藏·良友文学丛书:一天的工作
人文阅读与收藏·良友文学丛书:一天的工作
¥14.7¥45.8 - >
自卑与超越
自卑与超越
¥12.7¥39.8 - >
罗庸西南联大授课录
罗庸西南联大授课录
¥13.8¥32.0 - >
随园食单
随园食单
¥15.4¥48.0 - >
名家带你读鲁迅:故事新编
名家带你读鲁迅:故事新编
¥13.0¥26.0
本类畅销
-
”互联网+“时代计算机算法的应用及其实践研究
¥19.9¥59 -
微服务设计
¥52.8¥69 -
图说深度学习:用可视化方法理解复杂概念
¥109¥188 -
计算机基础
¥17.2¥31 -
改变未来的九大算法
¥50¥68 -
生成式AI入门与AWS实战
¥77.8¥99.8
