形式语言与自动机导论（原书第7版）

定　价：¥129.00

作　者：	[美]彼得·林茨 ,[美]苏珊·H. 罗杰
出版社：	机械工业出版社
丛编项：
标　签：	暂缺

购买这本书可以去

当当网 (¥96.70)

ISBN：	9787111767527	出版时间：	2025-02-01	包装：	平装-胶订
开本：	16开	页数：		字数：

内容简介

　　本书是理论计算机科学方面的经典教材，主要讨论形式语言与自动机理论、可计算性理论和计算复杂性理论等内容。本书强调定义和定理的准确性和严谨性，但在形式化证明中又非常注重符合直觉的理解，避免多余的数学细节。本书分为理论和应用两个部分：理论部分主要介绍有穷自动机、正则语言和文法、上下文无关语言和文法、下推自动机、图灵机、形式语言和自动机的层次结构以及计算复杂性等内容，应用部分主要介绍编译器和解析、LL解析以及LR解析。本书可帮助读者熟悉计算机科学的基础和原理，加强严格的形式化数学证明的能力，适合高等院校计算机科学及相关专业的学生学习，也适合理论计算机科学方向的研究人员参考。

作者简介

　　彼得·林茨（Peter Linz）加利福尼亚大学戴维斯分校计算机科学系荣休教授。他的研究重点是数值分析理论，致力于构建可靠的数值方法并将其用于科学计算中问题求解环境的设计。除本书外，他还著有Exploring Numerical Methods： An Introduction to Scientific Computing。他拥有威斯康星大学博士学位。苏珊·H. 罗杰（Susan H. Rodger）杜克大学计算机科学实践教授。她的主要贡献是开发了大量用于理论计算机科学教育的可视化和交互软件，其中，JFLAP软件被世界各地的大学用于形式语言与自动机的实验教学。她曾获得2023年ACM SIGCSE计算机科学教育杰出贡献奖，2019年IEEE计算机协会Taylor L. Booth教育奖，2013年ACM Karl V. Karlstrom杰出教育家奖，2019年杜克大学三一学院David和Janet Vaughn Brooks杰出教学奖。她拥有普渡大学计算机科学博士学位。

图书目录

目录
译者序
前言
理论部分
第 1 章计算理论概论　　　　　　 2
1.1 数学预备知识和符号表示　　　 3
1.1.1 集合　　　　　　　　　3
1.1.2 函数和关系　　　　　　　5
1.1.3 图和树　　　　　　　 8
1.1.4 证明方法　　　　　　　 9
1.2 三个基本概念　　　　　　　15
1.2.1 语言　　　　　　　　　15
1.2.2 文法　　　　　　　　 19
1.2.3 自动机　　　　　　　 24
1.3 应用 *　　　　　　　　 27
第 2 章有穷自动机　　　　　　　 33
2.1 确定的有穷接受器　　　　　 33
2.1.1 确定的接受器和转移图　　 34
2.1.2 语言和 DFA 的语言　　　　36
2.1.3 正则语言　　　　　　 40
2.2 非确定的有穷接受器　　　　 44
2.2.1 非确定的接受器的定义　　 44
2.2.2 为什么需要非确定性？　　 48
2.3 确定与非确定的有穷接受器的
等价性　　　　　　　　 51
2.4 减少有穷自动机中状态的
化简 *　　　　　　　　 58
第 3 章正则语言和正则文法　　　　 64
3.1 正则表达式.　　　　　　　64
3.1.1 正则表达式的形式定义　　 64
3.1.2 正则表达式所关联的语言　　 65
3.2 正则表达式和正则语言的
联系　　　　　　　　　　70
3.2.1 正则表达式表示正则语言　　 70
3.2.2 正则语言的正则表达式　　 72
3.2.3 描述简单模式的正则表达式　 77
3.3 正则文法　　　　　　　　 80
3.3.1 左线性文法和右线性文法　　 80
3.3.2 右线性文法生成正则语言　　 81
3.3.3 正则语言的右线性文法　　 83
3.3.4 正则语言和正则文法的
等价性　　　　　　　　 85
第 4 章正则语言的性质　　　　　 89
4.1 正则语言的封闭性　　　　　 90
4.1.1 简单集合运算的封闭性　　 90
4.1.2 其他运算的封闭性　　　　 92
4.2 正则语言的基本问题　　　　 99
4.3 识别非正则语言　　　　　　102
4.3.1 鸽巢原理的使用　　　　　102
4.3.2 泵引理　　　　　　 103
第 5 章上下文无关语言　　　　　　113
5.1 上下文无关文法　　　　　　114
5.1.1 上下文无关文法示例　　　 114
5.1.2 最左推导和最右推导　　　 116
5.1.3 推导树　　　　　　 117
5.1.4 句型和推导树的关系　　　 119
5.2 解析和歧义性　　　　　　 123
5.2.1 解析和成员资格　　　　　123
5.2.2 文法和语言的歧义性　　　 127
5.3 上下文无关文法和程序设计
语言　　　　　　　　　 132
第 6 章上下文无关文法的化简和
范式　　　　　　　　　　135
6.1 文法转换的方法　　　　　　136
6.1.1 有用的代入规则　　　　　136
6.1.2 消除无用的产生式　　　 138
6.1.3 消除 λ-产生式　　　　 141
6.1.4 消除单元产生式　　　　　143
6.2 两种重要的范式　　　　　　149
6.2.1 乔姆斯基范式　　　　　150
6.2.2 格雷巴赫范式　　　　　152
6.3 上下文无关文法的成员资格
判定算法 *　　　　　　　 156
第 7 章下推自动机　　　　　　 159
7.1 非确定的下推自动机　　　 160
7.1.1 下推自动机的定义　　　 160
7.1.2 下推自动机接受的语言　　　163
7.2 下推自动机和上下文无关
语言　　　　　　　　　 168
7.2.1 上下文无关语言对应的下推
自动机　　　　　　 168
7.2.2 下推自动机对应的上
下文无关文法　　　　　　173
7.3 确定的下推自动机和确定的
上下文无关语言　　　　　　179
7.4 确定的上下文无关语言的
文法 *　　　　　　　　　184
第 8 章上下文无关语言的性质　　　 188
8.1 两个泵引理　　　　　　 188
8.1.1 上下文无关语言的泵引理　 189
8.1.2 线性语言的泵引理　　　 192
8.2 上下文无关语言的封闭性
和判定算法　　　　　　 196
8.2.1 上下文无关语言的封闭性　 197
8.2.2 上下文无关语言的一些可判
定性质　　　　　　 200
第 9 章图灵机　　　　　　　　　204
9.1 标准的图灵机　　　　　　 204
9.1.1 图灵机的定义　　　　　205
9.1.2 作为语言接受器的图灵机　 209
9.1.3 作为转换器的图灵机　　　 212
9.2 完成复杂任务的组合图灵机　218
9.3 图灵论题　　　　　　　　　222
第 10 章图灵机的其他模型　　　　 225
10.1 对图灵机的小改动　　　　 225
10.1.1 自动机类的等价性　　　　226
10.1.2 可驻停图灵机　　　　226
10.1.3 半无穷带图灵机　　　　 228
10.1.4 离线图灵机　　　　　　 229
10.2 具有更复杂存储的图灵机　　232
10.2.1 多带图灵机　　　　　　 232
10.2.2 多维图灵机　　　　　　 234
10.3 非确定的图灵机　　　　　 236<>