Алгоритм Хопкрофта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_со...»)
 
(Простой алгоритм)
Строка 7: Строка 7:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Класс <tex>S</tex> '''разбивает''' класс <tex>R</tex> по символу <tex>a</tex> на <tex>R_1</tex> и <tex>R_2</tex>, если  
+
Класс <tex>C</tex> '''разбивает''' класс <tex>R</tex> по символу <tex>a</tex> на <tex>R_1</tex> и <tex>R_2</tex>, если  
# <tex>\forall r \in R_1 \,\,\, \delta(r, a) \in S</tex>  
+
# <tex>\forall r \in R_1 \,\,\, \delta(r, a) \in C</tex>  
# <tex>\forall r \in R_2 \,\,\, \delta(r, a) \notin S</tex>  
+
# <tex>\forall r \in R_2 \,\,\, \delta(r, a) \notin C</tex>  
 
}}  
 
}}  
 
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
 
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Строка 16: Строка 16:
 
Итеративно строим разбиение множества состояний следующим образом.
 
Итеративно строим разбиение множества состояний следующим образом.
 
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>F</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
 
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>F</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(F, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
+
# Перебираются символы алфавита <tex>c \in \Sigma</tex>, все пары <tex>(F, c)</tex> и <tex>(Q \setminus F, c)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
+
# Из очереди извлекается пара <tex>(C, a)</tex>, <tex>C</tex> далее именуется как сплиттер.
 
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.  
 
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.  
 
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
 
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
Строка 25: Строка 25:
 
<tex>Q</tex> {{---}} множество состояний ДКА.
 
<tex>Q</tex> {{---}} множество состояний ДКА.
 
<tex>F</tex> {{---}} множество терминальных состояний.
 
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
+
<tex>S</tex> {{---}} очередь.
 
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
 
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
 
<tex>R</tex> {{---}} класс состояний ДКА.
 
<tex>R</tex> {{---}} класс состояний ДКА.
 
   <tex>P \leftarrow \{ F, Q \setminus F \}</tex>
 
   <tex>P \leftarrow \{ F, Q \setminus F \}</tex>
   <tex>W \leftarrow \{ \}</tex>
+
   <tex>S \leftarrow \varnothing </tex>
   '''for all''' <tex>a \in \Sigma</tex>
+
   '''for all''' <tex>c \in \Sigma</tex>
     <tex>W</tex>'''.push'''(<tex>F, a</tex>)
+
     <tex>S</tex>'''.push'''(<tex>F, c</tex>)
     <tex>W</tex>'''.push'''(<tex>Q \setminus F, a</tex>)
+
     <tex>S</tex>'''.push'''(<tex>Q \setminus F, c</tex>)
   '''while not''' <tex>W</tex>'''.isEmpty()'''  
+
   '''while not''' <tex>S</tex>'''.isEmpty'''()
     <tex>W</tex>'''.pop'''(<tex>S, a</tex>)
+
     <tex>(C, a)</tex> <tex> \leftarrow </tex> <tex>S</tex>'''.pop'''()
 
     '''for all''' <tex>R</tex> '''in''' <tex>P</tex>  
 
     '''for all''' <tex>R</tex> '''in''' <tex>P</tex>  
       <tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
+
       <tex>R_1 = R \cap \delta^{-1} (C, a) </tex>
 
       <tex>R_2 = R \setminus R_1</tex>
 
       <tex>R_2 = R \setminus R_1</tex>
       '''if''' <tex> |R_1| \ne 0</tex> '''and''' <tex>|R_2| \ne 0</tex>
+
       '''if''' <tex> R_1 \ne \varnothing </tex> '''and''' <tex> R_2 \ne \varnothing </tex>
 
         '''replace''' <tex>R</tex> '''in''' <tex>P</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
 
         '''replace''' <tex>R</tex> '''in''' <tex>P</tex> '''with''' <tex>R_1</tex> '''and''' <tex>R_2</tex>
 
         '''for all''' <tex> c \in \Sigma </tex>  
 
         '''for all''' <tex> c \in \Sigma </tex>  
           <tex>W</tex>'''.push'''(<tex>R_1, c</tex>)
+
           <tex>S</tex>'''.push'''(<tex>R_1, c</tex>)
           <tex>W</tex>'''.push'''(<tex>R_2, c</tex>)
+
           <tex>S</tex>'''.push'''(<tex>R_2, c</tex>)
 
Когда очередь станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
 
Когда очередь станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
  
 
===Время работы===
 
===Время работы===
Время работы алгоритма оценивается как <tex>O(|\Sigma| \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| \cdot n)</tex>, получаем указанную оценку.
+
Время работы алгоритма оценивается как <tex>O(|\Sigma| \cdot n^2)</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(C, a)</tex> попала в очередь, и класс <tex>C</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса <tex>C_1</tex> и <tex>C_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|C| \ge |C_i| + 1</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(n)</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| \cdot n)</tex>, получаем указанную оценку.
  
 
== Алгоритм Хопкрофта==
 
