《形式语言与自动机理论(第3版)》课后习题答案

形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其近30年来在大学讲授该门课程的经验和体会，选择和组织有关内容撰写而成。基于计算机问题求解的需要讨论正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性。叙述中特别注意引导读者分析与解决问题，以培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。为了便于学生对内容的掌握，附录A还给出了建议的教学设计。本书配套出版有《形式语言与自动机理论教学参考书（第3版）》，归纳各章知识点，解读主要内容，解析典型习题。本书适合作为计算机学科研究生和高年级本科生的教材，也可供相关专业的学生、教师和科研人员参考。

目录

• 第1章 绪论
• 1.1 集合的基础知识
• 1.1.1 集合及其表示
• 1.1.2 集合之间的关系
• 1.1.3 集合的运算
• 1.2 关系
• 1.2.1 二元关系
• 1.2.2 等价关系与等价类
• 1.2.3 关系的合成
• 1.2.4 递归定义与归纳证明
• 1.2.5 关系的闭包
• 1.3 图19
• 1.3.1 无向图
• 1.3.2 有向图
• 1.3.3 树
• 1.4 语言
• 1.4.1 什么是语言
• 1.4.2 形式语言与自动机理论的产生与作用
• 1.4.3 基本概念
• 1.5 小结
• 习题
• 第2章 文法
• 2.1 启示
• 2.2 形式定义
• 2.3 文法的构造
• 2.4 文法的乔姆斯基体系
• 2.5 空语句
• 2.6 小结
• 习题
• 第3章 有穷状态自动机
• 3.1 语言的识别
• 3.2 有穷状态自动机
• 3.3 不确定的有穷状态自动机
• 3.3.1 作为对DFA的修改
• 3.3.2 NFA的形式定义
• 3.3.3 NFA与DFA等价
• 3.4 带空移动的有穷状态自动机
• 3.5 FA是正则语言的识别器
• 3.5.1 FA与右线性文法
• 3.5.2 FA与左线性文法
• 3.6 FA的一些变形
• 3.6.1 双向有穷状态自动机
• 3.6.2 带输出的FA
• 3.7 小结
• 习题
• 第4章 正则表达式
• 4.1 启示
• 4.2 正则表达式的形式定义
• 4.3 正则表达式与FA等价
• 4.3.1 正则表达式到FA的等价变换
• 4.3.2 正则语言可以用正则表达式表示
• 4.4 正则语言等价模型的总结
• 4.5 小结
• 习题
• 第5章 正则语言的性质
• 5.1 正则语言的泵引理
• ……
• 第6章 上下文无关语言
• 第7章 下推自动机
• 第8章 上下文无关语言的性质
• 第9章 图灵机
• 第10章 上下文有关语言
• 附录A 教学设计
• 附录B 缩写符号
• 词汇索引
• 参考文献