Изменения
Нет описания правки
#Для всех пар <tex> \langle t, k \rangle </tex>, таких, что <tex> \mathcal {9} c \in \Sigma, \langle t, c \rangle \vdash \langle u, \varepsilon \rangle, \langle k, c \rangle \vdash \langle v, \varepsilon \rangle </tex> и пара <tex> \langle t, k \rangle</tex> не отмечена в таблице, то отметим ее в таблице и добавим в <tex>Q</tex>.
За один проход по таблице согласно теореме разбиваем не помеченные состояния на классы эквивалентности.
==Корректность алгоритма==
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. <br>
Пусть существует автомат <tex>A'</tex> эквивалентный <tex>A</tex>, но с числом состояний меньшим чем в <tex>A_{min}</tex>.
Стартовые состояния <tex>s \in A_{min}</tex> и <tex>s' \in A'</tex> эквивалентны, так как <tex>A_{min}</tex> и <tex>A'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2...a_{k}</tex>, где <tex>a_{i} \in \Sigma</tex>, такую что <tex> \langle s, \alpha \rangle \vdash^* \langle u, \varepsilon \rangle </tex>, <tex> \langle s', \alpha \rangle \vdash^* \langle u', \varepsilon \rangle </tex>. Пусть <tex>\langle s, a_1 \rangle \vdash^* \langle l, \varepsilon \rangle </tex> и <tex>\langle s', a_1 \rangle \vdash^* \langle l', \varepsilon \rangle </tex>. Так как <tex>s</tex> и <tex>s'</tex> эквивалентны, то <tex>l</tex> и <tex>l'</tex> эквивалентны. Аналогично для всех <tex>a_{i}</tex>. В итоге получим, что <tex>u</tex> эквивалентно <tex>u'</tex>. Значит для каждого состояния из <tex>A_{min}</tex> существует эквивалентное состояние из <tex>A'</tex><br>
Состояний в <tex>A'</tex> меньше чем в <tex>A_{min}</tex>, значит двум состояниям из <tex>A_{min}</tex> эквивалентно одно состояние из <tex>A'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.<br>
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.
==Время работы алгоритма==
Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.
==Пример==
