Викиконспекты - Вклад участника [ru]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:43:19Z

Glukos: /* Время работы алгоритмов */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случае с простым алгоритмом при последующем разбиении класса <tex>S</tex> в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>, отсюда получаем время работы <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:43:05Z

Glukos: /* Время работы алгоритмов */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при последующем разбиении класса <tex>S</tex> в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>, отсюда получаем время работы <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:42:32Z

Glukos: /* Время работы алгоритмов */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при последующем разбиении в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>, отсюда получаем время работы <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:41:31Z

Glukos: /* Время работы алгоритмов */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, поэтому каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при последующем разбиении в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>. Поэтому, его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:40:31Z

Glukos: /* Время работы алгоритмов */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при последующем разбиении в очередь добавляется два класса <tex>S_1</tex> и <tex>S_2</tex>, причем можно гарантировать лишь следующее уменьшение размера: <tex>|S| \ge |S_i| + 1</tex>. Поэтому, его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:35:48Z

Glukos: /* Время работы алгоритмов */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при последующем разбиении можно гарантировать лишь <tex>|S| \ge |S_1| + 1</tex>, поэтому его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:34:10Z

Glukos:

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритмов==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовался в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при разбиении можно гарантировать лишь <tex>|S| \ge |S_1| + 1</tex>, поэтому его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:33:29Z

Glukos: /* Время работы простого и модифицированного алгоритма */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы простого и модифицированного алгоритма==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовася в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку. 
В случаем с простым алгоритмом при разбиении можно гарантировать лишь <tex>|S| \ge |S_1| + 1</tex>, поэтому его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:33:09Z

Glukos: /* Время работы алгоритма */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы простого и модифицированного алгоритма==
Время работы модифицированного алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовася в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку.
В случаем с простым алгоритмом при разбиении можно гарантировать лишь <tex>|S| \ge |S_1| + 1</tex>, поэтому его время работы оценивается как <tex>O(|\Sigma| * n^2)</tex>.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:22:37Z

Glukos: /* Время работы алгоритма */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритма==
Время работы алгоритма оценивается как <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что если пара <tex>(S, a)</tex> попала в очередь, и класс <tex>S</tex> использовася в качестве сплиттера, то при последующем разбиении этого класса в очередь будет добавлен класс <tex>S_1</tex>, причем <tex>|S| \ge 2|S_1|</tex>. Каждое состояние изначально принадлежит лишь одному классу в очереди, тогда из вышеуказанного следует, что каждый переход в автомате будет просмотрен не более, чем <tex>O(\log{n})</tex> раз. Учитывая, что ребер всего <tex>O(|\Sigma| * n)</tex>, получаем указанную оценку.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T15:03:06Z

Glukos: /* Псевдокод */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ \}</tex>
if <tex> |F| \le |Q \setminus F|</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
else
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if (<tex>R, a</tex>) in <tex>W</tex>
replace (<tex>R, a</tex>) in <tex>W</tex> with (<tex>R_1, a</tex>) and (<tex>R_2, a</tex>)
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1, a</tex>)
else
<tex>W</tex>.push(<tex>R_2, a</tex>)

==Время работы алгоритма==
Время работы алгоритма равно <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что каждое из ребер, а их порядка <tex> |\Sigma| * n </tex>, участвует не более чем в <tex> \log{n}</tex> разбиениях.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T14:54:30Z

Glukos: /* Псевдокод */

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
<tex>W \leftarrow \{ \}</tex>
for all <tex>a \in \Sigma</tex>
<tex>W</tex>.push(<tex>F, a</tex>)
<tex>W</tex>.push(<tex>Q \setminus F, a</tex>)
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S, a</tex>)
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
if <tex> |F| \le |Q \setminus F|</tex>
<tex>W</tex>.push(<tex>F</tex>)
else
<tex>W</tex>.push(<tex>Q \setminus F</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S</tex>)
for all <tex>a \in \Sigma</tex>
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if <tex>R</tex> in <tex>W</tex>
replace <tex>R</tex> in <tex>W</tex> with <tex>R_1</tex> and <tex>R_2</tex>
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
else
<tex>W</tex>.push(<tex>R_2</tex>)
==Время работы алгоритма==
Время работы алгоритма равно <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что каждое из ребер, а их порядка <tex> |\Sigma| * n </tex>, участвует не более чем в <tex> \log{n}</tex> разбиениях.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))

