Describing an Algorithm by Hopcroft
We give an algorithm, its correctness proof, and its proof of execution time bound, for finding the sets of equivalent states in a deterministic finite state automaton. The time bound is $K\cdotm\cdot\n\cdot\\log n$ where $K$ is a constant, $m$ the number of input symbols, and $n$ the number of states. Hopcroft  has already published such an algorithm. The main reason for this paper is to illustrate the use of communicating an algorithm to others using a structured, top-down approach. We have also been able to improve on Hopcroft's algorithm by reducing the size of the algorithm and correspondingly complicating the proof of the running time bound.
computer science; technical report
Previously Published As