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

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

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

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

Алгоритмы

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

Пусть [math]\displaystyle{ \mathcal A }[/math] — ДКА. Обозначим через [math]\displaystyle{ r(\mathcal A) }[/math] инвертированный автомат [math]\displaystyle{ \mathcal A }[/math]. Через [math]\displaystyle{ d(\mathcal A) }[/math] обозначим детерминизированный автомат, полученный из [math]\displaystyle{ \mathcal A }[/math] процедурой построения подмножеств. Имеет место следующий результат:

Пусть автомат [math]\displaystyle{ \mathcal A }[/math] распознаёт язык [math]\displaystyle{ L }[/math]. Тогда минимальный ДКА для языка [math]\displaystyle{ L }[/math] может быть найден как [math]\displaystyle{ \mathcal A_L = drdr(\mathcal A). }[/math]

См. также

• Конечный автомат
• Минимальная форма автомата
• Суффиксный автомат

Литература

• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to automata theory, languages, and computation, 2nd edition // ACM SIGACT News. — 2001-03-01. — Т. 32, вып. 1. — С. 60. — ISSN 0163-5700. — doi:10.1145/568438.568455.

Ссылки

• Алгоритм Бржозовского // Викиконспекты Университета ИТМО
• Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) // Викиконспекты Университета ИТМО