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

Авторы

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

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

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

Аннотация

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

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

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

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

Загрузки

Опубликован

07.02.2017

Выпуск

№ 1 (2017)

Раздел

Информатика

Лицензия

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

 

Материал публикуется под лицензией:

Creative Commons License

Creative Commons Attribution 4.0 International License.

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

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

Похожие статьи

11-20 из 240

Вы также можете начать расширеннвй поиск похожих статей для этой статьи.

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