2013-01-15T14:45:42Z

Glukos:

Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.

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

== Простой алгоритм ==
{{Определение
|definition =
Класс <tex>S</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_2 \,\,\, \delta(r, a) \notin S</tex>
}}
Если класс <tex>R</tex> может быть разбит по символу <tex>a</tex>, то он содержит хотя бы одну пару неэквивалентных состояний (так как существует строка которая их различает). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.

Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний <tex>Q \setminus F</tex>.
# Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.
# Из очереди извлекается пара <tex>(S, a)</tex>, <tex>S</tex> далее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.5.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
<tex>W \leftarrow \{ F, Q \setminus F \}</tex>
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S</tex>)
for all <tex>a \in \Sigma</tex>
for all <tex>R</tex> in <tex>P</tex>
<tex>R_1 = R \cap \delta^{-1} (S, a) </tex>
<tex>R_2 = R \setminus R_1</tex>
if <tex> |R_1| \ne 0</tex> and <tex>|R_2| \ne 0</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
<tex>W</tex>.push(<tex>R_2</tex>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.

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

{{Лемма
|statement = Класс <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex>, тогда разбиение всех классов (текущее разбиение) по символу <tex>a</tex> любыми двумя классами из <tex>R, R_1, R_2</tex> эквивалентно разбиению всех классов с помощью <tex>R, R_1, R_2</tex> по символу <tex>a</tex>.
|proof =
Разобьем все классы с помощью <tex>R </tex> и <tex> R_1</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \in R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R</tex> and <tex> \delta(r, a) \notin R_1</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R</tex> and <tex> \delta(r, a) \notin R_1</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_2 </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R_2</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R_2</tex> никак не повлияет на текущее разбиение. 
Аналогично доказывается и для разбиения с помощью <tex>R </tex> и <tex> R_2</tex> по символу <tex>a</tex>. 
Разобьем все классы с помощью <tex>R_1</tex> и <tex> R_2</tex> по символу <tex>a</tex>, тогда для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R_1</tex> and <tex> \delta(r, a) \notin R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \in R_2</tex> or
:<tex>\forall r \in B \,\,\, \delta(r, a) \notin R_1</tex> and <tex> \delta(r, a) \notin R_2</tex>
А так как <tex>R = R_1 \cup R_2</tex> и <tex>R_1 \cap R_2 = \varnothing</tex> то выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
Из этого следует, что разбиение всех классов с помощью <tex>R</tex> никак не повлияет на текущее разбиение.
}}

Алгоритм Хопкрофта отличается от простого тем, что иначе добавляет классы в очередь.
Если класс <tex>R</tex> уже есть в очереди, то согласно лемме можно просто заменить его на <tex>R_1</tex> и <tex>R_2</tex>.
Если класса <tex>R</tex> нет в очереди, то согласно лемме в очередь можно добавить класс <tex>R</tex> и любой из <tex>R_1</tex> и <tex>R_2</tex>, а так как для любого класса <tex>B</tex> из текущего разбиения выполняется
:<tex>\forall r \in B \,\,\, \delta(r, a) \in R </tex> or
:<tex> \forall r \in B \,\,\, \delta(r, a) \notin R</tex>
то в очередь можно добавить только меньшее из <tex>R_1</tex> и <tex>R_2</tex>.

===Псевдокод===
<tex>Q</tex> {{---}} множество состояний ДКА.
<tex>F</tex> {{---}} множество терминальных состояний.
<tex>W</tex> {{---}} очередь.
<tex>P</tex> {{---}} разбиение множества состояний ДКА.
<tex>R</tex> {{---}} класс состояний ДКА.
if <tex> |F| \le |Q \setminus F|</tex>
<tex>W</tex>.push(<tex>F</tex>)
else
<tex>W</tex>.push(<tex>Q \setminus F</tex>)
<tex>P \leftarrow \{ F, Q \setminus F \}</tex>
while not <tex>W</tex>.isEmpty()
<tex>W</tex>.pop(<tex>S</tex>)
for all <tex>a \in \Sigma</tex>
for each <tex>R</tex> in <tex>P</tex> split by <tex>S</tex>
replace <tex>R</tex> in <tex>P</tex> with <tex>R_1</tex> and <tex>R_2</tex>
if <tex>R</tex> in <tex>W</tex>
replace <tex>R</tex> in <tex>W</tex> with <tex>R_1</tex> and <tex>R_2</tex>
else
if <tex> |R_1| \le |R_2|</tex>
<tex>W</tex>.push(<tex>R_1</tex>)
else
<tex>W</tex>.push(<tex>R_2</tex>)
==Время работы алгоритма==
Время работы алгоритма равно <tex>O(|\Sigma| * n\log{n})</tex>, где <tex> n </tex> {{---}} количество состояний ДКА, а <tex> \Sigma </tex>{{---}} алфавит. Это следует из того, что каждое из ребер, а их порядка <tex> |\Sigma| * n </tex>, участвует не более чем в <tex> \log{n}</tex> разбиениях.

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

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Эквивалентность состояний ДКА

2013-01-15T12:38:32Z

Glukos: /* Проверка ДКА на эквивалентность */

{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
}}

