DFA化简方法示例-编译原理与实践

DFA化简指的是，寻找一个状态数最少的DFA M，使得L（M）=L（M）。每个正规集都可以由一个状态数最少的DFA所识别，如果不考虑状态名不同所带来的差异的话，则该DFA是唯一的。

化简是消去DFA中多余或无用状态、并合并等价状态的过程。所谓多余状态是指，从初始状态出发，读入任何输入串都无法到达的那个状态，或者说，从该状态没有通路能够到达终态。假定s和t是M的两个不同状态，二者等价是指：如果从状态s出发能读出某个字w而停于终态，则从t出发也能读出同样的字w而停于终态；反之，若从t出发能读出某个字w而停于终态，则从s出发也能读出同样的字w而停于终态。如果DFA的两个状态s和t不等价，则称s和t是可区别的。比如，终态与非终态是可区别的，因为终态能够读出空字ε，非终态则不能读出ε。

1.等价状态

在有限自动机中，状态s和t等价需满足以下条件：

（1）一致性条件：s和t同时为可接受状态或不可接受状态；

（2）蔓延性条件：对所有输入符号，s和t都能转换到等价的状态中。

2.基本思想

DFA化简

DFA化简的基本思想是：把DFA M的状态分成一些不相交的子集，使得任何不同子集中的状态都是可区别的，而同一子集中的状态都是等价的。然后，从每个子集中选出一个状态作为代表，同时消去其他等价状态。这种方法称为“分割法”，其具体过程是：

（1）将M的所有状态分成两个子集：终态集和非终态集；

（2）考察每个子集，若发现某子集中的状态不等价，则将其划分为两个集合；

（3）重复第（2）步，继续考察已得到的每个子集，直到没有任何一个子集需要继续划分为止。此时，DFA的状态被分割成若干个互不相交的子集；

（4）从每个子集中选出一个状态作为代表，即可得到最简DFA。

3.注意事项(www.xing528.com)

状态合并时需要注意以下两点：

（1）由于子集中的状态都是等价的，因此，要将原来进入（离开）该子集中每个状态的弧改为进入（离开）所选的代表状态；

（2）含有原来初态的子集仍为初态，含有原来各终态的子集仍为终态。

例3.10 化简图3-22（a）中的DFA。

（1）将DFA中的所有状态分为终态集和非终态集，得到：

Π0={{S,A,B},{C,D,E,F}}

（2）考察Π0，首先查看子集{S，A，B}的状态转换情况，有：δ（S，a）=A，δ（A，a）=C，δ（B，a）=A。显然，当读入a时，状态A和状态S、B分别进入不同的子集中，故可将{S，A，B}划分为{A}和{S，B}。类似地，状态C、D、E、F在读入a、b后均转移到同一子集中，因此，不可区分。于是，可以得到如下新的划分：

Π1={{A},{S,B},{C,D,E,F}}

（3）进一步考察Π1，首先查看子集{S，B}的状态转换情况，有：δ（S，b）=B，δ（B，b）=D。显然，当读入b时，状态S和B分别进入不同的子集中，故可将{S，B}划分为{S}和{B}。由于{A}和{C，D，E，F}不能再划分，也就是说，所有子集都不能再划分，因此，可以得到如下新的划分：

Π2={{A},{S},{B},{C,D,E,F}}

（4）从Π2的每个子集中选出一个状态作为代表，这里用{C}代表{C，D，E，F}，其余子集用自身做代表，最后得到仅含有4个状态的最小DFA，如图3-22（b）所示。

图3-22　DFA的最小化