An Algorithm for Minimizing a Completely Deterministic Finite Automaton Based on 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.
minimizing completely deterministic finite automaton state transition inverse mapping
Chu Chen Pinghong Ren Jiguo Yu Nong Yu
College of Computer Science, Qufu Normal University, Rizhao, China College of Information and Engineering, Shandong University of Science and Technology, Qingdao, Chin
国际会议
2009 International Workshop on Information Security and Application(2009 信息安全与应用国际研讨会)
青岛
英文
417-420
2009-11-21（万方平台首次上网日期，不代表论文的发表时间）