Portal de Periódicos da CAPES

Describing an algorithm by Hopcroft

1973; Springer Science+Business Media; Volume: 2; Issue: 2 Linguagem: Inglês

10.1007/bf00264025

1432-0525

David Gries,

Machine Learning and Algorithms

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 · m · n · log n where K is a constant, m the number of input, symbols, and n the number of states. Hopcroft [3] 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.