JZTXT

dfa最小化

发布时间 2023-03-30 14:50:42作者: TimQiu

你好，这是Bing。我会尽力用浅显易懂的语言结合例子解释dfa的最小化。?

dfa的最小化是指把一个dfa（确定有穷自动机）转换成一个状态数最少的等价dfa。等价dfa是指能够接受相同的正规式的dfa。状态数最少的dfa是指没有多余的状态和等价的状态。多余的状态是指从这个状态不能到达终态，或者从开始状态不能到达这个状态。等价的状态是指对于任何输入符号，两个状态都能转移到相同或者等价的状态，并且两个状态都是终态或者非终态。

dfa的最小化的一般步骤是：

  1. 把dfa的所有状态分成两个子集，一个由终态组成，一个由非终态组成。
  2. 对每个子集，检查其中的状态是否可以根据输入符号转移到不同的子集，如果可以，就把这些状态分开，形成新的子集。
  3. 重复第二步，直到没有新的子集产生。
  4. 用每个子集中的一个状态代表该子集，构造新的dfa，保留原来dfa的开始状态和终态。

举一个例子，假设有一个dfa如下图：

image

按照上面的步骤，我们可以得到如下的过程：

  1. 把所有状态分成两个子集：{C,D,E,F}和{S,A,B}。
  2. 检查{C,D,E,F}是否可以分割，发现它们对于任何输入符号都转移到自己这个子集，所以不可分割。检查{S,A,B}是否可以分割，发现A对于输入a转移到{C,D,E,F}，而S和B对于输入a转移到{S,A,B}，所以A和SB可以分割。得到三个子集：{C,D,E,F}，{A}，{S,B}。
  3. 检查{C,D,E,F}是否可以分割，发现仍然不可分割。检查{A}是否可以分割，发现只有一个状态，不可分割。检查{S,B}是否可以分割，发现B对于输入b转移到{C,D,E,F}，而S对于输入b转移到{S,B}，所以B和S可以分割。得到四个子集：{C,D,E,F}，{A}，{B}，{S}。
  4. 没有新的子集产生，停止分割。用每个子集中的一个状态代表该子集（比如用D代表{C,D,E,F}），构造新的dfa如下图：

image

这就是最小化后的dfa。

源: 与必应的对话， 2023/3/30(1) 正规式->最小化DFA说明 - 知乎. https://zhuanlan.zhihu.com/p/37900383 访问时间 2023/3/30.
(2) 编译原理学习笔记（十五）~最小化DFA_dfa最小化_海轰 .... https://blog.csdn.net/weixin_44225182/article/details/106576746 访问时间 2023/3/30.
(3) 编译原理笔记6：从正规式到词法分析器（3）：DFA最小 .... https://developer.aliyun.com/article/762160 访问时间 2023/3/30.
(4) DFA的最小化_dfa最小化_Next***的博客-CSDN博客. https://blog.csdn.net/m0_51366201/article/details/128308870 访问时间 2023/3/30.
(5) 【20200325】编译原理课程课业打卡十之DFA的最小化_dfa .... https://blog.csdn.net/qq_43543789/article/details/105126166 访问时间 2023/3/30.