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

作者：Chen Chu^*; Ren Pinghong; Yu Jiguo; Yu Nong

来源：International Workshop on Information Security and Application (IWISA 2009), 2009-11-21 to 2009-11-22.

• minimizing
• completely deterministic
• finite automaton
• state transition
• inverse mapping

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.

• 出版日期2009
• 单位曲阜师范大学