211
правок
Изменения
м
→Корректность алгоритма
Пусть в результате применения данного алгоритма к автомату <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> изоморфны.
