Ещё один метод минимизации конечных автоматов
Ключевые слова:
конечный автомат, диаграмма состояний, неразличимые состояния, алгоритм Дж.Хопкрофта
Аннотация
Описывается алгоритм минимизации приведённых детерминированных конечных автоматов, основанный на использовании классов эквивалентности по признаку неразличимости множеств цепочек, принимаемых в соответствующих состояниях. Проводится сравнение с алгоритмом Дж. Хопкрофта, в котором классы эквивалентных состояний строятся, исходя из отношения различимости состояний по допустимым входным цепочкам.
Литература
[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.
Опубликован
2017-02-07
Как цитировать
Мартыненко, Б. К. (2017). Ещё один метод минимизации конечных автоматов. Компьютерные инструменты в образовании, (1), 5-14. извлечено от http://cte.eltech.ru/ojs/index.php/kio/article/view/1432
Выпуск
Раздел
Информатика
Материал публикуется под лицензией:
