Изменения

==Постановка задачи={{Задача|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> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА | неэквивалентных состояний]] и класть их в очередь.

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

Изначально добавим в очередь <tex>Q</tex> пары состоянийТерминальными состояниями полученного автомата будут состояния, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.Пока <tex>Q</tex> не станет пуста, будем делать следующее:#Извлечем пару <tex> \langle u, v \rangle </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> не отмечена в таблице.В момент опустошения очереди пары состояний, не помеченные в таблицесоответствующие классам эквивалентности, являются парами эквивалентных состояний. За один проход по таблице разбиваем пары эквивалентных состояний на классы эквивалентностисодержащим терминальные состояния исходного автомата.

Стартовым состоянием полученного автомата будет состояние===Корректность===Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>\mathcal{A}_{min}</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>A_\mathcal{A}_{min}</tex>. Докажемпостроен так, что этот автомат минимальный и единственный с точностью до изоморфизмав нем нет эквивалентных состояний. Противоречие.

Пусть существует автомат Так как каждому состоянию из <tex>\mathcal{A'</tex>, эквивалентный <tex>A</tex>, но с числом состояний меньшим, чем в <tex>A_}_{min}</tex>.Стартовые состояния эквивалентно состояние из <tex>s \in A_mathcal{minA}</tex> и <tex>s' \in A'</tex> эквивалентны, так как то автоматы <tex>A_\mathcal{min}</tex> и <tex>A'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2...a_{k}</tex>, где <tex>a__{imin} \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_mathcal{iA}</tex>. В итоге получим, что <tex>u</tex> эквивалентно <tex>u'</tex>. Значит, для каждого состояния из <tex>A_{min}</tex> существует эквивалентное состояние из <tex>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>A\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>A_{min}) <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>A_\in</tex> <tex>\delta^{min-1}</tex> эквивалентно одно состояние из [u][c] '''for''' s <tex>A'\in</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_\delta^{min-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>A_\delta^{min-1}</tex> эквивалентно состояние размером <tex>n \times |\Sigma|</tex>. <font color="green">// Шаг 2</font> Построим массив достижимости состояний из стартового {{---}} reachable размером <tex>A'n</tex>. <font color="green">// Шаги 3 и 4</font> '''boolean'''[][] marked = buildTable(n, isTerminal, то автоматы <tex>A_\delta^{min-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>An - 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>.

==Примерработы==Минимизируем данный автомат.:

Будем рассматривать только нижний треугольник таблицы пар различимых === Шаг <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>\varepsilon1</tex>:{| border align= "1center" |B | <tex>1</tex> |colspan align= "6center"|<tex>1</tex> |- |C align="center"| <tex>1</tex> | |colspan align= "5center"|<tex>0</tex> |- |D | | | |colspan align= "4center"|<tex>1</tex> |- |E | | | | |colspan align= "3center"|<tex>1</tex> |- |F |x |x |x |x |x |colspan align= "2center"|<tex>1</tex> |- |G |x |x |x |x |x | |colspan align= "1center"|<tex>1</tex> |- |H | | | | | |x |x |- | |A |B |C |D |E |F |G |}

На момент опустошения очереди:Вычислили таблицу.{| 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">● |colspan align= "6center"|<font color="black">● |- |! C |xalign="center"| <font color="black">● |x align="center"| <font color="black">● |colspan align= "5center"|<font color="black">● |- |D |x align="center"| <font color="black">● |x align="center"| <font color="black">● | align="center"| <font color="black">● |colspan align= "4center"|<font color="black">● |- ! D|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"| <font color="black">● |E |x |x align="center"| <font color="black">● |x align="center"| <font color="black">● |x align="center"| <font color="black">● |colspan align= "3center"|<font color="black">● |- ! E|align="center"| <font color="black">● |align="center"| <font color="black">● |align="center"|F<font color="black">● |xalign="center"| <font color="black">● |xalign="center"| <font color="black">● |x |xalign="center"| <font color="black">● |xalign="center"| <font color="black">● |colspan align= "2center"|<font color="black">● |- ! F|align="center"| <font color="black">● |Galign="center"| <font color="black">● |xalign="center"| <font color="black">● |xalign="center"| <font color="black">● |x align="center"| <font color="black">● |x align="center"| <font color="black">● |x | |colspan align= "1center"|<font color="black">● |- ! G|align="center"| <font color="black">● |align="center"|H<font color="black">● |x align="center"| <font color="black">● |x align="center"| <font color="black">● |x align="center"| <font color="black">● |x align="center"| <font color="black">● |x |x |xalign="center"| <font color="black">● |- ! H|align="center"| <font color="black">● |align="center"| <font color="black">● |Aalign="center"| <font color="black">● |Balign="center"| <font color="black">● |Calign="center"| <font color="black">● |Dalign="center"| <font color="black">● |Ealign="center"| <font color="black">● |Falign="center"| <font color="black">● |G |}

=== Шаг <tex> 5 </tex> ===Из таблицы видно, что классы эквивалентных состояний это <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>.

== См. также == * [[Минимизация ДКА, алгоритм Хопкрофта (сложность 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"]