418
правок
Изменения
м
Нет описания правки
==Алгоритм==
=== Описание ===
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата.
Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.
===Корректность алгоритма===
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма.
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.
==Псевдокод==
===Время работы алгоритма=Асимптотики==
Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.
==Примерработы==
Минимизируем данный автомат.
[[Файл:dkaMin.png]]
==Источникиинформации==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4* [http://en.wikipedia.org/wiki/DFA_minimization Wikipedia:DFA_minimization]* [http://www.eecs.berkeley.edu/~sseshia/172/lectures/Lecture6.pdf Minimization of DFAs]* [http://www.comp.nus.edu.sg/~cs4212/dfa-min.pdf DFA Minimization]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
