形式语言与自动机理论引论（中文版） / 计算机科学与技术学科前沿丛书、计算机科学与技术学科研究生系列教材
￥39.00定价
作者： 蒋宗礼，姜守旭
出版时间：2017-03
出版社：清华大学出版社
- 清华大学出版社
- 9787302456025
- 1-1
- 60343
- 16开
- 2017-03
- 工学
- 计算机科学与技术
- TP301-43
- 计算机
内容简介
形式语言与自动机理论因其以体现计算学科中模型描述、模型研究和模型计算为问题求解的主要特征而成为计算机科学与技术、软件工程、网络空间安全等计算机类学科教育的*重要的内容之一。本书按照我国当前计算机类及相关学科研究生教育实际需求，结合作者30余年的教学实践编著而成，以正则语言与上下文无关语言的文法、识别模型及其性质，以及图灵机基本知识为载体，分9章讨论相关内容，力图强化学生基于模型的建立、研究、处理，实现问题求解的意识，让学生掌握相应的基本方法，提升解决问题的能力与水平。本书适合计算机类及相关学科研究生使用，也可以供相关专业高年级本科生、教师和科研人员参考。
目录
目录CONTENTS
第1章语言与文法1
1.1语言2
1.1.1什么是语言2
1.1.2形式语言与自动机理论的产生2
1.1.3基本概念3
1.2文法9
1.3文法的构造18
1.4文法的乔姆斯基体系26
1.5空语句36
1.6小结38
习题38
第2章有穷状态自动机44
2.1语言的识别44
2.2有穷状态自动机46
2.3不确定的有穷状态自动机57
2.3.1作为对DFA的修改57
2.3.2NFA的形式定义58
2.3.3NFA与DFA等价60
2.4带空移动的有穷状态自动机64
2.5FA是正则语言的识别器68
2.5.1FA与右线性文法68
2.5.2FA与左线性文法72
2.6FA的一些变形73
2.6.1双向有穷状态自动机74
2.6.2带输出的FA75
2.7小结76
习题77
第3章正则表达式82
3.1启示82
3.2正则表达式的形式定义83
3.3正则表达式与FA等价85
3.3.1正则表达式到FA的等价变换85
3.3.2正则语言可以用正则表达式表示93
3.4正则语言等价模型的总结98
3.5小结100
习题100
第4章正则语言的性质103
4.1正则语言的泵引理103
4.2正则语言的封闭性108
4.3MyhillNerode定理与DFA的极小化114
4.3.1MyhillNerode定理114
4.3.2DFA的极小化122
4.4关于正则语言的判定算法130
4.5小结131
习题132
目录形式语言与自动机理论引论第5章上下文无关语言134
5.1上下文无关文法134
5.1.1上下文无关文法的派生树135
5.1.2二义性140
5.1.3自顶向下的分析和自底向上的分析143
5.2上下文无关文法的化简145
5.2.1去无用符号146
5.2.2去ε产生式149
5.2.3去单一产生式组152
5.3乔姆斯基范式155
5.4格雷巴赫范式158
5.5自嵌套文法163
5.6小结164
习题164
第6章下推自动机168
6.1基本定义168
6.2PDA与CFG等价174
6.2.1PDA用空栈接受和用终止状态接受等价174
6.2.2PDA与CFG等价177
6.3小结186
习题186
第7章上下文无关语言的性质189
7.1上下文无关语言的泵引理189
7.2上下文无关语言的封闭性195
7.3上下文无关语言的判定算法200
7.3.1L空否的判定200
7.3.2L是否有穷的判定201
7.3.3x是否为L的句子的判定202
7.4小结204
习题204
第8章图灵机205
8.1基本概念206
8.1.1基本图灵机206
8.1.2图灵机作为非负整函数的计算模型213
8.1.3图灵机的构造215
8.2图灵机的变形221
8.2.1双向无穷带图灵机221
8.2.2多带图灵机224
8.2.3不确定的图灵机226
8.2.4多维图灵机227
8.2.5其他图灵机229
8.3通用图灵机231
8.4几个相关的概念233
8.4.1可计算性233
8.4.2P与NP相关问题233
8.5小结234
习题234
第9章上下文有关语言237
9.1图灵机与短语结构文法的等价性237
9.2线性有界自动机及其与上下文有关文法的等价性240
9.3小结241
习题241
附录缩写符号243
词汇索引245
参考文献251
第1章语言与文法1
1.1语言2
1.1.1什么是语言2
1.1.2形式语言与自动机理论的产生2
1.1.3基本概念3
1.2文法9
1.3文法的构造18
1.4文法的乔姆斯基体系26
1.5空语句36
1.6小结38
习题38
第2章有穷状态自动机44
2.1语言的识别44
2.2有穷状态自动机46
2.3不确定的有穷状态自动机57
2.3.1作为对DFA的修改57
2.3.2NFA的形式定义58
2.3.3NFA与DFA等价60
2.4带空移动的有穷状态自动机64
2.5FA是正则语言的识别器68
2.5.1FA与右线性文法68
2.5.2FA与左线性文法72
2.6FA的一些变形73
2.6.1双向有穷状态自动机74
2.6.2带输出的FA75
2.7小结76
习题77
第3章正则表达式82
3.1启示82
3.2正则表达式的形式定义83
3.3正则表达式与FA等价85
3.3.1正则表达式到FA的等价变换85
3.3.2正则语言可以用正则表达式表示93
3.4正则语言等价模型的总结98
3.5小结100
习题100
第4章正则语言的性质103
4.1正则语言的泵引理103
4.2正则语言的封闭性108
4.3MyhillNerode定理与DFA的极小化114
4.3.1MyhillNerode定理114
4.3.2DFA的极小化122
4.4关于正则语言的判定算法130
4.5小结131
习题132
目录形式语言与自动机理论引论第5章上下文无关语言134
5.1上下文无关文法134
5.1.1上下文无关文法的派生树135
5.1.2二义性140
5.1.3自顶向下的分析和自底向上的分析143
5.2上下文无关文法的化简145
5.2.1去无用符号146
5.2.2去ε产生式149
5.2.3去单一产生式组152
5.3乔姆斯基范式155
5.4格雷巴赫范式158
5.5自嵌套文法163
5.6小结164
习题164
第6章下推自动机168
6.1基本定义168
6.2PDA与CFG等价174
6.2.1PDA用空栈接受和用终止状态接受等价174
6.2.2PDA与CFG等价177
6.3小结186
习题186
第7章上下文无关语言的性质189
7.1上下文无关语言的泵引理189
7.2上下文无关语言的封闭性195
7.3上下文无关语言的判定算法200
7.3.1L空否的判定200
7.3.2L是否有穷的判定201
7.3.3x是否为L的句子的判定202
7.4小结204
习题204
第8章图灵机205
8.1基本概念206
8.1.1基本图灵机206
8.1.2图灵机作为非负整函数的计算模型213
8.1.3图灵机的构造215
8.2图灵机的变形221
8.2.1双向无穷带图灵机221
8.2.2多带图灵机224
8.2.3不确定的图灵机226
8.2.4多维图灵机227
8.2.5其他图灵机229
8.3通用图灵机231
8.4几个相关的概念233
8.4.1可计算性233
8.4.2P与NP相关问题233
8.5小结234
习题234
第9章上下文有关语言237
9.1图灵机与短语结构文法的等价性237
9.2线性有界自动机及其与上下文有关文法的等价性240
9.3小结241
习题241
附录缩写符号243
词汇索引245
参考文献251