{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</tex>, если
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.
}}

{{Определение
|definition = Два состояния <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.
}}

Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.

{{Лемма
|statement =
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.
|proof =
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex>
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}

=== Пример ===
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]

Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

== Проверка ДКА на эквивалентность ==
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними: 
[[Файл:auto_equiq.png|470px]] 
Осталось лишь проверить на эквивалентность состояния <tex> s_1 </tex> и <tex> s_2 </tex> в полученном автомате. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности.

Эквивалентность состояний ДКА

2013-01-15T12:37:16Z

Glukos: /* Проверка ДКА на эквивалентность */

{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
}}

{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</tex>, если
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.
}}

{{Определение
|definition = Два состояния <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.
}}

Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.

{{Лемма
|statement =
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.
|proof =
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex>
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}

=== Пример ===
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]

Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

== Проверка ДКА на эквивалентность ==
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними: 
[[Файл:auto_equiq.png|470px]] 
Осталось лишь проверить в полученном автомате состояния <tex> s_1 </tex> и <tex> s_2 </tex> на эквивалентность. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния на классы эквивалентности.

Эквивалентность состояний ДКА

2013-01-15T12:36:39Z

Glukos: /* Проверка ДКА на эквивалентность */

{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
}}

{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</tex>, если
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.
}}

{{Определение
|definition = Два состояния <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.
}}

Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.

{{Лемма
|statement =
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.
|proof =
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex>
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}

=== Пример ===
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]

Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

== Проверка ДКА на эквивалентность ==
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними: 
[[Файл:auto_equiq.png|470px]] 
Осталось лишь проверить в полученном автомате состояния <tex> s_1 </tex> и <tex> s_2 </tex> на эквивалентность. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>. Для этого можно применить [[Минимизация_ДКА,_алгоритм_за_O(n%5E2)_с_построением_пар_различимых_состояний|алгоритм минимизации ДКА]], который разбивает все состояния автомата на классы эквивалентности.

Эквивалентность состояний ДКА

2013-01-15T12:30:33Z

Glukos: /* Проверка ДКА на эквивалентность */

{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
}}

{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</tex>, если
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.
}}

{{Определение
|definition = Два состояния <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.
}}

Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.

{{Лемма
|statement =
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.
|proof =
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex>
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}

=== Пример ===
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]

Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

