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

Эта статья находится в разработке!

Задача:

Пусть дан автомат $\mathcal{A}$. Требуется построить автомат $\mathcal{A}_{min}$ с наименьшим количеством состояний, распознающий тот же язык, что и $\mathcal{A}$.

Алгоритм

Описание

Алгоритм минимизации конечных автоматов Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:

• Он элегантен и весьма оригинален.
• Он эффективен.
• Он работает даже с недетерминированными конечными автоматами.

Обладая обычными процедурами обращения $rev$ и детерминизации $det$ конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры:

$mFA = det(rev(det(rev(FA))))$, где

• $FA$ это исходный КА,
• $rev$ это процедура обращения КА,
• $det$ это процедура детерминизации КА,
• $mFA$ это минимизированный КА.

См. также

• Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
• Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))