Изменения

{{Задача|definition = Пусть дан [[Детерминированные_конечные_автоматы|автомат ]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>A_\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.}}

Для реализации алгоритма нам потребуются [[Очередь|очередь ]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь.

* '''Шаг 2'''. Найдем все достижимые состояния из стартового. Например, с помощью [[Обход_в_глубину,_цвета_вершин|обхода в глубину]].

Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_\mathcal{A}_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма.

Пусть существует автомат <tex>\mathcal{A}'</tex>, эквивалентный <tex>\mathcal{A}</tex>, но с числом состояний меньшим, чем в <tex>A_\mathcal{A}_{min}</tex>.Стартовые состояния <tex>s \in A_\mathcal{A}_{min}</tex> и <tex>s' \in \mathcal{A}'</tex> эквивалентны, так как <tex>A_\mathcal{A}_{min}</tex> и <tex>\mathcal{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_\mathcal{A}_{min}</tex> существует эквивалентное состояние из <tex>\mathcal{A}'</tex>.

Состояний в <tex>A'</tex> меньше, чем в <tex>A_\mathcal{A}_{min}</tex>, значит двум состояниям из <tex>A_\mathcal{A}_{min}</tex> эквивалентно одно состояние из <tex>\mathcal{A}'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_\mathcal{A}_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.

Так как каждому состоянию из <tex>A_\mathcal{A}_{min}</tex> эквивалентно состояние из <tex>\mathcal{A}'</tex>, то автоматы <tex>A_\mathcal{A}_{min}</tex> и <tex>\mathcal{A}'</tex> изоморфны.

'''function''' computeTable('''int''' n, '''intlist'''[][] <tex>\delta^{-1}</tex>, '''queue''' Q, '''boolean'''[][] marked):

'''intlist'''[][] <tex>\delta^{-1}</tex> = buildReverseEdges(n, <tex>\delta</tex>)<font color="green">// Cтроим список обратных ребер.</font>

checkReachability(1, reachable) <font color="green">// Cтроим таблицу достижимости состояний.</font>

'''for''' i = 0 .. lengthbuildDFA(classes) - 1 '''int''' u = component[classes[i]] '''for''' c <tex>\in</tex> <tex>\Sigma</tex> if reachable[<tex>\delta</tex>[classes[i]][c]] '''and''' , component[<tex>\delta</tex>[classes[i]][c]] != 0 int v = component[<tex>\delta</tex>[classes[i]][c]] output(u ->[c]-> v) <font color="green">// Ребро из u в v Строим по символу cклассам эквивалентности требуемый автомат.</font>

==АсимптотикиАсимптотика==Поиск недостижимых состояний с помощью [[Обход_в_глубину,_цвета_вершин|обхода в глубину]] требует <tex>O(n \cdot |\Sigma|)</tex> времени. Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.

* [http[wikipedia:ru://en.wikipedia.org/wiki/DFA_minimization |Wikipedia:DFA_minimization{{---}} DFA minimization]]* [http://www.eecs.berkeley.edu/~sseshia/172/lectures/Lecture6.pdf Sanjit A. Seshia, "Minimization of DFAs"]* [http://www.comp.nus.edu.sg/~cs4212/dfa-min.pdf National University of Singapore, "DFA Minimization"]