1
правка
Изменения
можно было догадаться, тем не менее, не было очевидно, что это имеется в виду
{{Задача
|definition =
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\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>\mathcal {9} c \in \Sigma</tex> такой, что пара <tex>\langle \delta(u, c), \delta(v, c) \rangle</tex> помечена. Тогда мы можем пометить пару <tex> \langle u, v \rangle </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> построен так, что в нем нет эквивалентных состояний. Противоречие.
'''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] '''and''' '''not''' != isTerminal[j]
marked[i][j] = marked[j][i] = ''true''
Q.push(<tex>\langle i, j \rangle</tex>)
<tex>\langle u, v \rangle</tex> = Q.poll()
'''for''' c <tex>\in</tex> <tex>\Sigma</tex>
'''foreachfor''' r <tex>\in</tex> <tex>\delta^{-1}</tex>[u][c] '''foreachfor''' s <tex>\in</tex> <tex>\delta^{-1}</tex>[v][c]
'''if''' '''not''' marked[r][s]
marked[r][s] = marked[s][r] = ''true''
'''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
<font color="green">// Шаг 1</font>
Построим таблицу списков обратных ребер {{- --}} <tex>\delta^{-1}</tex> размером <tex>n \times n</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>)
'''int'''[] component[n] <font color="green">// По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.</font>
fill(component, -1)
'''vectorfor''' 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>
buildDFA(reachable, classes, 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;" ! 0'''Ø'''
! A
! B
! H
|-
|truealign="center"|<tex>1</tex>|truealign="center"|<tex>1</tex>|truealign="center"|<tex>1</tex>|truealign="center"|<tex>1</tex>|falsealign="center"|<tex>0</tex>|truealign="center"|<tex>1</tex>|truealign="center"|<tex>1</tex>|truealign="center"|<tex>1</tex>|truealign="center"|<tex>1</tex>
|}
=== Шаг <tex> 3 </tex>===
Инициализировали таблицу.
{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;"! ! 0'''Ø'''
! A
! B
! H
|-
! 0'''Ø'''
|
|
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|-
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|-
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|-
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|-
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|-
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|-
! F
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">●
|-
! G
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">●
|-
! H
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|}
Вычислили таблицу.
{| border="1" class="wikitable" width="20%" style="color: blue; background-color:#ffffcc;" cellpadding="10"; float: left;"
!
! 0'''Ø'''
! A
! B
! H
|-
! 0'''Ø'''
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|-
! A
|markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|-
! B
|markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|-
! C
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|-
! D
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|-
! E
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|-
! F
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">●
|-
! G
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">●
|
|
|markedalign="center"| <font color="black">●
|-
! H
|markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="center"| <font color="black">● |markedalign="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> ===
Итого получили такой автомат:
==Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 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"]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: Минимизация ДКА ]]
