Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определения== {{Определение |definition = Состояния <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex> е...»)
 
м (Псевдокод)
 
(не показаны 83 промежуточные версии 11 участников)
Строка 1: Строка 1:
==Определения==
+
{{Задача
{{Определение
 
 
|definition =  
 
|definition =  
Состояния <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex> если
+
Пусть дан [[Детерминированные_конечные_автоматы | автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
 
# <tex> \langle v, s \rangle \vdash^* \langle z, \varepsilon \rangle </tex>, где <tex>z \notin T </tex>
 
}}
 
{{Определение
 
|definition =
 
Состояния <tex>u</tex> и <tex>v</tex> эквивалентны, если они неразличимы никакой строкой <tex>s</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>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>\mathcal{A}_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.
 +
 +
Так как каждому состоянию из <tex>\mathcal{A}_{min}</tex> эквивалентно состояние из <tex>\mathcal{A}'</tex>, то автоматы <tex>\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"| <font color="black">●
 +
|align="center"| <font color="black">●
 +
|align="center"| <font color="black">●
 +
|align="center"| <font color="black">●
 +
|
 +
|}
 +
 +
=== Шаг <tex> 5 </tex> ===
 +
Из таблицы видно, что классы эквивалентных состояний это <tex>  \{A, B\}, \{C, D\}, \{F, G\}, \{E\}, \{H\}</tex>.
 +
 +
=== Шаг <tex> 6 </tex> ===
 +
Итого получили такой автомат:
 +
 +
[[Файл:dkaMin.png]]
 +
 +
== См. также ==
 +
* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
  
{{Теорема
+
==Источники информации==
|statement =
+
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4
Если <tex>u</tex> и <tex>v</tex>, <tex>v</tex> и <tex>z</tex> эквивалентны, то <tex>u</tex> и <tex>z</tex> эквивалентны.
+
* [[wikipedia:ru:DFA_minimization | Wikipedia {{---}} DFA minimization]]
|proof =
+
* [http://www.eecs.berkeley.edu/~sseshia/172/lectures/Lecture6.pdf Sanjit A. Seshia, "Minimization of DFAs"]
Пусть <tex>u</tex> и <tex>z</tex> неэквивалентны. Тогда <tex> \mathcal {9} s</tex>, такой, что
+
* [http://www.comp.nus.edu.sg/~cs4212/dfa-min.pdf National University of Singapore, "DFA Minimization"]
# <tex> \langle u, s \rangle \vdash^* \langle t, \varepsilon \rangle </tex>, где <tex>t \in T </tex>
 
# <tex> \langle z, s \rangle \vdash^* \langle t_1, \varepsilon \rangle </tex>, где <tex>t_1 \notin T </tex>.
 
Рассмотрим <tex>x</tex>, такой, что <tex> \langle v, s \rangle \vdash^* \langle x, \varepsilon \rangle </tex>. <br>
 
Если <tex>x \in T</tex>, то <tex>v</tex> и <tex>z</tex> различимы строкой <tex>s</tex>. Противоречие. <br>
 
Если <tex>x \notin T</tex>, то <tex>u</tex> и <tex>v</tex> различимы строкой <tex>s</tex>. Противоречие. <br>
 
Значит, <tex>u</tex> и <tex>z</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> \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>Q</tex>.
 
За один проход по таблице согласно теореме разбиваем не помеченные состояния на классы эквивалентности.
 

Текущая версия на 20:27, 4 июня 2022

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


Алгоритм[править]

Описание[править]

Основная идея алгоритма заключается в том, чтобы разбить состояния на классы эквивалентности — они и будут состояниями минимизированного автомата.

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

  • В исходном автомате мы имели [math]n[/math] состояний с номерами от [math]0[/math] до [math]n - 1[/math]. Удобно будет увеличить все номера состояний на [math]1[/math] и добавить в исходный автомат вершину [math]0[/math], в которую будут вести по умолчанию все переходы по всем символам (в том числе переходы по всем символам в эту вершину из неё самой), которых не было в исходном автомате, тем самым увеличив количество состояний [math]n[/math] на [math]1[/math]. Теперь стартовое состояние будет иметь номер [math]1[/math].
  • Шаг 1. Построим множество [math]\delta^{-1}[/math], в котором будем хранить списки обратных ребер.
  • Шаг 2. Найдем все достижимые состояния из стартового. Например, с помощью обхода в глубину.
  • Шаг 3. Добавим в очередь [math]Q[/math] пары состояний, различимых строкой [math] \varepsilon [/math], и пометим их в таблице.
  • Шаг 4. Для каждой непомеченной пары [math] \langle u, v \rangle [/math] нужно проверить, что [math]\exists c \in \Sigma[/math] такой, что пара [math]\langle \delta(u, c), \delta(v, c) \rangle[/math] помечена. Тогда мы можем пометить пару [math] \langle u, v \rangle [/math].
Пока [math]Q[/math] не станет пуста, будем делать следующее:
1. Извлечем пару [math] \langle u, v \rangle [/math] из [math]Q[/math].
2. Для каждого символа [math]c \in \Sigma[/math] перебираем пары состояний [math]\langle \delta^{-1}(u, c), \delta^{-1}(v,c) \rangle[/math]. Если находим ещё непомеченную пару, то помечаем её в таблице и кладем в очередь.
В момент опустошения очереди пары состояний, не помеченные в таблице, являются парами эквивалентных состояний.
  • Шаг 5. За один проход по таблице разбиваем пары эквивалентных состояний на классы эквивалентности.
  • Шаг 6. За один проход по списку классов эквивалентности выделяем список новых состояний и переходов между ними.

Стартовым состоянием полученного автомата будет состояние, соответствующее классу эквивалентности, содержащему стартовое состояние исходного автомата.

Терминальными состояниями полученного автомата будут состояния, соответствующие классам эквивалентности, содержащим терминальные состояния исходного автомата.

Корректность[править]

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

Пусть существует автомат [math]\mathcal{A}'[/math], эквивалентный [math]\mathcal{A}[/math], но с числом состояний меньшим, чем в [math]\mathcal{A}_{min}[/math]. Стартовые состояния [math]s \in \mathcal{A}_{min}[/math] и [math]s' \in \mathcal{A}'[/math] эквивалентны, так как [math]\mathcal{A}_{min}[/math] и [math]\mathcal{A}'[/math] допускают один и тот же язык. Рассмотрим строку [math]\alpha = a_1a_2 \ldots a_{k}[/math], где [math]a_{i} \in \Sigma[/math], такую, что [math] \langle s, \alpha \rangle \vdash^* \langle u, \varepsilon \rangle [/math], [math] \langle s', \alpha \rangle \vdash^* \langle u', \varepsilon \rangle [/math]. Пусть [math]\langle s, a_1 \rangle \vdash \langle l, \varepsilon \rangle [/math] и [math]\langle s', a_1 \rangle \vdash \langle l', \varepsilon \rangle [/math]. Так как [math]s[/math] и [math]s'[/math] эквивалентны, то [math]l[/math] и [math]l'[/math] эквивалентны. Аналогично для всех [math]a_{i}[/math]. В итоге получим, что [math]u[/math] эквивалентно [math]u'[/math]. Значит, для каждого состояния из [math]\mathcal{A}_{min}[/math] существует эквивалентное состояние из [math]\mathcal{A}'[/math].

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

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

Псевдокод[править]

Функция для построения таблицы неэквивалентности.

boolean[][] buildTable(int n, boolean[] isTerminal, vector[][] [math]\delta^{-1}[/math]):
   queue Q
   boolean marked[n][n]
   // Шаг 3
   for i = 0[math]\ldots[/math]n - 1
      for j = 0[math]\ldots[/math]n - 1
         if not marked[i][j] and isTerminal[i] != isTerminal[j]
            marked[i][j] = marked[j][i] = true
            Q.push([math]\langle i, j \rangle[/math])

   // Шаг 4
   while not Q.isEmpty()
      [math]\langle u, v \rangle[/math] = Q.poll()
      for c [math]\in[/math] [math]\Sigma[/math]
         for r [math]\in[/math] [math]\delta^{-1}[/math][u][c]
            for s [math]\in[/math] [math]\delta^{-1}[/math][v][c]	
               if not marked[r][s]
                  marked[r][s] = marked[s][r] = true
                  Q.push([math]\langle r, s \rangle[/math])
   return marked

Основная функция алгоритма.

function minimization(int n, boolean[] isTerminal, int[][] [math]\delta[/math]):
   // Шаг 1
   Построим таблицу списков обратных ребер — [math]\delta^{-1}[/math] размером [math]n \times |\Sigma|[/math].
   // Шаг 2
   Построим массив достижимости состояний из стартового — reachable размером [math]n[/math].
   // Шаги 3 и 4
   boolean[][] marked = buildTable(n, isTerminal, [math]\delta^{-1}[/math])
   // Шаг 5
   int[] component[n] // По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.
   fill(component, -1)
   for i = 0[math]\ldots[/math]n - 1
      if not marked[0][i]
         component[i] = 0
	
   int componentsCount = 0
   for i = 1[math]\ldots[/math]n - 1
      if not reachable[i]
         continue
      if component[i] == -1
         componentsCount++
         component[i] = componentsCount
         for j = i + 1[math]\ldots[/math]n - 1
            if not marked[i][j]
               component[j] = componentsCount
   // Шаг 6
   buildDFA(component) // Строим требуемый автомат.

Асимптотика[править]

Поиск недостижимых состояний с помощью обхода в глубину требует [math]\mathcal{O}(n \cdot |\Sigma|)[/math] времени. Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы [math]\mathcal{O}(n^2)[/math]. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за [math]\mathcal{O}(n^2)[/math].

Пример работы[править]

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

Dka.png

Шаг [math]1[/math][править]

Строим [math]\delta^{-1}[/math]. Например, [math]\delta^{-1}(F, 1) = \{C, D, G, F\}[/math].

Шаг [math] 2 [/math][править]

Построили массив достижимости состояний из стартового.

Ø A B C D E F G H
[math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]0[/math] [math]1[/math] [math]1[/math] [math]1[/math] [math]1[/math]

Шаг [math] 3 [/math][править]

Инициализировали таблицу.

Ø A B C D E F G H
Ø
A
B
C
D
E
F
G
H

Вычислили таблицу.

Ø A B C D E F G H
Ø
A
B
C
D
E
F
G
H

Шаг [math] 5 [/math][править]

Из таблицы видно, что классы эквивалентных состояний это [math] \{A, B\}, \{C, D\}, \{F, G\}, \{E\}, \{H\}[/math].

Шаг [math] 6 [/math][править]

Итого получили такой автомат:

DkaMin.png

См. также[править]

Источники информации[править]