Algorithm for minimizing determination finite automation based on information system
Bo Wang · Journal of Computer Applications · 2012
At present,Determination Finite Automation(DFA) minimization more focuses on theoretical research,and there are not many algorithms easy to achieve.Therefore,the method of minimization of determination finite automation was researched.First,DFA was converted into information system;and then the information system was simplified,which was based on the partition of equivalence classes;at last the simplified information system was converted into minimized DFA.Concerning the above process,an algorithm of minimizing DFA based on strategy of divide and conquer was proposed.In the average case,the time complexity and space complexity of the algorithm are O(n log n) and O(n) respectively.Finally,an example was used to explain the feasibility of the proposed algorithm.