Ещё один метод минимизации конечных автоматов

Авторы

  • Борис Константинович Мартыненко СПбГУ, Санкт-Петербург, Россия

Ключевые слова:

конечный автомат, диаграмма состояний, неразличимые состояния, алгоритм Дж.Хопкрофта

Аннотация

Описывается алгоритм минимизации приведённых детерминированных конечных автоматов, основанный на использовании классов эквивалентности по признаку неразличимости множеств цепочек, принимаемых в соответствующих состояниях. Проводится сравнение с алгоритмом Дж. Хопкрофта, в котором классы эквивалентных состояний строятся, исходя из отношения различимости состояний по допустимым входным цепочкам.

Биография автора

  • Борис Константинович Мартыненко, СПбГУ, Санкт-Петербург, Россия

    Доктор физико-математических наук, профессор кафедры информатики математико-механического факультета СПбГУ; 198504, Россия, Санкт-Петербург, Старый Петергоф, Университетский пр., д. 28, математико-механический факультет, кафедра информатики.

Загрузки

Опубликован

07.02.2017

Выпуск

№ 1 (2017)

Раздел

Информатика

Лицензия

Copyright (c) 2017 Борис Константинович Мартыненко

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

Авторский договор

Как цитировать

[1]
Б. К. Мартыненко, «Ещё один метод минимизации конечных автоматов», Компьютерные инструменты в образовании, вып. 1, сс. 5–14, фев. 2017, просмотрено: сен. 08, 2026. доступно на: http://cte.eltech.ru/ojs/index.php/kio/article/view/1432

Наиболее читаемые статьи этого автора (авторов)