== Алгоритм Хопкрофта==

Версия 21:33, 6 ноября 2013

Пусть дан автомат, распознающий определенный язык. Требуется найти эквивалентный автомат с наименьшим количеством состояний.

Минимизация ДКА

Если в ДКА существуют два эквивалентных состояния, то при их объединении мы получим эквивалентный ДКА, так как распознаваемый язык не изменится. Основная идея минимизации состоит в разбиении множества состояний на классы эквивалентности, полученные классы и будут состояниями минимизированного ДКА.

Простой алгоритм

Определение:
Класс [math]C[/math] разбивает класс [math]R[/math] по символу [math]a[/math] на [math]R_1[/math] и [math]R_2[/math], если
  1. [math]\forall r \in R_1 \,\,\, \delta(r, a) \in C[/math]
  2. [math]\forall r \in R_2 \,\,\, \delta(r, a) \notin C[/math]

Если класс [math]R[/math] может быть разбит по символу [math]a[/math], то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний. Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.

  1. Первоначальное разбиение множества состояний — класс допускающих состояний [math]F[/math] и класс недопускающих состояний [math]Q \setminus F[/math].
  2. Перебираются символы алфавита [math]c \in \Sigma[/math], все пары [math](F, c)[/math] и [math](Q \setminus F, c)[/math] помещаются в очередь.
  3. Из очереди извлекается пара [math](C, a)[/math], [math]C[/math] далее именуется как сплиттер.
  4. Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу [math]a[/math] переходят в сплиттер, а второй из всех оставшихся.
  5. Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
  6. Пока очередь не пуста, выполняем п.3 – п.5.

Псевдокод

[math]Q[/math] — множество состояний ДКА. [math]F[/math] — множество терминальных состояний. [math]S[/math] — очередь. [math]P[/math] — разбиение множества состояний ДКА. [math]R[/math] — класс состояний ДКА.

 [math]P \leftarrow \{ F, Q \setminus F \}[/math]
 [math]S \leftarrow \varnothing [/math]
 for all [math]c \in \Sigma[/math]
   [math]S[/math].push([math]F, c[/math])
   [math]S[/math].push([math]Q \setminus F, c[/math])
 while not [math]S[/math].isEmpty()
   [math](C, a)[/math] [math] \leftarrow [/math] [math]S[/math].pop()
   for all [math]R[/math] in [math]P[/math] 
     [math]R_1 = R \cap \delta^{-1} (C, a) [/math]
     [math]R_2 = R \setminus R_1[/math]
     if [math] R_1 \ne \varnothing [/math] and [math] R_2 \ne \varnothing [/math]
       replace [math]R[/math] in [math]P[/math] with [math]R_1[/math] and [math]R_2[/math]
       for all [math] c \in \Sigma [/math] 
         [math]S[/math].push([math]R_1, c[/math])
         [math]S[/math].push([math]R_2, c[/math])

Когда очередь станет пустой, будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

Время работы

Время работы алгоритма оценивается как [math]O(|\Sigma| \cdot n^2)[/math], где [math] n [/math] — количество состояний ДКА, а [math] \Sigma [/math]— алфавит. Это следует из того, что если пара [math](C, a)[/math] попала в очередь, и класс [math]C[/math] использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь добавляется два класса [math]C_1[/math] и [math]C_2[/math], причем можно гарантировать лишь следующее уменьшение размера: [math]|C| \ge |C_i| + 1[/math]. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем [math]O(n)[/math] раз. Учитывая, что ребер всего [math]O(|\Sigma| \cdot n)[/math], получаем указанную оценку.

Алгоритм Хопкрофта

Лемма:
Класс [math]R = R_1 \cup R_2[/math] и [math]R_1 \cap R_2 = \varnothing[/math], тогда разбиение всех классов (текущее разбиение) по символу [math]a[/math] любыми двумя классами из [math]R, R_1, R_2[/math] эквивалентно разбиению всех классов с помощью [math]R, R_1, R_2[/math] по символу [math]a[/math].
Доказательство:
[math]\triangleright[/math]

Разобьем все классы с помощью [math]R [/math] и [math] R_1[/math] по символу [math]a[/math], тогда для любого класса [math]B[/math] из текущего разбиения выполняется

