高级搜索  |  搜索帮助
最近的浏览历史
书  名:形式语言与自动机理论(第3版)
  • 作  者: 蒋宗礼、姜守旭
  • 出版时间: 2013-05-01
  • 出 版 社: 清华大学出版社
  • 字  数: 471 千字
  • 印  次: 3-1
  • 印  张: 19
  • 开  本: 16开
  • ISBN: 9787302318026
  • 装  帧: 平装
  • 定  价:¥36.00
电子书价:¥25.20 折扣:70折 节省:¥10.80 vip价:¥25.20 电子书大小:18.86M
配套资源下载:
  • 名称
  • 说明
  • 权限
  • 文件大小
  • 点击图标下载
  • 图书样章
  • 所有用户
  • 256K
共有商品评论0条 查看评论摘要
内容简介
  形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其近30年来在大学讲授该门课程的经验和体会,选择和组织有关内容撰写而成。基于计算机问题求解的需要讨论正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识。其内容特点是抽象和形式化,既有严格的理论证明,又具有很强的构造性。叙述中特别注意引导读者分析与解决问题,以培养学生的形式化描述和抽象思维能力,使学生了解和初步掌握“问题、形式化、自动化(计算机化)”的解题思路。为了便于学生对内容的掌握,附录A还给出了建议的教学设计。
  本书配套出版有《形式语言与自动机理论教学参考书(第3版)》,归纳各章知识点,解读主要内容,解析典型习题。
  本书适合作为计算机学科研究生和高年级本科生的教材,也可供相关专业的学生、教师和科研人员参考。
前言
  
目录
第1章 绪论11.1集合的基础知识2
1.1.1集合及其表示2
1.1.2集合之间的关系4
1.1.3集合的运算5
1.2关系10
1.2.1二元关系10
1.2.2等价关系与等价类11
1.2.3关系的合成12
1.2.4递归定义与归纳证明12
1.2.5关系的闭包15
1.3图15
1.3.1无向图16
1.3.2有向图17
1.3.3树19
1.4语言20
1.4.1什么是语言20
1.4.2形式语言与自动机理论的产生与作用21
1.4.3基本概念23
1.5小结28
习题29

第2章 文法35
2.1启示36
2.2形式定义38
2.3文法的构造46
2.4文法的乔姆斯基体系54
2.5空语句64
2.6小结66
习题66

第3章 有穷状态自动机70
3.1语言的识别70
3.2有穷状态自动机72
3.3不确定的有穷状态自动机83
3.3.1作为对DFA的修改83
3.3.2NFA的形式定义84
3.3.3NFA与DFA等价86
3.4带空移动的有穷状态自动机90
3.5FA是正则语言的识别器94
3.5.1FA与右线性文法94
3.5.2FA与左线性文法98
3.6FA的一些变形99
3.6.1双向有穷状态自动机100
3.6.2带输出的FA101
3.7小结102
习题103

第4章 正则表达式108
4.1启示108
4.2正则表达式的形式定义109
4.3正则表达式与FA等价111
4.3.1正则表达式到FA的等价变换111
4.3.2正则语言可以用正则表达式表示119
4.4正则语言等价模型的总结124
4.5小结126
习题126

第5章 正则语言的性质129
5.1正则语言的泵引理129
5.2正则语言的封闭性134
5.3MyhillNerode 定理与DFA的极小化140
5.3.1MyhillNerode 定理140
5.3.2DFA的极小化148
5.4关于正则语言的判定算法156
5.5小结157
习题158

第6章 上下文无关语言160
6.1上下文无关文法160
6.1.1上下文无关文法的派生树161
6.1.2二义性166
6.1.3自顶向下的分析和自底向上的分析169
6.2上下文无关文法的化简171
6.2.1去无用符号172
6.2.2去ε产生式175
6.2.3去单一产生式组178
6.3乔姆斯基范式181
6.4格雷巴赫范式184
6.5自嵌套文法189
6.6小结190
习题190

第7章 下推自动机194
7.1基本定义194
7.2PDA与CFG等价200
7.2.1PDA用空栈接受和用终止状态接受等价200
7.2.2PDA与CFG等价203
7.3小结212
习题212

第8章 上下文无关语言的性质215
8.1上下文无关语言的泵引理215
8.2上下文无关语言的封闭性221
8.3上下文无关语言的判定算法226
8.3.1L空否的判定226
8.3.2L是否有穷的判定227
8.3.3x是否为L的句子的判定 228
8.4小结230
习题230

第9章 图灵机231
9.1基本概念232
9.1.1基本图灵机232
9.1.2图灵机作为非负整函数的计算模型239
9.1.3图灵机的构造241
9.2图灵机的变形247
9.2.1双向无穷带图灵机247
9.2.2多带图灵机250
9.2.3不确定的图灵机252
9.2.4多维图灵机253
9.2.5其他图灵机255
9.3通用图灵机257
9.4几个相关的概念259
9.4.1可计算性259
9.4.2P与NP相关问题259
9.5小结260
习题260

第10章 上下文有关语言263
10.1图灵机与短语结构文法的等价性263
10.2线性有界自动机及其与上下文有关文法的等价性266
10.3小结267
习题267

附录A 教学设计269
A.1课程内容体系269
A.1.1基本描述269
A.1.2教学定位269
A.1.3知识点与学时分配270
A.2课程的讲授271
A.2.1重点与难点271
A.2.2讲授中应注意的方法等问题275
A.3作业276
A.3.1指导思想276
A.3.2关于大作业和实验276
A.4考试与成绩记载276
A.4.1成绩评定276
A.4.2考题设计276
附录B 缩写符号278词汇索引280
参考文献287
Copyright(C)清华大学出版社有限公司,All Rights Reserved 京ICP备10035462号 联系我们