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

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

Минимальный ДКАПравить

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

АлгоритмыПравить

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

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

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

См. такжеПравить

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

ЛитератураПравить

• 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)) // Викиконспекты Университета ИТМО