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

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

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

Минимальный ДКА[править | править код]

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

Алгоритмы[править | править код]

Алгоритм Хопкрофта[править | править код]

Алгоритм Бжозовского[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

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

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

Ссылки[править | править код]