版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.csdn.net/lishuangzhe7047/article/details/7688142
一：DFA的最小化。
DFA最小化，最简单的理解就是“劈枝斩叶留主干”，最小化的DFA比原状态等价且状态数少。
劈枝斩叶留住干，在化简时候就是对等价的状态进行合并。
那么怎么找等价状态呢？所有的终结符号都是等价的。这也是找之后等价符号的基础。详情看下面例子。
化简步骤：
1，画出状态矩阵图
2，找终结符（等价的）。
3，根据找到的等价的终结符，在继续找其他的等价符号。
解：由于q2，q3等价，q0，q1 1到达q2，（q0,q1)==(q1,q0) 所以 q0,q1等价。
二：NFA->DFA的转换。
给定的NFA为图
转换步骤：
1，写I ， I0 ，I1,2，写I={q0}开始符号 3，求I0 ，I14，所有包含终态的都是终态。
NFA的矩阵如图示
转换图：
总结：I 的第一个是开始符号q0,第二第三个就是上一个中的跟之前的I 不相同的。
直到I中将所有的I0，I1都包括了，就停止了。
三：带空移动的NFA到NFA
带空的NFA如图3-1示
转换为等价的NFA的步骤：
1，类似NFA转换到DFA的第一步，不同的是，左侧的第一个是开始符号q0以及q0和空之后的所有字符。 例：图3-1的第一个就是{q0,q1,q2}
2，第二步是找第二个字符，及所有的所能识别的空移动到达的字符。
3，之后的以此类推，直到所有的字符都出现。
转换图如3-2所示
等价的NFA为图3-3所示
总结：带空的NFA到NFA与NFA到DFA的不用是左侧的符号，NFA到DFA左侧符号不能很方便的看出来，得根据右侧，第一个就是一个开始符号，空NFA到NFA左侧是所有的符号及识别空所能到达的符号，第一个符号是开始符号或者是开始符号和识别空所到达的符号。
