1632
правки
Изменения
м
rollbackEdits.php mass rollback
* '''Шаг 2'''. Найдем все достижимые состояния из стартового. Например, с помощью [[Обход_в_глубину,_цвета_вершин | обхода в глубину]].
* '''Шаг 3'''. Добавим в очередь <tex>Q</tex> пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.
* '''Шаг 4'''. Для каждой непомеченной пары <tex> \langle u, v \rangle </tex> нужно проверить, что <tex>\mathcal {9} exists c \in \Sigma</tex> такой, что пара <tex>\langle \delta(u, c), \delta(v, c) \rangle</tex> помечена. Тогда мы можем пометить пару <tex> \langle u, v \rangle </tex>.
: Пока <tex>Q</tex> не станет пуста, будем делать следующее:
: 1. Извлечем пару <tex> \langle u, v \rangle </tex> из <tex>Q</tex>.
Пусть существует автомат <tex>\mathcal{A}'</tex>, эквивалентный <tex>\mathcal{A}</tex>, но с числом состояний меньшим, чем в <tex>\mathcal{A}_{min}</tex>.
Стартовые состояния <tex>s \in \mathcal{A}_{min}</tex> и <tex>s' \in \mathcal{A}'</tex> эквивалентны, так как <tex>\mathcal{A}_{min}</tex> и <tex>\mathcal{A}'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2 \ldots 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>\mathcal{A}_{min}</tex> существует эквивалентное состояние из <tex>\mathcal{A}'</tex>.
Состояний в <tex>A'</tex> меньше, чем в <tex>\mathcal{A}_{min}</tex>, значит двум состояниям из <tex>\mathcal{A}_{min}</tex> эквивалентно одно состояние из <tex>\mathcal{A}'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>\mathcal{A}_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.
'''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
<font color="green">// Шаг 1</font>
Построим таблицу списков обратных ребер {{---}} <tex>\delta^{-1}</tex> размером <tex>n \times n|\Sigma|</tex>.
<font color="green">// Шаг 2</font>
Построим массив достижимости состояний из стартового {{---}} reachable размером <tex>n</tex>.
