【软考】编译原理之有限自动机
什么是有限自动机？
答：是一种识别装置的抽象概念，它能准确地识别正规集，他分为两类：确定的有限自动机和不确定的有限自动机
| DFA（确定有限自动机） | NFA（不确定有限自动机） | |
| S | 是一个有限集合，每个元素成为一个状态 | 是一个有限集合，每个元素成为一个状态 |
| ∑ | 是一个有穷字母表，其中每一个元素成为一个输入符号 | 是一个有穷字母表，其中每一个元素成为一个输入符号 |
| f | 单值映射函数 | 多值映射函数 |
| s0 | 是唯一的一个开始状态 | 开始状态不唯一 |
| Z | 非空的终止状态 | 非空的终止状态 |
| 一、DFA（确定有限自动机） |
特点：
1、任意状态的射出弧上的标志均不相同
2、任意状态至多有n条射出弧
3、若DFA识别空串，这初态也是终止状态
| 二、NFA（不确定有限自动机） |
特点：
1、同一状态的射出弧上的标志可以相同
2、每个状态可以有多于n条射出弧
3、允许初态也是终态
| 三、NFA到DFA的转换 |
利用子集法求解
- 若I是NFA M的装填的一个子集，定义ε-closure（I）
- 从ε-closure（I）这个集合里的任意一个状态出发，经过任意一条空弧能够到达的状态，依然属于开始的空闲包
例子：一个NFA如下
将其转化为DFA，并最小化。
由于B和C相同，一次删除C，则得到如下的DFA自动机