One More Method for Minimization of Finite Automata
Keywords:
finite automaton, state diagram, indistinguishable states, Hopkroft’s algorithm
Abstract
An algorithm for minimizing the number of states of the well-formed deterministic finite automaton is described. It is based on the use of equivalence classes on the relation of the indistinguishability of string sets accepted by the automaton. A comparison is made with the well-known algorithm of J.E. Hopcroft, which constructs the classes of equivalent states on the property of the distinguishability of input strings accepted in the corresponding states.
References
[1] A. van Wijngaarden, ed., Peresmotrennoe soobshchenie ob Algole 68 [Revised Report on the Algorithmic Language], Moscow, USSR: Mir, 1979 (in Russian).
[2] G. S. Tseitin, ed., Algol 68. Metody realizatsii [Algol 68. Methods of implementation], Leningrad, USSR: Izd-vo Leningr. un-ta, 1976 (in Rusian).
[3] B. K. Martynenko, Sintaksicheski upravlyaemaya obrabotka dannykh [Syntactically managed data processing], Saint-Petersburg, Russia: Izd-vo SPb un-ta, 2004 (in Russian).
[4] B. K. Martynenko, “Chelnochnye translyatsii v SYNTAX-tekhnologii [Shuttle translations in the SYNTAX-technology],” Computer tools in education journal, no. 5, pp. 3–15, 2014 (in Russian).
[5] J. E. Hopcroft and J. D. Ullman, Formal languages and their relation to automata. Reading, MA: AddisonWesley Pub. Co., Inc., 1969.
[6] G. Rozenberg and A. Salomaa, Handbook of Formal Languages, Vol. 1: Word, Language, Grammar., Berlin, Heidelberg: Springer-Verlag, 1997.
[7] A. V. Aho and J. D. Ullman, Teoriya sintaksicheskogo analiza, perevoda i kompilyatsii [The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing], Moscow, USSR: Mir, 1978 (in Russian).
[8] J. E. Hopcroft, “An n log n algorithm for minimizing ststes in a finite automaton,” Technical Report CS-71-190, Stanford University, January 1971.
[2] G. S. Tseitin, ed., Algol 68. Metody realizatsii [Algol 68. Methods of implementation], Leningrad, USSR: Izd-vo Leningr. un-ta, 1976 (in Rusian).
[3] B. K. Martynenko, Sintaksicheski upravlyaemaya obrabotka dannykh [Syntactically managed data processing], Saint-Petersburg, Russia: Izd-vo SPb un-ta, 2004 (in Russian).
[4] B. K. Martynenko, “Chelnochnye translyatsii v SYNTAX-tekhnologii [Shuttle translations in the SYNTAX-technology],” Computer tools in education journal, no. 5, pp. 3–15, 2014 (in Russian).
[5] J. E. Hopcroft and J. D. Ullman, Formal languages and their relation to automata. Reading, MA: AddisonWesley Pub. Co., Inc., 1969.
[6] G. Rozenberg and A. Salomaa, Handbook of Formal Languages, Vol. 1: Word, Language, Grammar., Berlin, Heidelberg: Springer-Verlag, 1997.
[7] A. V. Aho and J. D. Ullman, Teoriya sintaksicheskogo analiza, perevoda i kompilyatsii [The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing], Moscow, USSR: Mir, 1978 (in Russian).
[8] J. E. Hopcroft, “An n log n algorithm for minimizing ststes in a finite automaton,” Technical Report CS-71-190, Stanford University, January 1971.
Published
2017-02-07
How to Cite
Мартыненко, Б. К. (2017). One More Method for Minimization of Finite Automata. Computer Tools in Education, (1), 5-14. Retrieved from http://cte.eltech.ru/ojs/index.php/kio/article/view/1432
Issue
Section
Computer science
This work is licensed under a Creative Commons Attribution 4.0 International License.
