211
правок
Изменения
м
Нет описания правки
</ol>
}}
==Постановка задачи==
Пусть дан автомат <tex>A</tex>. Требуется построить автомат <tex>A_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>A</tex>.
==Алгоритм==
Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.
===Корректность алгоритма===
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. <br />
Пусть существует автомат <tex>A'</tex>, эквивалентный <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>.
