编译原理之确定有限自动机的最小化

最小化确定有限自动机

最小化下图的有限自动机DFA。

概念补充（不懂没关系，直接示范）

• DFA化简定义：找一个状态数比原来得确定有限自动机状态数少得确定有限自动机，但是表示得语言和原来的确定有限自动机相同
• 状态等价：
  • 状态s和t等价，意味着从s和t出发，读出识别同一个字符α，都到达了终态，那么这两个状态s和t是等价的
• 状态可区分：
  • 状态s和t可区分，存在一个字符α，分别让s和t读取之后，分别处于终态和非终态

实时演算

• 方法：
  • 将S划分成终态和非终态两个子集，形成基本划分
  • 然后分别对各个子集进行字符运算，观察彼此的结果是否在同一个子集中
    • 如果经过所有的字符运算之后，在同一个子集，那么就是自己所有的状态都是等价的
    • 如果不是经过某个字符运算之后，不在同一个子集，那么在进行划分，结果为同一个子集的划分到一起

演示

• 将所有的状态根据终态和非终态进行基本的划分，分别进行输入a的运算，发现如下的变化

• 对新生成的状态集子集在进行b运算，观察运算的结果是否相同

• 然后在进行对终态进行a和b的运算

• 同一状态子集的进行合并，选出集合中的其中一个状态，作为代表。将通向同一子集的其他状态的线，全部指向同一子集的代表的状态