A class of non - deterministic finite automata minimization and complexity
|Keywords||Connection type finite automata Equivalence relation Indistinguishable state Time complexity Tree graph partitioning method Critical condition|
In this paper, the theory of automata mainly two aspects: the complexity of automata minimization and minimization of the time . Defined on the equivalence relations in the set of states of the automaton , the introduction of the equivalence class , would be equivalent to state merged into one state , generating a smaller number of new state automaton . Identify the language of the new generation of automatic machine with the automatic machine unchanged , meaning that they are equivalent . This is the idea of the tree graph partitioning method . Tree graph partitioning method can be deterministic finite automata minimization . The focus of this paper is to construct a class of non - deterministic finite automata, the connection type finite automata . Kind of finite automata by two deterministic finite automata are connected . The use of two deterministic finite automata equivalence relation on the set of states can be constructed connection type equivalence relation on the set of states of finite automata . Such non- deterministic finite automata can also use the tree graph partitioning method to minimization . Can also get the status of the connection and then minimization of automata is not greater than the number of states of the automata minimization and then connect . Non- deterministic finite automata the situation is more complicated . Often relatively large finite automata equivalent states , but a two or several states to merge does not change their language . In this paper, a non-deterministic finite automata state merger conditions . Find a non-deterministic finite automata minimization state critical condition . The automata minimization time complexity of the effective authentication minimization algorithm is valid . , Completed in polynomial time that the algorithm is effective . Deterministic finite automata finite automaton the tree graph partitioning method minimization and connection type , they all can be completed in the state cubic time . The end of this article gives a non- deterministic finite automata minimization algorithm .