Изменения

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

=== Описание ===Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата. <br /> Для реализации алгоритма нам потребуются [[Очередь | очередь ]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. <br />Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь.  * В исходном автомате мы имели <tex>n<br /tex>Изначально добавим в очередь состояний с номерами от <tex>0</tex> до <tex>Qn - 1</tex> пары . Удобно будет увеличить все номера состояний, различимых строкой на <tex> \varepsilon 1</tex>, и пометим их добавить в таблице.Пока исходный автомат вершину <tex>Q0</tex> , в которую будут вести по умолчанию все переходы по всем символам (в том числе переходы по всем символам в эту вершину из неё самой), которых не станет пустабыло в исходном автомате, будем делать следующее:#Извлечем пару тем самым увеличив количество состояний <tex>n</tex> на <tex>1</tex>. Теперь стартовое состояние будет иметь номер <tex> \langle u, v \rangle 1</tex> из .* '''Шаг 1'''. Построим множество <tex>Q\delta^{-1}</tex>, в котором будем хранить списки обратных ребер.#Отметим * '''Шаг 2'''. Найдем все достижимые состояния из стартового. Например, с помощью [[Обход_в_глубину,_цвета_вершин | обхода в таблице и добавим глубину]].* '''Шаг 3'''. Добавим в очередь <tex>Q</tex> все пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.* '''Шаг 4'''. Для каждой непомеченной пары <tex> \langle tu, k v \rangle </tex> такиенужно проверить, что <tex> \mathcal {9} exists c \in \Sigma</tex> такой, что пара <tex>\langle t\delta(u, c ), \delta(v, c) \rangle \vdash </tex> помечена. Тогда мы можем пометить пару <tex> \langle u, \varepsilon v \rangle</tex>.: Пока <tex>Q</tex> не станет пуста, будем делать следующее:: 1. Извлечем пару <tex> \langle ku, c v \rangle </tex> из <tex>Q</tex>. : 2. Для каждого символа <tex>c \vdash in \langle v, \varepsilon \rangle Sigma</tex>, и пара перебираем пары состояний <tex> \langle t\delta^{-1}(u, c), \delta^{-1}(v, k c) \rangle</tex> не отмечена . Если находим ещё непомеченную пару, то помечаем её в таблицеи кладем в очередь.: В момент опустошения очереди пары состояний, не помеченные в таблице, являются парами эквивалентных состояний. * '''Шаг 5'''. За один проход по таблице, согласно теореме, разбиваем пары эквивалентных состояний на классы эквивалентности. <br />* '''Шаг 6'''. За один проход по списку классов эквивалентности выделяем список новых состояний и переходов между ними.Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата. <br /> 

===Корректность алгоритма===Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_\mathcal{A}_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма. <br /> Пусть существует автомат <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...\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>A_\mathcal{A}_{min}</tex> существует эквивалентное состояние из <tex>\mathcal{A}'</tex>.<br /> Состояний в <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> построен так, что в нем нет эквивалентных состояний. Противоречие.<br /> Так как каждому состоянию из <tex>A_\mathcal{A}_{min}</tex> эквивалентно состояние из <tex>\mathcal{A}'</tex>, то автоматы <tex>A_\mathcal{A}_{min}</tex> и <tex>\mathcal{A}'</tex> изоморфны. == Псевдокод ==Функция для построения таблицы неэквивалентности. '''boolean'''[][] buildTable('''int''' n, '''boolean'''[] isTerminal, '''vector'''[][] <tex>\delta^{-1}</tex>): '''queue''' Q '''boolean''' marked[n][n] <font color="green">// Шаг 3</font> '''for''' i = 0<tex>\ldots</tex>n - 1 '''for''' j = 0<tex>\ldots</tex>n - 1 '''if''' '''not''' marked[i][j] '''and''' isTerminal[i] != isTerminal[j] marked[i][j] = marked[j][i] = ''true'' Q.push(<tex>\langle i, j \rangle</tex>) <font color="green">// Шаг 4</font> '''while''' '''not''' Q.isEmpty() <tex>\langle u, v \rangle</tex> = Q.poll() '''for''' c <tex>\in</tex> <tex>\Sigma</tex> '''for''' r <tex>\in</tex> <tex>\delta^{-1}</tex>[u][c] '''for''' s <tex>\in</tex> <tex>\delta^{-1}</tex>[v][c] '''if''' '''not''' marked[r][s] marked[r][s] = marked[s][r] = ''true'' Q.push(<tex>\langle r, s \rangle</tex>) '''return''' marked Основная функция алгоритма. '''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>): <font color="green">// Шаг 1</font> Построим таблицу списков обратных ребер {{---}} <tex>\delta^{-1}</tex> размером <tex>n \times |\Sigma|</tex>. <font color="green">// Шаг 2</font> Построим массив достижимости состояний из стартового {{---}} reachable размером <tex>n</tex>. <font color="green">// Шаги 3 и 4</font> '''boolean'''[][] marked = buildTable(n, isTerminal, <tex>\delta^{-1}</tex>) <font color="green">// Шаг 5</font> '''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font> fill(component, -1) '''for''' i = 0<tex>\ldots</tex>n - 1 '''if''' '''not''' marked[0][i] component[i] = 0 '''int''' componentsCount = 0 '''for''' i = 1<tex>\ldots</tex>n - 1 '''if''' '''not''' reachable[i] ''continue'' '''if''' component[i] == -1 componentsCount++ component[i] = componentsCount '''for''' j = i + 1<tex>\ldots</tex>n - 1 '''if''' '''not''' marked[i][j] component[j] = componentsCount <font color="green">// Шаг 6</font> buildDFA(component) <font color="green">// Строим требуемый автомат.</font> ==Асимптотика==Поиск недостижимых состояний с помощью [[Обход_в_глубину,_цвета_вершин | обхода в глубину]] требует <tex>\mathcal{O}(n \cdot |\Sigma|)</tex> времени. Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>\mathcal{O}(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>\mathcal{O}(n^2)</tex>. ==Пример работы==Минимизируем данный автомат: [[Файл:dka.png]] === Шаг <tex>1</tex> ===Строим <tex>\delta^{-1}</tex>. Например, <tex>\delta^{-1}(F, 1) = \{C, D, G, F\}</tex>. === Шаг <tex> 2 </tex> ===Построили массив достижимости состояний из стартового.{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;"  !'''Ø'''! A! B! C! D! E! F! G! H|-|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>0</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|align="center"|<tex>1</tex>|} === Шаг <tex> 3 </tex>===Инициализировали таблицу.{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;" !!'''Ø'''! A! B! C! D! E! F! G! H|-!'''Ø'''|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! A|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! B|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! C|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! D|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! E|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||-! F|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! G|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! H|||||||align="center"| <font color="black">● |align="center"| <font color="black">● ||}

