编译原理的词法分析实验：DFA化简
DFA化简
- 确定有穷自动机M的化简是指：寻找一个状态数比DFA M少的DFA M’，使得L(M)＝ L(M’)。
- 一个有穷自动机是化简了的，即是它没有多余状态，并且它的状态中没有两个是互相等价的。
- 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机。
多余状态
所谓有穷自动机的多余状态，是指这样的状态：从有穷自动机
的初态出发，任何输入串也不能到达的那个状态；或者从这个状态
没有通路到达终态
等价和可区别的
等价：如果有穷自动机DFA M的两个状态s和t能够识别同样的符号串，则称状态s和t等价。
可区别的：如果有穷自动机DFA M的两个状态s和t不等价，
则称这两个状态是可区别的。
例如终态与非终态是可区别的。
DFA的最小化过程：
最小状态DFA的含义:
- 没有多余状态(死状态)
- 没有两个状态是互相等价（不可区别）
分割法
确定有限自动机M的化简的过程也就是其状态最少化过程：
一个DFA M的状态最少化过程是指将 M的状态集分割成一些不相交的子集，使得任何不同的两子集中的状态都是可区别的，而同一子集中的任何两个状态都是等价的。最后，在每个子集中选出一个代表，同时消去其它等价状态。
例：化简下图的DFA
DFA的状态集$K＝\{0，1，2 ，3，4，5，6\}$
- 首先把$M$的状态$K$分为两组：
终态集$K1=\{3，4，5，6\}$
非终态集$K2=\{0，1，2\}$
显然$K1$与$K2$不等价。
- 试图$K1，K2$在中寻找一个子集和一个输入符号使得这个子集中的状态可区别的；若可区别，则再分割；继续，一直到不能再分割为止。
讨论终态集$K1={3，4，5，6}$ 是否可分割：
$\{3，4，5，6\}_a \subset K1$
$\{3，4，5，6\}_b \subset K1$
所以状态3，4，5，6均等价，因此$K1$不能再分割。讨论非终态集$K2={0，1，2}$ 是否可分割：
$\{0，1，2\}_a \subset \{1，3\}$
它既不属于$K2＝\{0，1，2\}$，也不属于$K1＝\{3，4，5，6\}\$
将其一分为二
$\{0，2\}_a＝\{1\}\$
$\{1\}_a＝\{3\}$
$K21＝\{1\}$
$K22＝\{0，2\}$
再讨论$K22=\{0，2\}$ 是否可分割：
$\{0，2\}_b ＝\{2 ，5\}$
而它未包括在$K1 ，K21与K22$中，故$\{0，2\}$应一分为二：
$K221＝\{0\}$
$K222＝\{2\}$
所以$K$分为四组$\{3，4，5，6\}，\{0\}，\{1\}，\{2\}$。每个组都不可再分。
- 最后，令状态3代表$\{3，4，5，6\}$。把原来到达4，5，6的弧都导入3，并删除4，5，6状态。即可得到化简后的DFA。
实验
【问题描述】DFA化简问题的一种描述是：
编写一个程序，输入一个确定的有穷自动机（DFA），输出与DFA等价的最简的确定有穷自动机（DFA）。
【基本要求】设置DFA初始状态X，终态Y，过程态用数字表示：0 1 2 3………
【测试用例】
测试数据：1
2
3
4
5X X-a->0 X-b->1
Y Y-a->0 Y-b->1
0 0-a->0 0-b->2
1 1-a->0 1-b->1
2 2-a->0 2-b->Y
输出结果应为：1
2
3
4X X-a->0 X-b->X
Y Y-a->0 Y-b->X
0 0-a->0 0-b->2
2 2-a->0 2-b->Y
第一步，读取DFA
第二步，分组