== Проверка ДКА на эквивалентность ==
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними: 
[[Файл:auto_equiq.png|470px]] 
Осталось лишь проверить в полученном автомате состояния <tex> s_1 </tex> и <tex> s_2 </tex> на эквивалентность. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>.

Эквивалентность состояний ДКА

2013-01-15T12:30:10Z

Glukos: /* Проверка ДКА на эквивалентность */

{{Определение
|definition = Два автомата <tex> \mathcal{A}_1 = \langle Q_1,\Sigma,\delta_1,s_{1}, T_1\subseteq Q_1 \rangle </tex> и <tex>\mathcal{A}_2 = \langle Q_2,\Sigma,\delta_2,s_{2}, T_2\subseteq Q_2 \rangle </tex> называются '''эквивалентными''', если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>, то есть <tex>\mathcal{L}(\mathcal{A}_1) = \mathcal{L}(\mathcal{A}_2)</tex>.
}}

{{Определение
|definition = Слово <tex>z \in \Sigma^*</tex> '''различает''' два состояния <tex>q_i</tex> и <tex>q_j</tex>, если
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \notin T \Leftrightarrow t_2 \in T) </tex>.
}}

{{Определение
|definition = Два состояния <tex>q_i</tex> и <tex>q_j</tex> называются '''эквивалентными''' <tex>(q_i \sim q_j)</tex>, если не существует строки, которая их различает, то есть <tex>\forall z \in \Sigma^*</tex> верно, что
* <tex> \langle q_i, z \rangle \vdash^* \langle t_1, \varepsilon \rangle, \langle q_j, z \rangle \vdash^* \langle t_2, \varepsilon \rangle \Rightarrow (t_1 \in T \Leftrightarrow t_2 \in T) </tex>.
}}

Заметим, что эквивалентность состояний действительно является [[Отношение эквивалентности|отношением эквивалентности]]. Так как <tex> \Leftrightarrow </tex> (равносильность) является отношением эквивалентности и в детерминированном автомате всегда существует путь по любому слову, описанное нами отношение является отношением эквивалентности.

{{Лемма
|statement =
<tex> \mathcal{A} = \langle Q, \Sigma, \delta, s, T \rangle </tex>, <tex> p_1, p_2, q_1, q_2 \in Q </tex>, <tex> q_i = \delta(p_i, c) </tex>, <tex> w \in \Sigma^*</tex> различает <tex> q_1 </tex> и <tex> q_2 </tex>. Тогда <tex>cw</tex> различает <tex> p_1 </tex> и <tex> p_2 </tex>.
|proof =
<tex> \langle p_i, cw \rangle \vdash \langle q_i, w \rangle \vdash^* \langle t_i, \varepsilon \rangle </tex>
А значит, по условию различимости для <tex> q_1 </tex> и <tex> q_2</tex> , <tex> t_1 \in T \Leftrightarrow t_2 \notin T </tex>
}}

=== Пример ===
[[Файл:avtomat2.png|350px]] [[Файл:avtomat3.png|350px]]

Эти два автомата принимают слова из языка слов длины не меньше одного, состоящих из символов алфавита <tex> \lbrace 0, 1\rbrace </tex>. Стартовые и все допускающие состояния автоматов эквивалентны между собой.

