《形式语言与自动机理论（第二版）》课后习题答案

形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其20余年来在大学讲授该门课程的经验和体会，选择和组织有关内容撰写而成。不仅含有有关正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识，更涉及到本学科方法论中所包含的3个学科形态。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性，从而培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。为了便于学生对内容的掌握，附录A还给出了建议的教学设计。

本书配套出版有《形式语言与自动机理论教学参考书（第2版）》，归纳各章知识点，解读主要内容，解析典型习题。

本书适合作为计算机科学与技术专业的高年级本科生、研究生的教材，也可供相关专业的学生、教师和科研人员参考。

目录

• 第1章绪论1
• 1.1集合的基础知识2
• 1.1.1集合及其表示2
• 1.1.2集合之间的关系5
• 1.1.3集合的运算6
• 1.2关系12
• 1.2.1二元关系12
• 1.2.2等价关系与等价类13
• 1.2.3关系的合成14
• 1.2.4递归定义与归纳证明15
• 1.2.5关系的闭包18
• 1.3图19
• 1.3.1无向图19
• 1.3.2有向图21
• 1.3.3树23
• 1.4语言24
• 1.4.1什么是语言24
• 1.4.2形式语言与自动机理论的产生与作用25
• 1.4.3基本概念28
• 1.5小结35
• 习题35
• 第2章文法42
• 2.1启示43
• 2.2形式定义48
• 2.3文法的构造58
• 2.4文法的乔姆斯基体系68
• 2.5空语句79
• 2.6小结82
• 习题82
• 第3章有穷状态自动机86
• 3.1语言的识别86
• 3.2有穷状态自动机89
• 3.3不确定的有穷状态自动机102
• 3.3.1作为对DFA的修改102
• 3.3.2NFA的形式定义104
• 3.3.3NFA与DFA等价106
• 3.4带空移动的有穷状态自动机110
• 3.5FA是正则语言的识别器115
• 3.5.1FA与右线性文法115
• 3.5.2FA与左线性文法120
• 3.6FA的一些变形122
• 3.6.1双向有穷状态自动机122
• 3.6.2带输出的FA123
• 3.7小结125
• 习题126
• 第4章正则表达式131
• 4.1启示131
• 4.2正则表达式的形式定义133
• 4.3正则表达式与FA等价135
• 4.3.1正则表达式到FA的等价变换135
• 4.3.2正则语言可以用正则表达式表示144
• 4.4正则语言等价模型的总结150
• 4.5小结152
• 习题153
• 第5章正则语言的性质156
• 5.1正则语言的泵引理156
• 5.2正则语言的封闭性162
• 5.3MyhillNerode 定理与DFA的极小化170
• 5.3.1MyhillNerode 定理170
• 5.3.2DFA的极小化180
• 5.4关于正则语言的判定算法189
• 5.5小结190
• 习题191
• 第6章上下文无关语言194
• 6.1上下文无关文法195
• 6.1.1上下文无关文法的派生树195
• 6.1.2二义性202
• 6.1.3自顶向下的分析和自底向上的分析205
• 6.2上下文无关文法的化简207
• 6.2.1去无用符号208
• 6.2.2去ε产生式212
• 6.2.3去单一产生式组216
• 6.3乔姆斯基范式219
• 6.4格雷巴赫范式223
• 6.5自嵌套文法229
• 6.6小结230
• 习题230
• 第7章下推自动机235
• 7.1基本定义235
• 7.2PDA与CFG等价242
• 7.2.1PDA用空栈接受和用终止状态接受等价243
• 7.2.2PDA与CFG等价246
• 7.3小结257
• 习题257
• 第8章上下文无关语言的性质260
• 8.1上下文无关语言的泵引理260
• 8.2上下文无关语言的封闭性267
• 8.3上下文无关语言的判定算法273
• 8.3.1L空否的判定273
• 8.3.2L是否有穷的判定274
• 8.3.3x是否为L的句子的判定276
• 8.4小结278
• 习题278
• 第9章图灵机280
• 9.1基本概念281
• 9.1.1基本图灵机282
• 9.1.2图灵机作为非负整函数的计算模型289
• 9.1.3图灵机的构造293
• 9.2图灵机的变形300
• 9.2.1双向无穷带图灵机300
• 9.2.2多带图灵机304
• 9.2.3不确定的图灵机306
• 9.2.4多维图灵机308
• 9.2.5其他图灵机310
• 9.3通用图灵机313
• 9.4几个相关的概念315
• 9.4.1可计算性315
• 9.4.2P与NP相关问题316
• 9.5小结316
• 习题317
• 第10章上下文有关语言320
• 10.1图灵机与短语结构文法的等价性320
• 10.2线性有界自动机及其与上下文有关文法的等价性323
• 10.3小结325
• 习题325
• 附录A教学设计327
• 附录B缩写符号338
• 词汇索引340
• 参考文献348