A Class Of Non-deterministic Finite Automata Minimization And Time Complexity

The research of the automation theory mainly includes two aspects: one is minimization of automaton and the other is its time complexity.Equivalent relations are definited in the set of the automation's states and equivalent classes will be introducted. Then the equivalent states will be merged into one state, so the new generation of automation will be smaller. The language that the new generation of automation accepts is the same as the language that the original automaton accepts. That is to say, they are equivalent. This is the tree segregated method. Tree segregated method can be used to minimize deterministic finite automation (DFA).A kind of non- deterministic finite automation (NFA) is the focus of this paper. That is connecting NFA. Such NFA is determined by the two-DFA. Using equivalent relations of two-DFA's state can construct equivalent relation of connecting NFA's the state. Such NFA can also use tree segregated method to minimize. Conclusions can be got that the number of the minimizing connecting automation's states is not more than the number of the connecting minimizing automation's states.NFA is more complicated. A big NFA is often no equivalent states, but merging two or several states don't change its language. In this paper condition of merging states is given and the number of minimum automation's states is found.The time complexity of minimizing automation is very effective to test algorithm. In general, the algorithm which can be completed in polynomial time is effective. Using of tree segregated method, DFA and connecting NFA can be minimized in cubic time. Finally the algorithm of minimizing NFA is presented in this paper.