[math]\forall r \in B \,\,\, \delta(r, a) \in R[/math] and [math] \delta(r, a) \in R_1[/math] or
[math]\forall r \in B \,\,\, \delta(r, a) \in R[/math] and [math] \delta(r, a) \notin R_1[/math] or
[math]\forall r \in B \,\,\, \delta(r, a) \notin R[/math] and [math] \delta(r, a) \notin R_1[/math]

А так как [math]R = R_1 \cup R_2[/math] и [math]R_1 \cap R_2 = \varnothing[/math] то выполняется

[math]\forall r \in B \,\,\, \delta(r, a) \in R_2 [/math] or
[math] \forall r \in B \,\,\, \delta(r, a) \notin R_2[/math]

Из этого следует, что разбиение всех классов с помощью [math]R_2[/math] никак не повлияет на текущее разбиение.
Аналогично доказывается и для разбиения с помощью [math]R [/math] и [math] R_2[/math] по символу [math]a[/math].
Разобьем все классы с помощью [math]R_1[/math] и [math] R_2[/math] по символу [math]a[/math], тогда для любого класса [math]B[/math] из текущего разбиения выполняется

[math]\forall r \in B \,\,\, \delta(r, a) \in R_1[/math] and [math] \delta(r, a) \notin R_2[/math] or
[math]\forall r \in B \,\,\, \delta(r, a) \notin R_1[/math] and [math] \delta(r, a) \in R_2[/math] or
[math]\forall r \in B \,\,\, \delta(r, a) \notin R_1[/math] and [math] \delta(r, a) \notin R_2[/math]

А так как [math]R = R_1 \cup R_2[/math] и [math]R_1 \cap R_2 = \varnothing[/math] то выполняется

[math]\forall r \in B \,\,\, \delta(r, a) \in R [/math] or
[math] \forall r \in B \,\,\, \delta(r, a) \notin R[/math]
Из этого следует, что разбиение всех классов с помощью [math]R[/math] никак не повлияет на текущее разбиение.
[math]\triangleleft[/math]

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь. Если класс [math]R[/math] уже есть в очереди, то согласно лемме можно просто заменить его на [math]R_1[/math] и [math]R_2[/math]. Если класса [math]R[/math] нет в очереди, то согласно лемме в очередь можно добавить класс [math]R[/math] и любой из [math]R_1[/math] и [math]R_2[/math], а так как для любого класса [math]B[/math] из текущего разбиения выполняется

[math]\forall r \in B \,\,\, \delta(r, a) \in R [/math] or
[math] \forall r \in B \,\,\, \delta(r, a) \notin R[/math]

то в очередь можно добавить только меньшее из [math]R_1[/math] и [math]R_2[/math].

Псевдокод

[math]Q[/math] — множество состояний ДКА. [math]F[/math] — множество терминальных состояний. [math]W[/math] — очередь. [math]P[/math] — разбиение множества состояний ДКА. [math]R[/math] — класс состояний ДКА.

 [math]P \leftarrow \{ F, Q \setminus F \}[/math]
 [math]W \leftarrow \{ \}[/math]
 for all [math]a \in \Sigma[/math]
   [math]W[/math].push(min([math]F, Q \setminus F[/math]), [math]a[/math])
 while not [math]W[/math].isEmpty() 
   [math]W[/math].pop([math]S, a[/math])
   for each [math]R[/math] in [math]P[/math] split by [math](S, a)[/math]  
     replace [math]R[/math] in [math]P[/math] with [math]R_1[/math] and [math]R_2[/math]
     if ([math]R, a[/math]) in [math]W[/math]
       replace ([math]R, a[/math]) in [math]W[/math] with ([math]R_1, a[/math]) and ([math]R_2, a[/math])
     else
       if [math] |R_1| \le |R_2|[/math]
         [math]W[/math].push([math]R_1, a[/math])
       else
         [math]W[/math].push([math]R_2, a[/math])

Время работы

Время работы модифицированного алгоритма оценивается как [math]O(|\Sigma| \cdot n\log{n})[/math], где [math] n [/math] — количество состояний ДКА, а [math] \Sigma [/math]— алфавит. В данном случае при последующем разбиении в очередь будет добавлен класс [math]S_1[/math], причем [math]|S| \ge 2|S_1|[/math]. Каждый переход в автомате будет просмотрен не более, чем [math]O(\log{n})[/math] раз, ребер всего [math]O(|\Sigma| \cdot n)[/math], отсюда указанная оценка.

Литература

  • Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — М.: Издательский дом «Вильямс», 2002. — С. 177 — ISBN 5-8459-0261-4 (рус.)
  • D. Gries. Describing an algorithm by Hopcroft. Technical Report TR-72-151, Cornell University, December 1972.