172
правки
Изменения
Нет описания правки
Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.
== Минимизация ДКА ==
Если в ДКА существуют два [[ Эквивалентность_состояний_ДКА | эквивалентных состояния]], то при их объединении мы получим [[ Эквивалентность_состояний_ДКА | эквивалентный ДКА]], так как распознаваемый язык не изменится. Основная идея минимизации состоит в разбиении множества состояний на классы эквивалентности, полученные классы и будут состояниями минимизированного ДКА.
== Простой алгоритм ==
{{Определение
|definition =
Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний <tex>Q</tex> и класс недопускающих состояний<tex>Q \setminus F</tex>.# Оба этих класса Перебираются символы алфавита <tex>a \in \Sigma</tex>, все пары <tex>(Q, a)</tex> и <tex>(Q \setminus F, a)</tex> помещаются в очередь.# Из очереди извлекается класс, далее именуемый как сплиттер.# Перебираются все символы из алфавита пара <tex>\Sigma(S, a)</tex>, где <tex>aS</tex> {{---}} текущий символдалее именуется как сплиттер.
# Все классы текущего разбиения разбиваются на 2 подкласса (один из которых может быть пустым). Первый состоит из состояний, которые по символу <tex>a</tex> переходят в сплиттер, а второй из всех оставшихся.
# Те классы, которые разбились на два непустых подкласса, заменяются этими подклассами в разбиении, а также добавляются в очередь.
# Пока очередь не пуста, выполняем п.3 – п.65.
===Псевдокод===
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс невозможно разбить.
== Алгоритм Хопкрофта==
{{Лемма
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.
