作者:
John E. Hopcroft
/
Rajeev Motwani
/
Jeffrey D. Ullman
出版社: 机械工业出版社
原作名: Introduction to Automata Theory, Languages and Computation
译者: 孙家骕 等
出版年: 2008-7-1
页数: 366
定价: 49.00元
装帧: 平装
丛书: 计算机科学丛书
ISBN: 9787111240358
出版社: 机械工业出版社
原作名: Introduction to Automata Theory, Languages and Computation
译者: 孙家骕 等
出版年: 2008-7-1
页数: 366
定价: 49.00元
装帧: 平装
丛书: 计算机科学丛书
ISBN: 9787111240358
内容简介 · · · · · ·
本书是关于形式语言、自动机理论和计算复杂性方面的经典教材,是三位理论计算大师的巅峰之作,现已更新到第3版。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。
作者简介 · · · · · ·
John E. Hopcroft,在斯坦福大学获得博士学位,现为康奈尔大任康奈尔大学工程学院院长。他是1986年图灵奖获得者。他的研究兴趣集中在计算理论方面,尤其是算法分析、自动机理论等。
目录 · · · · · ·
出版者的话
译者序
前言
第1章 自动机:方法与体验
1.1 为什么研究自动机理论
1.1.1 有穷自动机简介
1.1.2 结构表示法
1.1.3 自动机与复杂性
1.2 形式化证明简介
1.2.1 演绎证明
1.2.2 求助于定义
1.2.3 其他定理形式
1.2.4 表面上不是“如果-则”命题的定理
1.3 其他的证明形式
1.3.1 证明集合等价性
1.3.2 逆否命题
1.3.3 反证法
1.3.4 反例
1.4 归纳证明
1.4.1 整数上的归纳法
1.4.2 更一般形式的整数归纳法
1.4.3 结构归纳法
1.4.4 互归纳法
1.5 自动机理论的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 语言
1.5.4 问题
1.6 小结
1.7 参考文献
第2章 有穷自动机
2.1 有穷自动机的非形式化描述
2.1.1 基本规则
2.1.2 协议
2.1.3 允许自动机忽略动作
2.1.4 整个系统成为一个自动机
2.1.5 用乘积自动机验证协议
2.2 确定型有穷自动机
2.2.1 确定型有穷自动机的定义
2.2.2 DFA如何处理串
2.2.3 DFA的简化记号
2.2.4 把转移函数扩展到串
2.2.5 DFA的语言
2.2.6 习题
2.3 非确定型有穷自动机
2.3.1 非确定型有穷自动机的非形式化观点
2.3.2 非确定型有穷自动机的定义
2.3.3 扩展转移函数
2.3.4 NFA的语言
2.3.5 确定型有穷自动机与非确定型有穷自动机的等价性
2.3.6 子集构造的坏情形
2.3.7 习题
2.4 应用:文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非确定型有穷自动机
2.4.3 识别关键字集合的DFA
2.4.4 习题
2.5 带e 转移的有穷自动机
2.5.1 e 转移的用途
2.5.2 e-NFA的形式化定义
2.5.3 e 闭包
2.5.4 e-NFA的扩展转移和语言
2.5.5 消除 e 转移
2.5.6 习题
2.6 小结
2.7 参考文献
第3章 正则表达式与正则语言
3.1 正则表达式
3.1.1 正则表达式运算符
3.1.2 构造正则表达式
3.1.3 正则表达式运算符的优先级
3.1.4 习题
3.2 有穷自动机和正则表达式
3.2.1 从DFA到正则表达式
3.2.2 通过消除状态把DFA转化为正则表达式
3.2.3 把正则表达式转化为自动机
3.2.4 习题
3.3 正则表达式的应用
3.3.1 UNIX中的正则表达式
3.3.2 词法分析
3.3.3 查找文本中的模式
3.3.4 习题
3.4 正则表达式代数定律
3.4.1 结合律与交换律
3.4.2 单位元与零元
3.4.3 分配律
3.4.4 幂等律
3.4.5 与闭包有关的定律
3.4.6 发现正则表达式定律
3.4.7 检验正则表达式代数定律
3.4.8 习题
3.5 小结
3.6 参考文献
第4章 正则语言的性质
第5章 上下文无关文法及上下文无关语言
第6章 下推自动机
第7章 上下文无关语言的性质
第8章 图灵机导引
第9章 不可判定性
第10章 难解问题
第11章 其他问题类
索引
· · · · · · (收起)
译者序
前言
第1章 自动机:方法与体验
1.1 为什么研究自动机理论
1.1.1 有穷自动机简介
1.1.2 结构表示法
1.1.3 自动机与复杂性
1.2 形式化证明简介
1.2.1 演绎证明
1.2.2 求助于定义
1.2.3 其他定理形式
1.2.4 表面上不是“如果-则”命题的定理
1.3 其他的证明形式
1.3.1 证明集合等价性
1.3.2 逆否命题
1.3.3 反证法
1.3.4 反例
1.4 归纳证明
1.4.1 整数上的归纳法
1.4.2 更一般形式的整数归纳法
1.4.3 结构归纳法
1.4.4 互归纳法
1.5 自动机理论的中心概念
1.5.1 字母表
1.5.2 串
1.5.3 语言
1.5.4 问题
1.6 小结
1.7 参考文献
第2章 有穷自动机
2.1 有穷自动机的非形式化描述
2.1.1 基本规则
2.1.2 协议
2.1.3 允许自动机忽略动作
2.1.4 整个系统成为一个自动机
2.1.5 用乘积自动机验证协议
2.2 确定型有穷自动机
2.2.1 确定型有穷自动机的定义
2.2.2 DFA如何处理串
2.2.3 DFA的简化记号
2.2.4 把转移函数扩展到串
2.2.5 DFA的语言
2.2.6 习题
2.3 非确定型有穷自动机
2.3.1 非确定型有穷自动机的非形式化观点
2.3.2 非确定型有穷自动机的定义
2.3.3 扩展转移函数
2.3.4 NFA的语言
2.3.5 确定型有穷自动机与非确定型有穷自动机的等价性
2.3.6 子集构造的坏情形
2.3.7 习题
2.4 应用:文本搜索
2.4.1 在文本中查找串
2.4.2 文本搜索的非确定型有穷自动机
2.4.3 识别关键字集合的DFA
2.4.4 习题
2.5 带e 转移的有穷自动机
2.5.1 e 转移的用途
2.5.2 e-NFA的形式化定义
2.5.3 e 闭包
2.5.4 e-NFA的扩展转移和语言
2.5.5 消除 e 转移
2.5.6 习题
2.6 小结
2.7 参考文献
第3章 正则表达式与正则语言
3.1 正则表达式
3.1.1 正则表达式运算符
3.1.2 构造正则表达式
3.1.3 正则表达式运算符的优先级
3.1.4 习题
3.2 有穷自动机和正则表达式
3.2.1 从DFA到正则表达式
3.2.2 通过消除状态把DFA转化为正则表达式
3.2.3 把正则表达式转化为自动机
3.2.4 习题
3.3 正则表达式的应用
3.3.1 UNIX中的正则表达式
3.3.2 词法分析
3.3.3 查找文本中的模式
3.3.4 习题
3.4 正则表达式代数定律
3.4.1 结合律与交换律
3.4.2 单位元与零元
3.4.3 分配律
3.4.4 幂等律
3.4.5 与闭包有关的定律
3.4.6 发现正则表达式定律
3.4.7 检验正则表达式代数定律
3.4.8 习题
3.5 小结
3.6 参考文献
第4章 正则语言的性质
第5章 上下文无关文法及上下文无关语言
第6章 下推自动机
第7章 上下文无关语言的性质
第8章 图灵机导引
第9章 不可判定性
第10章 难解问题
第11章 其他问题类
索引
· · · · · · (收起)
丛书信息
· · · · · ·
计算机科学丛书(共612册),
这套丛书还有
《算法基础:Python和C#语言实现(原书第2版)》《嵌入式计算系统设计原理 第2版》《C语言程序设计与问题求解(原书第7版)》《软件可靠性方法》《数据库系统概念(本科教学版)》
等
。
喜欢读"自动机理论、语言和计算导论(原书第3版)"的人也喜欢的电子书 · · · · · ·
支持 Web、iPhone、iPad、Android 阅读器
喜欢读"自动机理论、语言和计算导论(原书第3版)"的人也喜欢 · · · · · ·
- 程序设计语言 8.4
- Scala程序设计(第2版) 8.4
- 编译原理 9.1
- 编译器构造C语言描述 7.9
- 高级编译器设计与实现 8.7
- 编译器设计 8.4
- OpenCL异构计算 7.5
- 交互式计算机图形学 8.7
- C语言接口与实现 8.2
自动机理论、语言和计算导论(原书第3版)的书评 · · · · · · ( 全部 6 条 )
内容不错,而翻译就...
内容不错啊,讲的挺详细,即使我这个非计算机专业的拿来看也能顺着看下去。当然,前提是你能忍受得了这翻译。有的地方也太“直译”了,有的地方读起来有当初看GRE长难句的感觉。慢慢看下去习惯了翻译也就觉得书还是不错的。
(展开)
> 更多书评 6篇
论坛 · · · · · ·
比Sipser那本难读 | 来自哗呀哩呜 | 3 回应 | 2015-09-23 03:27:49 |
这本书的其他版本 · · · · · · ( 全部13 )
-
机械工业出版社 (2022)暂无评分 1人读过
-
Addison Wesley (2006)8.7分 48人读过
-
机械工业出版社 (2008)9.2分 81人读过
-
机械工业出版社 (2004)8.4分 70人读过
在哪儿借这本书 · · · · · ·
以下书单推荐 · · · · · · ( 全部 )
- 计算机科学丛书·机械工业出版社 (a_4930g)
- 程序解体诸因 (在坡华子)
- IT 一级 信息技术(智力层次-实用性) 1.1.1 (ajian005)
- 计算机科学 (月亮)
- 印象较深的计算机书 (新陈)
谁读这本书? · · · · · ·
二手市场
· · · · · ·
订阅关于自动机理论、语言和计算导论(原书第3版)的评论:
feed: rss 2.0
0 有用 IdleMind 2012-12-21 18:13:45
大四选修课教材,自动机、编译原理基础理论。
0 有用 继续发育 2012-01-18 18:59:36
太罗嗦,找不到重点
0 有用 歪的 2012-01-05 23:24:38
有穷自动机,下推自动机,图灵机,可判定性问题,难解问题 循序渐进,非形式化与形式化并重
0 有用 马蹄北去 2017-06-22 01:31:13
正则语言/有限自动机+上下文无关语言/下推自动机部分
0 有用 茂盛 2019-11-20 13:17:43
翻译不好,即使我明白里面的知识都很难读下去。相比较更喜欢Sipser的《计算理论导引》
0 有用 6*9=42 2023-03-12 21:46:55 北京
【Others】散修35th.其实只是英文版读不明白的时候拿来当翻译用(
0 有用 豆友11nFub_irU 2022-04-09 17:42:45
翻译就是垃圾,本来应该是一本不错的书
0 有用 塔纳托斯 2022-01-02 15:36:42
@2021-01-18 21:19:46
0 有用 茂盛 2019-11-20 13:17:43
翻译不好,即使我明白里面的知识都很难读下去。相比较更喜欢Sipser的《计算理论导引》
0 有用 taotao 2019-10-03 23:58:07
甚至不如机翻