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

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

Алгоритм

Описание

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

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

См. также

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