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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Псевдокод)
Строка 1: Строка 1:
 
==Постановка задачи==
 
==Постановка задачи==
Пусть дан автомат <tex>A</tex>. Требуется построить автомат <tex>A_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>A</tex>.
+
{{Задача
 +
|definition =
 +
Пусть дан [[Детерминированные_конечные_автоматы|автомат]] <tex>\mathcal{A}</tex>. Требуется построить автомат <tex>\mathcal{A}_{min}</tex> с наименьшим количеством состояний, распознающий тот же язык, что и <tex>\mathcal{A}</tex>.
 +
}}
  
 
==Алгоритм==
 
==Алгоритм==
Строка 6: Строка 9:
 
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата.
 
Основная идея алгоритма заключается в том, чтобы разбить состояния на [[Отношение эквивалентности#Классы эквивалентности|классы эквивалентности]] — они и будут состояниями минимизированного автомата.
  
Для реализации алгоритма нам потребуются очередь <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь.
+
Для реализации алгоритма нам потребуются [[Очередь|очередь]] <tex>Q</tex> и таблица <tex>marked</tex> размером <tex>n \times n</tex>, где <tex>n</tex> — количество состояний автомата. Будем помечать в таблице пары [[Эквивалентность состояний ДКА|неэквивалентных состояний]] и класть их в очередь.
  
 
* Удобно будем добавить в исходный автомат вершину <tex>0</tex>, в которую будут вести по умолчанию все переходы по всем символам, которых ещё не было в исходном автомате. Теперь стартовое состояние будет иметь номер <tex>1</tex>.
 
* Удобно будем добавить в исходный автомат вершину <tex>0</tex>, в которую будут вести по умолчанию все переходы по всем символам, которых ещё не было в исходном автомате. Теперь стартовое состояние будет иметь номер <tex>1</tex>.
 
* '''Шаг 1'''. Построим множество <tex>\delta^{-1}</tex>, в котором будем хранить списки обратных ребер.
 
* '''Шаг 1'''. Построим множество <tex>\delta^{-1}</tex>, в котором будем хранить списки обратных ребер.
* '''Шаг 2'''. Найдем все достижимые состояния из стартового.
+
* '''Шаг 2'''. Найдем все достижимые состояния из стартового. Например, с помощью [[Обход_в_глубину,_цвета_вершин|обхода в глубину]].
 
* '''Шаг 3'''. Добавим в очередь <tex>Q</tex> пары состояний, различимых строкой <tex> \varepsilon </tex>, и пометим их в таблице.
 
* '''Шаг 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>.
 
* '''Шаг 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>.
Строка 24: Строка 27:
  
 
===Корректность===
 
===Корректность===
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>A_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма.
+
Пусть в результате применения данного алгоритма к автомату <tex>A</tex> мы получили автомат <tex>\mathcal{A}_{min}</tex>. Докажем, что этот автомат минимальный и единственный с точностью до изоморфизма.
  
Пусть существует автомат <tex>A'</tex>, эквивалентный <tex>A</tex>, но с числом состояний меньшим, чем в <tex>A_{min}</tex>.
+
Пусть существует автомат <tex>\mathcal{A}'</tex>, эквивалентный <tex>\mathcal{A}</tex>, но с числом состояний меньшим, чем в <tex>\mathcal{A}_{min}</tex>.
Стартовые состояния <tex>s \in A_{min}</tex> и <tex>s' \in A'</tex> эквивалентны, так как <tex>A_{min}</tex> и <tex>A'</tex> допускают один и тот же язык. Рассмотрим строку <tex>\alpha = a_1a_2...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_{min}</tex> существует эквивалентное состояние из <tex>A'</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...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>A_{min}</tex>, значит двум состояниям из <tex>A_{min}</tex> эквивалентно одно состояние из <tex>A'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>A_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.
+
Состояний в <tex>A'</tex> меньше, чем в <tex>\mathcal{A}_{min}</tex>, значит двум состояниям из <tex>\mathcal{A}_{min}</tex> эквивалентно одно состояние из <tex>\mathcal{A}'</tex>. Тогда эти два состояния эквивалентны, но автомат <tex>\mathcal{A}_{min}</tex> построен так, что в нем нет эквивалентных состояний. Противоречие.
  
Так как каждому состоянию из <tex>A_{min}</tex> эквивалентно состояние из <tex>A'</tex>, то автоматы <tex>A_{min}</tex> и <tex>A'</tex> изоморфны.
+
Так как каждому состоянию из <tex>\mathcal{A}_{min}</tex> эквивалентно состояние из <tex>\mathcal{A}'</tex>, то автоматы <tex>\mathcal{A}_{min}</tex> и <tex>\mathcal{A}'</tex> изоморфны.
  
 
== Псевдокод ==
 
== Псевдокод ==
Функция для построения списка обратных ребер.
 
'''vector'''[][] buildReverseEdges('''int''' n, '''int'''[][] <tex>\delta</tex>):
 
    '''int''' <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)
 
    '''return''' <tex>\delta^{-1}</tex>
 
 
Функция для проверки достижимости состояний.
 
'''function''' checkReachability('''int''' u, '''boolean'''[] visited):
 
    visited[u] = true
 
    '''for''' c <tex>\in</tex> <tex>\Sigma</tex>
 
      '''if''' '''not''' visited[<tex>\delta</tex>[u][c]]
 
          checkReachability(<tex>\delta</tex>[u][c], visited)
 
 
 
Функция для инициализации таблицы неэквивалентности.
 
Функция для инициализации таблицы неэквивалентности.
 
  '''function''' initTable('''int''' n, '''boolean'''[] isTerminal, '''queue''' Q, '''boolean'''[][] marked):
 
  '''function''' initTable('''int''' n, '''boolean'''[] isTerminal, '''queue''' Q, '''boolean'''[][] marked):
Строка 58: Строка 46:
  
 
Функция для вычисления таблицы неэквивалентности.
 
Функция для вычисления таблицы неэквивалентности.
  '''function''' computeTable('''int''' n, '''int'''[][] <tex>\delta^{-1}</tex>, '''queue''' Q, '''boolean'''[][] marked):
+
  '''function''' computeTable('''int''' n, '''list'''[][] <tex>\delta^{-1}</tex>, '''queue''' Q, '''boolean'''[][] marked):
 
     '''while''' '''not''' Q.isEmpty()
 
     '''while''' '''not''' Q.isEmpty()
 
       <tex>\langle u, v \rangle</tex> = Q.poll()
 
       <tex>\langle u, v \rangle</tex> = Q.poll()
Строка 75: Строка 63:
 
  '''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
 
  '''function''' minimization('''int''' n, '''boolean'''[] isTerminal, '''int'''[][] <tex>\delta</tex>):
 
     <font color="green">// Шаг 1</font>
 
     <font color="green">// Шаг 1</font>
     '''int'''[][] <tex>\delta^{-1}</tex> = buildReverseEdges(n, <tex>\delta</tex>)
+
     '''list'''[][] <tex>\delta^{-1}</tex> = buildReverseEdges(n, <tex>\delta</tex>) <font color="green">// Cтроим список обратных ребер.</font>
 
     <font color="green">// Шаг 2</font>
 
     <font color="green">// Шаг 2</font>
 
     '''boolean''' reachable[n]
 
     '''boolean''' reachable[n]
     checkReachability(1, reachable)  
+
     checkReachability(1, reachable) <font color="green">// Cтроим таблицу достижимости состояний.</font>
 
     <font color="green">// Шаг 3</font>
 
     <font color="green">// Шаг 3</font>
 
     '''queue''' Q
 
     '''queue''' Q
Строка 105: Строка 93:
 
                 component[j] = components_count
 
                 component[j] = components_count
 
     <font color="green">// Шаг 6</font>
 
     <font color="green">// Шаг 6</font>
     '''for''' i = 0 .. length(classes) - 1
+
     buildDFA(classes, component) <font color="green">// Строим по классам эквивалентности требуемый автомат.</font>
      '''int''' u = component[classes[i]]
 
      '''for''' c <tex>\in</tex> <tex>\Sigma</tex>
 
          if reachable[<tex>\delta</tex>[classes[i]][c]] '''and''' component[<tex>\delta</tex>[classes[i]][c]] != 0
 
            int v = component[<tex>\delta</tex>[classes[i]][c]]
 
            output(u ->[c]-> v) <font color="green">// Ребро из u в v по символу c</font>
 
  
==Асимптотики==
+
==Асимптотика==
Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.
+
Поиск недостижимых состояний с помощью [[Обход_в_глубину,_цвета_вершин|обхода в глубину]] требует <tex>O(n \cdot |\Sigma|)</tex> времени. Каждую пару мы добавляли в очередь один раз, значит время заполнения таблицы <tex>O(n^2)</tex>. Разбиение на классы эквивалентности делается за один проход по таблице, то есть за <tex>O(n^2)</tex>.
  
 
==Пример работы==
 
==Пример работы==
Строка 382: Строка 365:
  
 
[[Файл:dkaMin.png]]
 
[[Файл:dkaMin.png]]
 +
 +
== См. также ==
 +
* [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
  
 
==Источники информации==
 
==Источники информации==
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4
 
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, 2-е издание. Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 171 - 182. — ISBN 5-8459-0261-4
* [http://en.wikipedia.org/wiki/DFA_minimization Wikipedia:DFA_minimization]
+
* [[wikipedia:ru:DFA_minimization|Wikipedia {{---}} DFA minimization]]
* [http://www.eecs.berkeley.edu/~sseshia/172/lectures/Lecture6.pdf Minimization of DFAs]
+
* [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 DFA Minimization]
+
* [http://www.comp.nus.edu.sg/~cs4212/dfa-min.pdf National University of Singapore, "DFA Minimization"]
  
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 00:12, 4 ноября 2014

Постановка задачи

Задача:
Пусть дан автомат [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]0[/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]\mathcal {9} 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...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] изоморфны.

Псевдокод

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

function initTable(int n, boolean[] isTerminal, queue Q, boolean[][] marked):
   for i = 0 .. n - 1
      for j = 0 .. n - 1
         if not marked[i][j] and isTerminals[i] and not isTerminals[j] and i != j
            marked[i][j] = marked[j][i] = true
            Q.push([math]\langle i, j \rangle[/math])

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

function computeTable(int n, list[][] [math]\delta^{-1}[/math], queue Q, boolean[][] marked):
   while not Q.isEmpty()
      [math]\langle u, v \rangle[/math] = Q.poll()
      for c [math]\in[/math] [math]\Sigma[/math]
         list rr = [math]\delta^{-1}[/math][u][c]
         list ss = [math]\delta^{-1}[/math][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([math]\langle r, s \rangle[/math])

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

function minimization(int n, boolean[] isTerminal, int[][] [math]\delta[/math]):
   // Шаг 1
   list[][] [math]\delta^{-1}[/math] = buildReverseEdges(n, [math]\delta[/math]) // Cтроим список обратных ребер.
   // Шаг 2
   boolean reachable[n]
   checkReachability(1, reachable) // Cтроим таблицу достижимости состояний.
   // Шаг 3
   queue Q
   boolean marked[n][n]
   initTable(n, isTerminal, Q, marked)
   // Шаг 4
   computeTable(n, [math]\delta^{-1}[/math], Q, marked)
   // Шаг 5
   int[] component[n] // По позиции i будем хранить номер компоненты эквивалентности для i-ого состояния.
   fill(component, -1)
   list classes // По позиции i будем хранить представителя i-ой компоненты эквивалентности.
   for i = 0 .. n - 1
      if not table[0][i]
         component[i] = 0
	
   int components_count = 0
   for i = 1 .. n - 1
      if not visited[i]
         continue
      if component[i] == -1
         components_count++
         component[i] = components_count
         classes.add(i)
         for j = i + 1 .. n - 1
            if not table[i][j]
               component[j] = components_count
   // Шаг 6
   buildDFA(classes, component) // Строим по классам эквивалентности требуемый автомат.

Асимптотика

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

Пример работы

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

Dka.png

Шаг 1

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

Шаг 2

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

0 A B C D E F G H
true true true true false true true true true

Шаг 3

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

0 A B C D E F G H
0 marked marked
A marked marked
B marked marked
C marked marked
D marked marked
E marked marked
F marked marked marked marked marked marked marked
G marked marked marked marked marked marked marked
H marked marked

Шаг 4

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

0 A B C D E F G H
0 marked marked marked marked marked marked marked marked
A marked marked marked marked marked marked marked
B marked marked marked marked marked marked marked
C marked marked marked marked marked marked marked
D marked marked marked marked marked marked marked
E marked marked marked marked marked marked marked marked
F marked marked marked marked marked marked marked
G marked marked marked marked marked marked marked
H marked marked marked marked marked marked marked marked

Шаг 5

Из таблицы видно, что классы эквивалентных состояний это [math] \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} [/math].

Шаг 6

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

DkaMin.png

См. также

Источники информации