编译原理 第三章下：有穷自动机DFA和NFA的详细讲解【搭配题目训练】
编译原理 第三章下：有穷自动机DFA和NFA的详细讲解【搭配题目训练】
3.4 有穷自动机
3.4.1 确定的有穷自动机DFA
有穷自动机分为确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。先以DFA为例进行介绍。
3.4.1.1 有穷自动机的形式定义
一个确定的有穷自动机M是一个五元组，M=(有穷集合，字母表，初始状态，结束状态集合，状态转换函数)。
来看一个具体实例：
- {0,1,2,3}是有穷集合
- {a,b}是字母表，可以理解为标记
- 0是开始状态
- {3}是结束状态
- 最后的是状态转换函数
3.4.1.2 状态转换矩阵
状态转换矩阵有助于我们更直观地得到转换信息。状态转换矩阵的绘制方法如下：
- 纵坐标是有穷集合，打*号是因为是结束状态
- 横坐标是字母表，也就是标记
- 它们之间填充的就是某个状态，作用某个标记得到的状态
3.4.1.3 DFA接受的语言
从开始状态出发，看看最后是否在终结状态结束。
3.4.2 不确定的有穷自动机NFA
3.4.2.1 形式定义
与DFA相比，NFA有两个不同点：字母表中加入了空串，状态转换函数变成了映射。
图解：
- 通过状态转换函数构造状态图的过程，大差不差，多了空这种标记
- 状态矩阵中，走不到的地方，用空填充，由于变成了不确定的自动机，自然从状态1，经过标记a，就不一定只有一个状态了
- 注意新增的ε是字母表中的一员
3.4.2.2 NFA接受的语言
重点是扩充的状态转换函数和对于ε-闭包的理解。简言之就是，NFA的ε标记，会一直找下去，从a，经过标记ε，到b，发现b，经过标记ε，还可以到c，那么状态转换函数（a，ε），里面就不止有b还有c。
3.4.3 NFA到DFA的转换
为了更好地让计算机实现，那肯定是确定的事物要好于不确定的事物，本小节的目标是实现将不确定的有穷自动机转换为确定的无穷自动机。本小节为重点大题，单独编写博客编译原理必考大题：子集法将NFA转换为DFA【详细讲解，真题实战】
3.4.4 正则表达式与有穷自动机的等价性
正则表达式构造有穷自动机的原理如下：
- 原理：略
- 例题：略
有穷自动机推出正则表达式：
反向思考的问题，即正则表达式构造有穷自动机的逆向问题。
3.5 有穷自动机的化简
对于任何给定的DFA，都有一个含有最少状态的等价DFA，而且这个最少状态DFA是唯一的。一个有穷自动机可以通过消除多余的状态和合并等价状态转换成一个最小的与之等价的有穷自动机。
3.5.1 等价状态与不等价状态与多余状态
- 等价状态与不等价状态：对于DFA中的两个状态S1,S2,如果将它们看作是初始状态，则所接受的符号串相同，则定义S1,S2是等价的。
- 多余状态：多余状态有不可到达的状态和不可终止的状态。
3.5.2 化简方法
- 划分终结符号和非终结符号为两个不等价状态集组
- 对每组中的某个状态分离出与之不等价的状态组，直到所有状态组内部都等价
核心要点：当我们得到一组新的状态集合放入表格右边的时候，要从右往左检查，检查新状态集合的每个元素，是否都还在这个状态集组里或其他状态集合组里，如果不在，则在右边找到那个不在的元素，看它对应的左边是哪个元素，把那个元素单独拿出来剔除，当然了，不一定非要拿一个，根据规律，几个为一组拿出来也可。整体的去看，一个组内元素不能既在某个组，又在另一个组。
3.5.3 真题实战
略
3.6 词法分析程序自动生成器LEX
一定要知道词法分析程序自动生成器叫什么？
答：LEX
明确两种词法分析器的流程：
- 直接编程的词法分析器(人工构造词法分析器)
- 正则文法➡️正则表达式➡️NFA➡️DFA➡️状态图➡️流程图
- 表驱动的词法分析程序
- 正则文法➡️正则表达式➡️NFA➡️DFA➡️矩阵表示
总结：从正则文法到正则表达式，再到NFA，DFA都是一样的，从DFA开始变化
功能：依据语言的正则表达式，自动生成该语言的词法分析程序。