Вычислили таблицу.{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;" ! !'''Ø'''! A! B! C! D! E! F! G! H|-!'''Ø'''||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! A|align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! B|align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! C|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! D|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! E|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● ||align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |-! F|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! G|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |||align="center"| <font color="black">● |-! H|align="center"| <font color="black">● |align="center"| <font color="black">● |align=Время работы алгоритма"center"| <font color="black">● |align="center"| <font color="black">● Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы |align="center"| <texfont color="black">O(n^2)● |align="center"| </texfont color="black">. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за ● |align="center"| <texfont color="black">O(n^2)● |align="center"| </texfont color="black">.● ||}

==Пример==Минимизируем данный автомат. Шаг <br /tex>[[Файл:dka.jpg]]5 <br /tex>===Будем рассматривать только нижний треугольник Из таблицы пар различимых видно, что классы эквивалентных состояний. <br />Отметили состояния, различающиеся строкой это <tex> \varepsilon</tex>:{| border = "1" |A, B | |colspan = "6"| |- |\}, \{C | | |colspan = "5"| |- |, D | | | |colspan = "4"| |- |E | | | | |colspan = "3"| |- |\}, \{F |x |x |x |x |x |colspan = "2"| |- |, G |x |x |x |x |x | |colspan = "1"| |- |\}, \{E\}, \{H | | | | | |x |x |- | |A |B |C |D |E |F |G |\}</tex>.

На момент опустошения очереди[[Файл:{| border = "1" |B | |colspan = "6"| |- |C |x |x |colspan = "5"| |- |D |x |x | |colspan = "4"| |- |E |x |x |x |x |colspan = "3"| |- |F |x |x |x |x |x |colspan = "2"| |- |G |x |x |x |x |x | |colspan = "1"| |- |H |x |x |x |x |x |x |x |- | |A |B |C |D |E |F |G |}dkaMin.png]]

Из таблицы видно, что классы эквивалентных состояний это <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Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]

==Источникиинформации==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4* [[wikipedia:ru:DFA_minimization | Wikipedia {{---}} 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"]