DFA化简算法的一种改进方法

A Improved Method of DFA Simplified Algorithm

在深入研究DFA化简基本原理的基础上,首先给出现有分析算法(分割法)的形式化算法描述,然后证明了该算法存在着漏洞,并给出相应的解决方法。最后,借鉴时序逻辑门电路中原始状态表化简的方法,对现有分割算法进行修改,提出一种新的适用于任何DFA的化简算法——K次划分法。

With the basis of deep research in basic principle of DFA simplification, this paper describes the formalization algorithm of current analyzing algorithm （segmentation algorithm）, proves that there are shortages in this algorithm and provides their solutions. By the end, profiting from the method which used in sequential logic gate circuit to simplify the original state table, the paper changes the current segmentation algorithm and provides a algorithm suitable to any DFA simplification K--thdivision method.