AN O(N-LOG-N) IMPLEMENTATION OF THE STANDARD METHOD FOR MINIMIZING N-STATE FINITE AUTOMATA

More than 20 years ago, Hopcroft (1971) has given an algorithm for min imizing an n-state finite automaton in O(kn log n) time where k is the size of the alphabet. This contrasts to the usual O(kn(2)) algorithms presented in text books. Since Hopcroft's algorithm changes the stand ard method, a nontrivial correctness proof for its method is needed. I n lectures given at university, mostly the standard method and its str aightforward O(kn(2)) implementation is presented. We show that a slig ht modification of the O(kn(2)) implementation combined with the use o f a simple data structure composed of chained lists and four arrays of pointers (essentially the same as Hopcroft's data structure) leads to an O(kn log n) implementation of the standard method. Thus, it is pos sible to present in lectures, with a little additional amount of time, an O(kn log n) time algorithm for minimizing n-state finite automata.