Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.03.061

Upr. sist. maš., 2016, Issue 3 (263), pp. 61-70.

UDC 519.713

A.N. Chebotarev, Doctor (Eng.), V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 03187, Glushkov ave., 40, Ukraine, E-mail: ancheb.@gmail.com 

On Automata Minimization by Hopcroft’s Algorithm

Introduction. The algorithm for minimizing deterministic complete finite state automata proposed by J. Hopcroft is considered. Although the existence of this algorithm is widely known, its theoretical justification is not that obvious. The aim of this study is to give a clear and understandable presentation of the algorithm focusing on the firm theoretical basis, rigorous correctness proof and time complexity analysis.

Methods. The algorithm is based on the partition notion of the automaton states which defines the equivalence relation. It constructs a sequence of such partitions by a stepwise refinement of some initial partition. The last partition in this sequence corresponds to the maximal congruence on the automaton’s states, i.e., the equivalence stable with respect to the transition function of the automaton. To prove correctness of the algorithm it is necessary to show that the final constructed partition is a congruence, and that this congruence is maximal. In the first part of this proof, the introduced notion of binary splitting tree is used whose nodes are classes of the partitions constructing by the algorithm and a technique for extending the so called “closed” nodes of this tree. The second part is based on the proposition concerning the order on partitions. It is proved that every partition in the sequence generated by the algorithm is greater than or equal to the partition corresponding to the maximal congruence.

Results. It is show that Hopcroft’s algorithm can be implemented to worst-case time complexity O(kn log n) for an automaton with n states over a k-letter alphabet. This statement relies on the fact that the total number of actions refining the partitions over all steps of algorithm execution is of the order of O(kn log n). The data structures which allow obtaining this time complexity is presented. The last section describes the algorithm features for minimizing Moore and Mealy automata.

Download full text! (In Russian).

Keywords: Hopcroft’s algorithm, automaton minimization, partition, congruence, time complexity, splitting tree.

1. Huffman, D.A. “The synthesis of sequential switching circuits”. J. Franklin Inst., 1954, 257, 3, pp. 161–190; 4, pp. 275–303.
2. Moore, E.F., 1956. “Gedanken-experiments on sequential Machines. Automata studies”. Princeton Univ. Press, Princeton, N.J., pp. 129–153.
3. Hopcroft, J., 1971. “An n log n algorithm for minimizing states in a finite automaton”. Proc. Internat. Symp. on the Theory of Machines and Computations, Academic Press, New York, pp. 189–196.
   https://doi.org/10.1016/B978-0-12-417750-5.50022-1
4. Gries, D., 1973. “Describing an algorithm by Hopcroft”. Acta Inform., 2, pp. 97–109.
   https://doi.org/10.1007/BF00264025
5. Brauer, V., 1987. Vvedeniye v teoriyu konechnykh avtomatov. M.: Radio i svyaz’, 392 p. (In Russian).
6. Knuutila, T., 2001. “Re-describing an algorithm by Hopcroft”. Theoret. Comput. Sci., 250, pp. 333–363.
   https://doi.org/10.1016/S0304-3975(99)00150-4
7. Baclet, M., Pagetti, C., 2006. “Around Hopcroft’s algorithm”. Lecture Notes in Comp. Sci., 4094, Springer-Verlag, pp. 114–125.
   https://doi.org/10.1007/11812128_12
8. Berstel, J., Carton, O., 2005. “On the complexity of Hopcroft’s state minimization algorithm”. Lecture Notes in Comp. Sci., 3317, Springer-Verlag, pp. 35–44.
   https://doi.org/10.1007/978-3-540-30500-2_4

Received 11.03.2016