1
правка
Изменения
можно было догадаться, тем не менее, не было очевидно, что это имеется в виду
==Алгоритм==
=== Описание ===
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата.
Для реализации алгоритма нам потребуются [[Очередь | очередь ]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь. Изначально добавим в очередь <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>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>\mathcal {9} 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>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...\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>.
Состояний в <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> изоморфны.
== Псевдокод ==
Функция для построения списка обратных ребертаблицы неэквивалентности. '''vectorboolean'''[][] buildReverseEdgesbuildTable('''int''' n, '''intboolean'''[][] <tex>\delta</tex>): isTerminal, '''intvector''' <tex>\delta^{-1}</tex>[n][n] '''for''' i = 0 .. n - 1 '''for''' c <tex>\in</tex> <tex>\Sigma</tex> <tex>\delta^{-1}</tex>[<tex>\delta</tex>[i][c]][c].add(i): '''returnqueue''' <tex>\delta^{-1}</tex>Q Функция для проверки достижимости состояний. '''function''' checkReachability('''int''' u, '''boolean'''marked[n] visited): visited[un] = true; '''for''' c <texfont color="green">\in</tex> <tex>\Sigma/ Шаг 3</texfont> '''iffor''' '''not''' visited[<tex>\delta</tex>[u][c]] checkReachability(i = 0<tex>\deltaldots</tex>[u][c], visited) Функция для инициализации таблицы неэквивалентности. '''function''' initTable('''int''' n, '''boolean'''[] isTerminal, '''queue''' Q, '''boolean'''[][] marked): '''for i = 0 .. n - 1 '''for''' j = 0 .. <tex>\ldots</tex>n - 1 '''if''' '''not''' marked[i][j] '''and''' isTerminalsisTerminal[i] '''and''' '''not''' isTerminals!= isTerminal[j] '''and''' i != j marked[i][j] = marked[j][i] = ''true''
Q.push(<tex>\langle i, j \rangle</tex>)
'''while''' '''not''' Q.isEmpty()
<tex>\langle u, v \rangle</tex> = Q.poll()
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
'''listfor''' rr = r <tex>\in</tex> <tex>\delta^{-1}</tex>[u][c] '''listfor''' ss = s <tex>\in</tex> <tex>\delta^{-1}</tex>[v][c] '''for''' i = 0 .. length(rr) - 1 '''int''' r = rr[i] '''for''' j = 0 .. length(ss) - 1 '''int''' s = ss[j]
'''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>
<font color="green">// Шаг 2</font>
<font color="green">// Шаг 5</font>
'''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font>
fill(component, -1)
'''listfor''' classes i = 0<font color="green"tex>// По позиции i будем хранить представителя i-ой компоненты эквивалентности.\ldots</fonttex> '''for''' i = 0 .. n - 1 '''if''' '''not''' tablemarked[0][i]
component[i] = 0
'''int''' components_count componentsCount = 0 '''for''' i = 1 .. <tex>\ldots</tex>n - 1 '''if''' '''not''' visitedreachable[i] ''continue''
'''if''' component[i] == -1
<font color="green">// Шаг 6</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> 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">●
|
|}
=== Шаг <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>.
=== Шаг <tex> 6 </tex> ===
Итого получили такой автомат:
[[Файл:dkaMin.png]]
== См. также ==
* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
==Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4
* [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"]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Минимизация ДКА ]]
