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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Минимизация ДКА — построение по детерминированному конечному автомату (ДКА) эквивалентного ДКА, имеющего наименьшее возможное число состояний.

Минимальный ДКА

[править | править код]

Для любого регулярного языка существует минимальный ДКА, который его принимает, то есть, ДКА с наименьшим возможным числом состояний. Такой автомат единственен с точностью до изоморфизма.

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

[править | править код]

1.     Разделить все состояния ДКА на две группы: группу конечных состояний и группу неконечных состояний.

2.     Для каждого символа алфавита, проверить, в какую из групп перейдет автомат из каждого состояния, используя данный символ. Если из состояний A и B можно перейти в состояния C и D соответственно, то состояния A и B будут считаться эквивалентными по данному символу, если состояния C и D принадлежат одной и той же группе.

3.     На основе этой информации разделить каждую группу на подгруппы, где состояния, эквивалентные по всем символам алфавита, находятся в одной подгруппе.

4.     Повторять шаги 2 и 3 до тех пор, пока группы перестанут разделяться.

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

6.     Удалить недостижимые состояния.

Алгоритм Бжозовского

[править | править код]

Пусть  — ДКА. Обозначим через инвертированный автомат . Через обозначим детерминизированный автомат, полученный из процедурой построения подмножеств. Имеет место следующий результат[1]:

Пусть автомат распознаёт язык . Тогда минимальный ДКА для языка может быть найден как

Примечания

[править | править код]
  1. Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Split and join for minimizing: Brzozowski's algorithm (англ.). undefined (2002). Дата обращения: 27 июля 2019. Архивировано 27 июля 2019 года.

Литература

[править | править код]