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

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

Задача:

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

Алгоритм

Описание

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

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

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

[math]mFA = \operatorname {det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))[/math], где

• [math]FA[/math] это исходный КА,
• [math]\operatorname{rev}[/math] это процедура обращения КА,
• [math]\operatorname{det}[/math] это процедура детерминизации КА,
• [math]mFA[/math] это минимизированный КА.

Корректность

an automation is deterministic if and only if the left languages of its states are pairwise disjoint

if A recognizes the language L then r(A) recognizes the language r(L)

if the left (resp. right) language of the state q in A is L_g(q)(resp. L_d(q)), then its left (resp. right) language in r(A) is L_d(q) (resp. L_g(q))

The right languages if a state q` if d(A) is equal to the union of the right languages of the states q of A belonging to the subset q`

A (deterministic, complete, accessible) automation is minimal if and only if the right languages of its states are all different

Пример работы

1. Исходный НКА ([math]FA[/math]):
   
2. Первый шаг алгоритма ([math]\operatorname{rev}(FA)[/math]):
   
3. Второй шаг алгоритма ([math]\operatorname{det}(\operatorname{rev}(FA))[/math]):
   
   [math]\operatorname{det}[/math] переименовывает состояния, после этого [math]0[/math] всегда является начальным состоянием
4. Третий шаг алгоритма ([math]\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA)))[/math]):
   
   После выполнения этого шага алгоритма оба состояния [math]2[/math] и [math]3[/math] являются начальными.
5. Заключительный шаг алгоритма ([math]\operatorname{det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))[/math]):
   

Заключение

Самым эффективным алгоритмом минимизации принято считать алгоритм Хопкрофта, который, как и прочие традиционные алгоритмы, работает только с ДКА. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и алгоритм Хопкрофта. В работе, сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.

См. также

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

Источники информации

1. Алгоритм Бржозовского для минимизации конечного автомата