Equivalence Of The Minimization Of Automata

The research of the automaton theory begins from 40s' in the twenty century. Through the development of several decades, the automaton theory has become an important branch in the computer science, and it has been applied in many realms in the computer science. For example, the construction of the compiling program, text manipulation, structure data translating and the switch circuit design and so on. It is the important foundation theory of the research of computer software and hardware.The research of the automaton theory mainly includes two aspects, one is the regular expression, and the other is the finite automaton. The description capability of the regular expression and the finite automaton are equivalent. Any expression can be translated into a finite automaton which can identify the same language.We usually use the pump lemma to judge that a given language is not regular language. However, the process is a little fussier. Using the principle of equivalence, we bring forward a new method to judge whether a given language is regular language or not. This method simplifies the step of the judge of the regular language very much.The reducing of the finite automaton is a very important issue. Taking equivalence as precondition, the fewer of the automaton's states means that we can save more resources of the software and hardware. The minimizing of the states is to divide the set of the state into some subsets which are not interactive and make sure that the states in the different subsets are distinguishable and the states in the same subsets are undistinguishable. At the last, we can use one element in the subset to stand for the subset.Also using the principle of equivalence, we introduce the concept of the equivalence class and then give the minimizing algorithm of the deterministic finite automaton, the equivalence merger algorithm. Using this algorithm, we can merge the equivalent states in the set of the automaton's states and then get the minimized automaton which is equivalent to the original automaton.For the reducing of the non-deterministic finite automaton, we also use the concept of the equivalence class. On the basis of the minimizing algorithm of the deterministic finite automaton, we give the minimizing algorithm of the non-deterministic finite automaton.