An Algorithm for Minimizing a Completely Deterministic Finite Automaton Based on State Transition Inverse Mapping

Abstract—During the process of minimizing a deterministic finite automaton, there exist computing dependency and repetitive computing problems caused by the disorder of selecting a set to partition in the partition algorithm or by the disorder of computing state-pairs in the combination algorithm. To solve theses problems, a new algorithm for minimizing a completely deterministic finite automaton is presented. Firstly, based on the concept of a completely deterministic finite automaton, characteristics of state transition inverse mapping and the usage to reduce repetitive computing are analyzed. Secondly, the algorithm for minimizing a completely deterministic finite automaton, its rightness proof and analysis of time complexity are given. In the end, an experiment is carried out and the result shows that this algorithm is fairly efficient for minimizing a finite automaton. Index Terms—minimizing, completely deterministic, finite automaton, state transition, inverse mapping I