Изменения

Перейти к: навигация, поиск
Нет описания правки
Пусть дан автомат, распознающий определенный язык. Требуется найти [[ Эквивалентность_состояний_ДКА | эквивалентный автомат]] с наименьшим количеством состояний.
= Минимизация ДКА Алгоритм Хопкрофта=Понятие Если в ДКА существуют два [[ Эквивалентность_состояний_ДКА | эквивалентности состоянийэквивалентных состояния]] позволяет объединить состояния в классы следующим образом.# Все состояния в классе эквивалентны.# Любые два состояния, выбранные из разных класовто при их объединении мы получим [[ Эквивалентность_состояний_ДКА | эквивалентный ДКА]], неэквивалентнытак как распознаваемый язык не изменится.Таким образом, основная Основная идея минимизации ДКА алгоритма состоит в разбиении множества состояний на классы эквивалентности.===Пример минимизации , полученные классы и будут состояниями минимизированного ДКА===[[Изображение:Automaton1.png]][[Изображение:Automaton2.png]]
Первый класс состоит из состояния <tex>A</tex>, а второй из эквивалентных состояний <tex>B</tex> и <tex>C</tex>.
= Алгоритм =
Итеративно строим разбиение множества состояний следующим образом.
# Первоначальное разбиение множества состояний {{---}} класс допускающих состояний и класс недопускающих состояний.
else
<tex>W</tex>.push(<tex>R_2</tex>)
=Корректность алгоритма=
==Время работы алгоритма==
Благодаря системе добавления классов состояний в очередь, каждое ребро будет рассмотрено не более чем <tex>\log{n}</tex> раз. А так как ребер у нас порядка <tex> |\Sigma| * n </tex> то получаем <tex> O(n\log{n})</tex>
= Литература =
Анонимный участник

Навигация