计算机科学丛书 自动机理论、语言和计算导论 原书第3版作者:(美)JohnE.Hopcroft著 孙家骕译出版时间: 2008.07丛编项: 计算机科学丛书内容简介 本书是关于形式语言、自动机理论和计算复杂性方面的经典教材,是三位理论计算大师的巅峰之作,现已更新到第3版。书中涵盖了有穷自动机、正则表达式与语言、正则语言的性质、上下文无关文法及上下文无关语言、下推自动机、上下文无关语言的性质、图灵机、不可判定性以及难解问题等内容。 本书已被世界许多著名大学采用为计算机理论课程的教材或教学参考书,适合作为国内高校计算机专业高年级本科生或研究生的教材,还可供从事理论计算工作的研究人员参考。 本书特点: 以简洁和易理解的方式讲述理论概念。 强调理论的现代应用。 使用大量的图来帮助表达概念。 提供定义和证明的更多细节。 每章提供大量难易程度不同的练习。目录出版者的话译者序前言第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 识别关键字集合的DFA2.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章 其他问题类索引 上一篇: 玻璃笼子:自动化时代和我们的未来 下一篇: 图解智能控制系统应用手册