211
правок
Изменения
м
Нет описания правки
<li><tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>. </li>
</ol>
Рассмотрим <tex>x</tex> такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. <br/>Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. <br/>Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. <br/>
Значит, <tex>u</tex> и <tex>z</tex> эквивалентны.</li>
</ol>
==Алгоритм==
Основная идея алгоритма заключается в том, чтобы разбить состояния на классы эквивалентности — они и будут состояниями минимизированного автомата. <br/>Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. <br/>Будем помечать в таблице пары неэквивалентных состояний и класть их в очередь. <br/>
Изначально добавим в очередь <tex>Q</tex> пары состояний различимых строкой <tex> \varepsilon </tex> и пометим их в таблице.
Пока <tex>Q</tex> не станет пуста, будем делать следующее:
#Отметим в таблице и добавим в очередь <tex>Q</tex> все пары <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> не отмечена в таблице.
В момент опустошения очереди пары состояний, не помеченные в таблице, являются парами эквивалентных состояний.
За один проход по таблице, согласно теореме, разбиваем пары эквивалентных состояний на классы эквивалентности. <br/>Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата. <br/>
Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.
==Корректность алгоритма==
Пусть в результате применения данного алгоритма к автомату <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> изоморфны.
==Пример==
Минимизируем данный автомат. <br/>
[[Файл:dka.jpg]]
<br/>Будем рассматривать только нижний треугольник таблицы пар различимых состояний. <br/>
Отметили состояния, различающиеся строкой <tex>\varepsilon</tex>:
{| border = "1"
|}
Из таблицы видно, что классы эквивалентных состояний это <tex> \mathcal {f} A, B \mathcal {g}, \mathcal {f} C, D \mathcal {g}, \mathcal {f} F, G \mathcal {g}, \mathcal {f} E \mathcal {g}, \mathcal {f} H \mathcal {g} </tex>. <br/>Итого получили такой автомат: <br/> [[Файл:dkaMin.jpg]]
==Источники==
''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4