[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

== Проверка ДКА на эквивалентность ==
Заданы два автомата: <tex> \mathcal{A}_1 </tex> со стартовым состоянием <tex> s_1 </tex> и <tex> \mathcal{A}_2 </tex> со стартовым состоянием <tex> s_2 </tex> соответственно. Нужно проверить их на эквивалентность.
Для этого построим автомат <tex> \mathcal{A} </tex>, содержащий все состояния обоих автоматов и изначальные переходы между ними: 
[[Файл:auto_equiq.png|400px]] 
Осталось лишь проверить в полученном автомате состояния <tex> s_1 </tex> и <tex> s_2 </tex> на эквивалентность. Их эквивалентность совпадает с эквивалентностью автоматов <tex> \mathcal{A}_1 </tex> и <tex> \mathcal{A}_2 </tex>.

Glukos:

{{В разработке}}
Пусть задано множество точек <tex>S</tex> из евклидового пространства. Пусть область <tex>R \subset S</tex> такова, что её границы ортогональны координатным осям пространства. Требуется определить множество точек <tex>S' \subset S</tex>, лежащих в области <tex>R</tex>.
== Одномерный случай ==

Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из точек лежат на этом отрезке.

[[Файл:Line_with_dots_and_segment.png‎]] 
Задача тривиальна — нужно оставить только те точки, которые находятся между началом и концом отрезка.

На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.

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

Рассмотрим на примере:

[[Файл:Upper_bound_and_lower_bound2.png|600px]]

Код реализации:

template<class RauIter, class OutIter, class Scalar> OutIter range_search(RauIter p, RauIter q, OutIter out)
{
return std::copy(lower_bound(p, q, l), upper_bound(p, q, r), out);
}

Алгоритм работает за <tex>O(\log n)</tex>.

== Двумерный случай ==

Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.

Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. Рассмотрим на примере: 
[[Файл:ortog_search_tree.png|600px]] 
Рассмотрим, как в такой структуре данных будет выглядеть поиск множества точек, находящихся в заданном прямоугольнике <tex>[x_{min}, x_{max}] \times [y_{min}, y_{max}]</tex>. Для начала, найдем в дереве те точки, <tex>x</tex>-координата которых лежит в интервале <tex>[x_{min}, x_{max}]</tex>. Сделаем это следующим образом:
# Найдем в дереве поиска вершины с минимальной и максимальной <tex>x</tex>-координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как <tex>v_l</tex> и <tex>v_r</tex>.
# Добавим в искомое множество их наименьшего общего предка <tex>v_n</tex>.
# Для каждой из промежуточных вершин <tex>v_i</tex> на восходящем пути <tex>v_l \to v_n</tex> зафиксируем, из какого ребенка мы поднялись в вершину <tex>v_i</tex>. Если мы поднялись из левого сына, то добавим в искомое множество саму вершину <tex>v_i</tex>, а также множество точек, находящихся в поддереве правого сына вершины <tex>v_i</tex>. Если же мы поднялись из правого сына, то не добавляем ничего.
# Повторим процесс для пути <tex>v_r \to v_n</tex>. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.
Пример процесса показан на иллюстрации: 
[[Файл:ortog_search_tree2.png|700px]] 
В итоге, в множество мы добавим <tex>O(\log n)</tex> вершин и <tex>O(\log n)</tex> поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, <tex>y</tex>-координата которых не лежит в интервале <tex>[y_{min}, y_{max}]</tex>. Для точек это сделать просто — нужно вручную проверить, лежит ли <tex>y</tex>-координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
 Каждая из функций <tex>range{\_}search(y_{min}, y_{max})</tex> будет работать в худшем случае за <tex>O(\log n)</tex>, отсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>. Что касается памяти, то в сбалансированном дереве поиска <tex>O(\log n)</tex> слоев, а каждый слой хранит массивы, содержащие в сумме ровно <tex>n</tex> точек, соответственно вся структура в целом занимает <tex>O(n\log n)</tex> памяти.

== Обобщение для p-мерного пространства ==

Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из <tex>p</tex>-мерного пространства, каждая из которых представляется как <tex>n</tex> координатных чисел: <tex>(\xi_1, \xi_2, ... , \xi_p)</tex>. Тогда, строя дерево поиска по координате <tex>\xi_i</tex>, в каждой вершине будем хранить другое дерево поиска с ключом <tex>\xi_{i+1}</tex>, составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате <tex>\xi_{p-1}</tex>, уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату <tex>\xi_{p}</tex> дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на <tex>\log n</tex>. Отсюда, получаем оценку <tex>O(\log^{p} n)</tex> на время запроса и <tex>O(n\log^{p-1} n)</tex> на занимаемую память.

Такой же результат можно получить с помощью [[Сжатое многомерное дерево отрезков|сжатого многомерного дерева отрезков]].

== Ускорение запроса ==
Для ускорения запроса можно "прошить" дерево поиска по предпоследней координате, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <tex>(x, y)</tex> массива-предка соединим с элементами <tex>upper\_bound(y)</tex> и <tex>lower\_bound(y)</tex> каждого массива-ребенка. Ниже представлен пример соединения корня с его левым сыном: [[Файл:ortog_search_tree3.png]] Для выполнения завершающей фазы поиска нам достаточно будет посчитать <tex>upper\_bound()</tex> и <tex>lower\_bound()</tex> только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам. Заметим, что все вершины, к массивам которых нужно перейти, смежны с какой-либо из вершин путей <tex>v_l \to v_n</tex> или <tex>v_r \to v_n</tex>. Отсюда следует, что число спусков оценивается как <tex>O(length(v_l \to v_n) + length(v_r \to v_n)) = O(\log n)</tex>. Таким образом, поиск теперь будет выполняться за <tex>O(\log^{p-1} n)</tex>, где <tex>p</tex> — размерность пространства.

Ортогональный поиск

2012-06-07T05:04:42Z

Glukos: /* Одномерный случай */

{{В разработке}}
== Одномерный случай ==

Пусть дана прямая с точками на ней и отрезок. Необходимо указать, какие из точек лежат на этом отрезке.

[[Файл:Line_with_dots_and_segment.png‎]] 
Задача тривиальна — нужно оставить только те точки, которые находятся между началом и концом отрезка.

На практике для быстрого осуществления запроса нужно хранить точки в отсортированном массиве и пользоваться двоичным поиском. В C++ данная задача решается с помощью функций из STL - upper_bound и lower_bound.

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

Рассмотрим на примере:

[[Файл:Upper_bound_and_lower_bound2.png|600px]]

Код реализации:

template<class RauIter, class OutIter, class Scalar> OutIter range_search(RauIter p, RauIter q, OutIter out)
{
return std::copy(lower_bound(p, q, l), upper_bound(p, q, r), out);
}

Алгоритм работает за <tex>O(\log n)</tex>.

== Двумерный случай ==

Пусть дано некоторое множество точек на плоскости. Нам необходимо ответить, какие именно из них лежат в некотором заданном прямоугольнике.

Для этого возьмем любое сбалансированное дерево поиска и наполним его точками <tex>(x, y)</tex> из множества. В качестве ключа будет использоваться <tex>x</tex>-координата точки. Теперь модернизируем дерево: в каждой вершине дерева будем хранить отсортированный по <tex>y</tex>-координате массив точек, которые содержатся в соответствующем поддереве. Рассмотрим на примере: 
[[Файл:ortog_search_tree.png|600px]] 
Рассмотрим, как в такой структуре данных будет выглядеть поиск множества точек, находящихся в заданном прямоугольнике <tex>[x_{min}, x_{max}] \times [y_{min}, y_{max}]</tex>. Для начала, найдем в дереве те точки, <tex>x</tex>-координата которых лежит в интервале <tex>[x_{min}, x_{max}]</tex>. Сделаем это следующим образом:
# Найдем в дереве поиска вершины с минимальной и максимальной <tex>x</tex>-координатой из прямоугольника запроса, добавим их в искомое множество, обозначим их как <tex>v_l</tex> и <tex>v_r</tex>.
# Добавим в искомое множество их наименьшего общего предка <tex>v_n</tex>.
# Для каждой из промежуточных вершин <tex>v_i</tex> на восходящем пути <tex>v_l \to v_n</tex> зафиксируем, из какого ребенка мы поднялись в вершину <tex>v_i</tex>. Если мы поднялись из левого сына, то добавим в искомое множество саму вершину <tex>v_i</tex>, а также множество точек, находящихся в поддереве правого сына вершины <tex>v_i</tex>. Если же мы поднялись из правого сына, то не добавляем ничего.
# Повторим процесс для пути <tex>v_r \to v_n</tex>. Здесь ориентация сторон инвертирована: будем пополнять множество в том случае, если мы поднялись из правого сына.
Пример процесса показан на иллюстрации: 
[[Файл:ortog_search_tree2.png|700px]] 
В итоге, в множество мы добавим <tex>O(\log n)</tex> вершин и <tex>O(\log n)</tex> поддеревьев дерева поиска. Теперь нужно просеять полученное множество — извлечь из него те элементы, <tex>y</tex>-координата которых не лежит в интервале <tex>[y_{min}, y_{max}]</tex>. Для точек это сделать просто — нужно вручную проверить, лежит ли <tex>y</tex>-координата в нужном интервале. Для каждого из полученных поддеревьев обратимся к массиву содержащихся в нем точек и запустим от него приведенную выше функцию <tex>range{\_}search(y_{min}, y_{max})</tex>. Все полученные таким образом точки и будут составлять ответ.
 Каждая из функций <tex>range{\_}search(y_{min}, y_{max})</tex> будет работать в худшем случае за <tex>O(\log n)</tex>, отсюда получаем итоговое время выполнения запроса <tex>O(\log^2 n)</tex>. Что касается памяти, то в сбалансированном дереве поиска <tex>O(\log n)</tex> слоев, а каждый слой хранит массивы, содержащие в сумме ровно <tex>n</tex> точек, соответственно вся структура в целом занимает <tex>O(n\log n)</tex> памяти.

== Обобщение для p-мерного пространства ==

Такую структуру данных можно при необходимости обобщить на случай большей размерности. Пусть у нас есть множество точек из <tex>p</tex>-мерного пространства, каждая из которых представляется как <tex>n</tex> координатных чисел: <tex>(\xi_1, \xi_2, ... , \xi_p)</tex>. Тогда, строя дерево поиска по координате <tex>\xi_i</tex>, в каждой вершине будем хранить другое дерево поиска с ключом <tex>\xi_{i+1}</tex>, составленное из точек, лежащих в соответствующем поддереве. В дереве поиска, составленном по предпоследней координате <tex>\xi_{p-1}</tex>, уже не будет необходимости хранить в каждой вершине целое дерево, поскольку при переходе на последнюю координату <tex>\xi_{p}</tex> дальнейший поиск производиться не будет, поэтому в вершинах будем хранить массивы, так же, как и в двумерном случае. Оценим занимаемую память и время запроса: при добавлении следующей координаты асимптотика обеих величин умножается на <tex>\log n</tex>. Отсюда, получаем оценку <tex>O(\log^{p} n)</tex> на время запроса и <tex>O(n\log^{p-1} n)</tex> на занимаемую память.

Такой же результат можно получить с помощью [[Сжатое многомерное дерево отрезков|сжатого многомерного дерева отрезков]].

== Ускорение запроса ==
Для ускорения запроса можно "прошить" дерево поиска по предпоследней координате, а именно: каждый элемент массива, сохраненного в какой-либо вершине, соединить с элементами массивов, сохраненных в вершинах-детях. Соединять будем по следующему принципу: элемент <tex>(x, y)</tex> массива-предка соединим с элементами <tex>upper\_bound(y)</tex> и <tex>lower\_bound(y)</tex> каждого массива-ребенка. Ниже представлен пример соединения корня с его левым сыном: [[Файл:ortog_search_tree3.png]] Для выполнения завершающей фазы поиска нам достаточно будет посчитать <tex>upper\_bound()</tex> и <tex>lower\_bound()</tex> только на массиве, привязанному к корню дерева. Для получения границ на других массивах можно будет просто спуститься по ссылкам. Заметим, что все вершины, к массивам которых нужно перейти, смежны с какой-либо из вершин путей <tex>v_l \to v_n</tex> или <tex>v_r \to v_n</tex>. Отсюда следует, что число спусков оценивается как <tex>O(length(v_l \to v_n) + length(v_r \to v_n)) = O(\log n)</tex>. Таким образом, поиск теперь будет выполняться за <tex>O(\log^{p-1} n)</tex>, где <tex>p</tex> — размерность пространства.