Изменения

Перейти к: навигация, поиск
Нет описания правки
= Постановка задачи =
Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.
 
= Минимизация ДКА =
Если в ДКА существуют два [[ Эквивалентность_состояний_ДКА | эквивалентных состояния]], то при их объединении мы получим [[ Эквивалентность_состояний_ДКА | эквивалентный ДКА]], так как распознаваемый язык не изменится. Основная идея минимизации состоит в разбиении множества состояний на классы эквивалентности, полученные классы и будут состояниями минимизированного ДКА.
 
= Простой алгоритм =
{{Определение
|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>a</tex>). Если класс нельзя разбить, то он состоит из эквивалентных состояний.
Поэтому самый простой алгоритм состоит в том, чтобы разбивать классы текущего разбиения до тех пор пока это возможно.
 
===Псевдокод===
<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>)
Когда очередь станет пустой будет получено разбиение на классы эквивалентности, так как больше ни один класс не может быть разбит.
= Алгоритм Хопкрофта=
Если в ДКА существуют два [[ Эквивалентность_состояний_ДКА | эквивалентных состояния]], то при их объединении мы получим [[ Эквивалентность_состояний_ДКА | эквивалентный ДКА]], так как распознаваемый язык не изменится. Основная идея   Алгорит Хопкрофта является улучшением простого алгоритма состоит в разбиении множества состояний на классы эквивалентности, полученные классы и будут состояниями минимизированного ДКА.
Итеративно строим разбиение множества состояний следующим образом.
Анонимный участник

Навигация