基于前序关系的非确定型有穷自动机极小化算法

A non-deterministic finite automata minimization method based on the preorder relation

为了减少非确定型有穷自动机(non-deterministic finite automata,NFA)的状态数,引入前序关系,并以图论为工具,将NFA的转移图看作一个带有标记的有向图,给出了NFA极小化的一个新方法。与现行的利用归并等价状态来极小化NFA的算法相比,该方法可以使得NFA在接受语言的能力等价的前提下,状态数得到进一步的减少。

In order to reduce the number of non-deterministic finite automata（NFA） states,the preorder relation was introduced.The transition diagram for the NFA was regarded as a directed graph with signs based on graph theory and then a new method of NFA minimization was proposed.Compared with the current NFA minimization algorithm based on merging the equivalent states,this method could further reduce the number of NFA states while accepting the same languages.