内容简介
形式语言与自动机理论是计算机科学与技术专业的一门重要课程。本书是作者结合其多年来在大学讲授该门课程的经验和体会，选择和组织有关内容撰写而成。不仅含有有关正则语言、上下文无关语言的文法、识别模型及其性质、图灵机的基本知识，更涉及到本学科方法论中所包含的3个学科形态。其内容特点是抽象和形式化，既有严格的理论证明，又具有很强的构造性，从而培养学生的形式化描述和抽象思维能力，使学生了解和初步掌握“问题、形式化、自动化（计算机化）”的解题思路。
目录
第1章 基础知识…………………………………………………………………………… 1
1. 1 集合, 关系和函数……………………………………………………………………… 1
1. 2 证明方法………………………………………………………………………………… 4
1. 3 图………………………………………………………………………………………… 6
1. 4 语言:基本概念………………………………………………………………………… 7
问题与解答…………………………………………………………………………………… 10
习题…………………………………………………………………………………………… 12
第2章 文法…………………………………………………………………………………… 14
2. 1 文法的定义和分类…………………………………………………………………… 15
2. 2 二义性………………………………………………………………………………… 24
2. 3 CFG 的化简…………………………………………………………………………… 28
2. 4 范式…………………………………………………………………………………… 31
问题和解答…………………………………………………………………………………… 36
习题…………………………………………………………………………………………… 39
第3章 有限状态自动机……………………………………………………………………… 44
3. 1 确定有限状态自动机(DFSA)………………………………………………………… 45
3. 2 不确定有限状态自动机(NFSA) …………………………………………………… 47
3. 3 正则表达式…………………………………………………………………………… 51
问题与解答…………………………………………………………………………………… 56
习题…………………………………………………………………………………………… 61
第4章 有限自动机:特征、性质和可判定性………………………………………………… 65
4. 1 有限自动机和正则文法……………………………………………………………… 65
4. 2 正则集的泵浦引理…………………………………………………………………… 66
4. 3 封闭性………………………………………………………………………………… 68
4. 4 可判定性定理………………………………………………………………………… 70
问题和解答…………………………………………………………………………………… 71
习题…………………………………………………………………………………………… 71
第5章 带输出的有限状态自动机及其化……………………………………………… 73
5. 1 Myhill鄄Nerode 定理…………………………………………………………………… 73
5. 2 带输出的有限自动机………………………………………………………………… 77
问题与解答…………………………………………………………………………………… 79
习题…………………………………………………………………………………………… 81
第6章 有限自动机的变形…………………………………………………………………… 83
6. 1 双向有限自动机……………………………………………………………………… 83
6. 2 多头有限状态自动机………………………………………………………………… 88
6. 3 概率有限自动机……………………………………………………………………… 89
6. 4 加权有限自动机和数字图像……………………………
