本书是计算理论方面的优秀教材之一,包括上下文无关文法、上下文无关文法范式、有限自动机、正则语言的性质、下推自动机和上下文无关语言、图灵机、图灵可计算函数、乔姆斯基层次、判定问题与丘奇图灵机、不可判定性、Mu-递归函数、时间复杂性、库克定理、NP-完全问题、LL(k)文法以及LR(k)文法等问题。本书不仅介绍了计算机科学的基础,而且通过概念的严格表述,以及使用通俗的例子来阐释定理,从而帮助学生提高数学论证能力以及对计算理论知识的全面深入的理解。书中每章后面都有附有大量习题,通过完成这些习题,学生可以加深对本章内容的理解。
本书可以用作计算机科学、计算机工程及其相关专业的教材,也可以作为从事计算理论、形式语言以及计算机系统研发的研究人员和工程技术人员的参考书。
出版者的话
专家指导委员会
译者序
前言
绪论
第一部分 基础
第1章 数学预备知识
1.1 集合论
1.2 笛卡儿积、关系和函数
1.3 等价关系
1.4 可数集合和不可数集合
1.5 对角化和自反
1.6 递归定义
1.7 数学归纳
1.8 有向图
1.9 练习
参考文献注释
第2章 语言
2.1 字符串和语言
2.2 语言的有穷规格说明
2.3 正则集合和表达式
2.4 正则表达式和文本搜索
2.5 练习
参考文献注释
第二部分 文法、自动机和语言
第3章 上下文无关文法
3.1 上下文无关文法和语言
3.2 文法和语言的例子
3.3 正则文法
3.4 验证文法
3.5 最左推导和二义性
3.6 上下文无关文法和编程语言定义
3.7 练习
参考文献注释
第4章 上下文无关文法范式
4.1 文法转换
4.2 消去入规则
4.3 去掉链规则
4.4 无用符
4.5 乔姆斯基范式
4.6 CYK算法
4.7 去掉直接左递归
4.8 格立巴赫范式
4.9 练习
参考文献注释
第5章 有限自动机
5.1 一个有限状态自动机
5.2 确定型有限自动机
5.3 状态图和例子
5.4 非确定型有限自动机
5.5 λ-转换
5.6 去掉非确定性
5.7 DFA的最小化
5.8 练习
参考文献注释
第6章 正则语言的性质
6.1 有限状态机接收正则语言
6.2 表达式图
6.3 正则文法和有限自动机
6.4 正则语言的封闭性质
6.5 非正则语言
6.6 规则语言的泵引理
6.7 Myhill-Nerode定理
6.8 练习
参考文献注释
第7章 下推自动机和上下文无关语言
7.1 下推自动机
7.2 PDA的变种
7.3 上下文无关语言的接收
7.4 上下文无关语言的泵引理
7.5 上下文无关语言的封闭性
7.6 练习
参考文献注释
第三部分 可计算性
第8章 图灵机
8.1 标准图灵机
8.2 作为语言接收器的图灵机
8.3 可供选择接收标准
8.4 多道图灵机
8.5 双向图灵机
8.6 多带图灵机
8.7 非确定型图灵机
8.8 用来枚举语言的图灵机
8.9 练习
参考文献注释
第9章 图灵可计算函数
9.1 函数的计算
9.2 数值计算
9.3 图灵机的顺序操作
9.4 函数的合成
9.5 不可计算函数
9.6 关于编程语言
9.7 练习
参考文献注释
第10章 乔姆斯基层次
10.1 无限制文法
10.2 上下文有关文法
10.3 线性有界自动机
10.4 乔姆斯基层次
10.5 练习
参考文献注释
第11章 判定问题与丘奇—图灵论题
11.1 判定问题的描述
11.2 判定问题和递归语言
11.3 问题归约
11.4 丘奇—图灵论题
11.5 通用机
11.6 练习
参考文献注释
第12章 不可判定性
12.1 图灵机的停机问题
12.2 问题归约和不可判定性
12.3 其他的停机问题
12.4 莱斯定理
12.5 不可解决的词问题
12.6 波斯特对应问题
12.7 上下文无关文法中的不可判定问题
12.8 练习
参考文献注释
第13章 Mu-递归函数
13.1 原始递归函数
13.2 一些原始递归函数
13.3 有界操作符
13.4 除法函数
13.5 歌德尔数字和串值递归
13.6 可计算部分函数
13.7 图灵可计算函数和Mu-递归函数
13.8 修订的丘奇—图灵论题
13.9 练习
参考文献注释
第四部分 计算复杂性
第14章 时间复杂性
14.1 复杂性度量
14.2 增长的速度
14.3 图灵机的时问复杂性
14.4 复杂性和图灵机的变种
14.5 线性加速
14.6 语言时间复杂性的属性
14.7 计算机计算的模拟
14.8 练习
参考文献注释
第15章 P、NP和库克定理
15.1 非确定型图灵机的时间复杂性
15.2 P类和NP类
15.3 问题表示和复杂性
15.4 判定问题和复杂性类
15.5 哈密尔顿回路问题
15.6 多项式时间归约
15.7 P=NP?
15.8 可满足性问题
15.9 复杂类的关系
15.10 练习
参考文献注释
第16章 NP-完全问题
16.1 归约和NP-完全问题
16.2 三元可满足性问题
16.3 三元可满足性的归约
16.4 归约和子问题
16.5 最优化问题
16.6 近似算法
16.7 近似方案
16.8 练习
参考文献注释
第17章 其他复杂性类
17.1 派生的复杂性类
17.2 空间复杂性
17.3 空间复杂性和时间复杂性的关系
17.4 P-空间,NP-空间和萨维奇定理
17.5 P-空间完全性
17.6 一个难解问题
17.7 练习
参考文献注释
第五部分 确定型语法分析
第18章 语法分析引论
18.1 文法图
18.2 自顶向下语法分析
18.3 归约和自底向上语法分析
18.4 自底向上语法分析器
18.5 语法分析和编译
18.6 练习
参考文献注释
第19章 LL(k)文法
19.1 上下文无关文法中的预读
19.2 FIRST集合、FOLLOW集合和预读集合
19.3 强LL(k)语法
19.4 FIRSTk集合的构造
19.5 FOLLOWk集合的构造
19.6 强LL(1)文法
19.7 强LL(k)分析器
19.8 LL(k)文法
19.9 练习
参考文献注释
第20章 LR(k)文法
20.1 LR(0)上下文
20.2 LR(0)分析器
20.3 LR(0)机
20.4 被LR(0)机接收
20.5 LR(1)文法
20.6 练习
参考文献注释
附录Ⅰ 标记索引
附录Ⅱ 希腊字母表
附录Ⅲ ASC Ⅱ字符集
附录Ⅲ Java的BNF范式定义
参考文献
索引
《邻里杂货:澳门士多店主口述历史》内容简介:本书为“澳门口述历史丛书”之一,主要由对十一位澳门士多店主的访谈整理而成。他们
本书脱胎于作者在C语言的摇篮——贝尔实验室教授C语言的讲稿,几乎涵盖了C语言各个方面的难点,并包含了一些其他书籍很少分析到的
电波传播的特性是研究移动通信系统首先要遇到问题,称动传播环境的特性不仅是所有移动通信理论研究的基础,也更直接关系到工程设
《阅读摄影:郭力昕摄影批评》内容简介:《阅读摄影》是一部呈现郭力昕这十五年间关心当代摄影实践与发展的相对完整的批评性思考的
《JAVA核心技术卷2:高级特征》是Java技术权威指南,全面覆盖Java技术的高级主题,包括流与文件、XML、网络、数据库编程、高级Swi
郑泽宇,现为才云科技(Caicloud.io)联合创始人、首席大数据科学家。针对分布式TensorFlow上手难、管理难、监控难、上线难等问题
馬克.古德曼MarcGoodman全球資訊安全專家,現為「國際刑警組織」((Interpol)資深顧問,並且擔任街頭警察。矽谷奇點大學(Singula
CATIA V5R20快速入门.进阶与精通-(含多媒体DVD光盘2张) 本书特色 本书是全面、系统学习和运用catia v5r20软件的快速入门、进阶与精通书籍...
《唤醒孩子学习天赋》内容简介:1800000粉丝的育儿账号“科学小子钦”主理人 赵邈 力作 在陪伴中总结心得,在实践中改良方法 发掘孩
信息系统项目管理师教程-(第2版) 本书特色 根据人事部、信息产业部文件,计算机技术与软件专业技术资料考试纳入全国专业技术人员职业资格证书制度的统一规划。通过考...
《出纳实务》内容简介:本教材构建了以职业岗位能力为导向的项目教学体系,教材中所选用的会计核算资料均采集于企业出纳岗位上经常
samuelp.harbisoniii于卡内基—梅隆大学获得计算机科学博士学位,现任carlow学院的计算机科学系副教授。他曾就职于德州仪器和ta
五笔字型汉字速查一本通(双色版) 内容简介 五笔字型输入法是王永民教授发明的一种完全依照汉字字形进行编码的汉字输入方法,五笔字型发展到今天,共经历了三个版本,即...
《信息图表设计入门》是一本信息图表制作的实用入门书。信息视觉化是一种潮流,无论是商业宣传活动、专业设计领域还是制作供非专
全国专业技术人员计算机应用能力考试考前冲刺WORD2003中文字处理 本书特色 《全国专业技术人员计算机应用能力考试考前冲刺:Word 2003中文字处理》:紧...
《新零售进化论》内容简介:本书主要介绍了新零售的进化现象和规律,提出了新零售的第一性原理是物理数据二重性,即在新零售时代,
《小狐狸勇闯《山海经》·四海八荒(平装)》内容简介:小狐狸是一个地图迷,无意在爷爷书房里发现一张“山海经”地图,他拿起放大
本书系统讲解数据结构和算法,并分析了算法的复杂性。本书选择Jaya语言以面向对象的方式描述数据结构,还特别强调了封装和分解的
MacromediaFlash是全球25000万用户在Web上发布多媒体信息的实际标准。本书是关ActionScript(Flash的面向对象编程语言)的完整而...
《天使说》内容简介:如何在早期投资时获得天使投资人的青睐? 在商业模式与行业选择上应该何去何从? 什么样的创业者是靠谱的?什