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

Задача:

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

Описание

Пусть [math]q[/math] — состояние автомата [math]\mathcal{A} = \langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle[/math].

Определение:

Правым языком (англ. right language) — называется язык [math]L_d(q)[/math], принимаемый автоматом [math]\mathcal{A}_{d}(q) = \langle \Sigma , Q , q , T , \delta \rangle[/math], полученным из [math]\mathcal{A}[/math] путём добавления уникального начального состояния [math]q[/math].

Определение:

Левым языком (англ. left language) — называется язык [math]L_g(q)[/math], принимаемый автоматом [math]\mathcal{A}_{g}(q) = \langle \Sigma , Q , q , T , \delta \rangle[/math], полученным из [math]\mathcal{A}[/math] путём добавления уникального терминального состояния [math]q[/math].

Утверждение (1):

Автомат является детерминированным тогда и только тогда, когда левые языки его состояний попарно не пересекаются.

Определение:

Обратное слово [math]r(u)[/math] для слова [math]u[/math] определяется следующим образом: [math]r(\varepsilon) = \varepsilon[/math] и если [math]u = u_1 u_2 u_3 \dotsc u_p[/math], тогда [math]r(u) = v_1 v_2 v_3 \dotsc v_p[/math], где [math]v_i = u_{p - i + 1}[/math].

Определение:

Обратный язык для языка [math]L[/math] — язык [math]r(L) = \{ u \mid r(u) \in L \}[/math].

Определение:

Обратный автомат для автомата [math]\mathcal{A} = \langle \Sigma , Q , S , T , \delta \rangle[/math] — автомат [math]r(\mathcal{A}) = \langle \Sigma , Q , T , I , r(\delta) \rangle[/math], полученный из [math]\mathcal{A}[/math] сменой местами начальных и конечных состояний и сменой направлений переходов.

Утверждение (2):

Если [math]\mathcal{A}[/math] распознает язык [math]L[/math], то [math]r(\mathcal{A})[/math] распознает [math]r(L)[/math].

Утверждение (3):

Если левый язык состояния [math]q[/math] в [math]\mathcal{A}[/math] — [math]L_g(q)[/math], тогда его левый язык в [math]r(A)[/math] — [math]L_d(q)[/math]. Аналогично для правого языка [math]q[/math].

Пусть [math]\mathcal{A} = \langle \Sigma , Q , I , T , \delta \rangle[/math] — НКА.
Тогда детерминированный автомат [math]d(\mathcal{A}) = \langle \Sigma , Q' , \{ i' \} , T' , \delta' \rangle[/math] определяется следующим образом:

• Детерминированному состоянию соответствует множество недетерминированных состояний: для каждого [math]q' \in Q'[/math] имеем [math]q' \subseteq Q[/math],
• Начальное состояние в [math]d(\mathcal{A})[/math] — множество из [math]I[/math] начальных состояний автомата [math]\mathcal{A}[/math],
• Состояние в детерминированном автомате является терминальным тогда и только тогда, когда оно содержится хотя бы в одном недетерминированном состоянии,
• Пусть [math]q'[/math] — состояние детерминированного автомата и [math]a[/math] – символ из [math]\Sigma[/math]. Если переход из [math]q'[/math] по символу [math]a[/math] определен, тогда, по построению: [math]\delta'(q', a) = \bigcup\limits_{q \in q'}{ \delta(q, a)}[/math].

Утверждение (4):

Правый язык состояния [math]q'[/math] [math]d(\mathcal{A})[/math] эквивалентен объединению правых языков состояний [math]q \mathcal{A}[/math], принадлежащих множеству [math]q'[/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] это минимизированный КА.

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

Корректность алгоритма доказана в работе

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

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))

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

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