Smallest State After The Computation Of Finite Automata

In this paper, based on automata theory, the Fill Table Algorithm which can minimize deterministic finite automata (DFA) that represents a regular language and the minimization problem on the automaton which is the result of the union or intersection operation on two DFAs have been studied.Firstly, we have introduced one minimization algorithm, Fill Table Algorithm [34], which can minimize a given DFA, have shown the correctness and have analyzed the computation complexity of Fill Table Algorithm.Secondly, through analyzing the previous algorithm, two problems have been found. One is the algorithm cannot deal with the non-complete DFA, and the other is, in pre-process of the algorithm, the number of the initial marked state pairs is able to be increased. Based on this, we analyzed the properties of coaccessible states and the essence of the initial marked state pairs in detail. Further more we modified and circumstantiated the original algorithm, and showed the correctness and analyzed the computation complexity of the modified algorithm.Thirdly, we have verified the correctness of the above two algorithms by some instances. We also have found four factors influencing the result of the two different algorithms, summarized these running cases, and presented five improved places from the original one.Finally, we have given the two constructions for the union or intersection operation on the two DFAs. The automata from the constructions can be minimized by the new algorithm. We have shown the correctness of the two constructions in the end.