More than 20 years ago, Hopcroft (1971) has given an algorithm
for minimizing an n-state finite automaton in
k is the size of the alphabet. This contrasts to the usual O(kn2)
algorithms presented in text books. Since Hopcroft's algorithm changes
the standard method, a nontrivial correctness proof for its method is needed.
In lectures given at university, mostly the standard method and its
straight forward O(kn2) implementation is presented. We show that
a slight modification of the O(kn2) implementation combined with the
use of a simple data structure composed of chained lists and four arrays of
pointers (essentially the same as Hopcroft's data structure)
leads to an
implementation of the standard method. Thus,
it is possible to present in lectures, within a few additional amount of time,
time algorithm for minimizing n-state finite automata.