Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009) Qingdao, China, November 2122, 2009 Editors: Feng Gao and Xijun Zhu AP Catalog Number: APPROCCS09CN004 ISBN: 9789525726060 Page(s): 417420 

An Algorithm for Minimizing a Completely Deterministic Finite Automaton Based on State Transition Inverse Mapping Chu Chen, Pinghong Ren, Jiguo Yu, and Nong Yu 
Full text: PDF 
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 statepairs 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 

Copyright @ 2009 ACADEMY PUBLISHER — All rights reserved 