非确定型有穷自动机的极小化

Minimization of a Kind of Non-deterministic Finite Automata

利用自动机状态集上的等价关系对自动机的状态集进行极小化,从而得到与原自动机功能等价的极小化自动机.通过两台确定型有穷自动机(DFA)的连接,构造一台非确定型有穷自动机(NFA).利用这两台确定型有穷自动机状态集上的等价关系,可以构造这台非确定型有穷自动机状态集上的等价关系,从而对这台非确定型有穷自动机进行极小化.结果表明这台非确定型有穷自动机的极小化自动机的状态复杂度,不大于对那两台确定型有穷自动机的极小化自动机进行连接得到的非确定型有穷自动机的状态复杂度;并且自动机在等价关系基础上进行极小化时不改变识别语言.

The automaton state set can be minimized based on the equivalence relation, so that a minimized automaton can be obtained. The link operation is that the execution will shift to the second automaton unconditionally as soon as the first DFA has finished its execution. A non-deterministic finite automaton （NFA） can be constructed by linking two deterministic finite automata （DFAs）. At the same time, the NFA＇s equivalence relation can be constructed based on the two DFAs＇ equivalence relation, so that we can minimize this NFA. Moreover, several conclusions have been obtained in this paper. The first one is that the number of states of the minimal automaton of the NFA is not more than the counterpart of the NFA which is constructed by linking the two minimal automata of the two DFAs. The second one is that the language which is identified by automaton is unchangeable in the course of minimizing.