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

Задача:

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

Описание

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

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

Правым языком (англ. right language) называется язык $L_d(q)$, распознаваемый автоматом $\mathcal{A}$, в котором $q$ является уникальным начальным состоянием.

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

Левым языком (англ. left language) называется язык $L_g(q)$, распознаваемый автоматом $\mathcal{A}$, в котором $q$ является уникальным терминальным состоянием.

Таким образом, допустимые слова языка $L$, проходящие через состояние $q$, фактически разделяются на два языка, а соединение соответствующих слов этих языков по всем состояниям даст исходный язык $L$.
Рассмотрим слово $y$ из левого языка $L_g(q)$. Тогда множество слов $L_d(q)$ — правый контекст слова $y$ в языке $L$. Аналогично для правого языка и левого контекста.

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

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

$\triangleright$

Рассмотрим состояния $q$ и $q'$ ($q \neq q'$) в ДКА. Пусть левые языки этих состояний пересекаются, то есть $L_g(q) \cap L_g(q') = \{ w \}$. По окончании процесса допуска слова $w$ мы оказываемся в состоянии $q$ или $q'$. Следовательно, из какого-то состояния на пути в терминальное существует несколько различных переходов по одному из символов $w$, а значит $\mathcal{A}$ — НКА. Получаем противоречие.

$\triangleleft$

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

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

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

Обратный язык (англ. reverse of the language) для языка $L$ — язык $r(L) = \{ u \mid r(u) \in L \}$.

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

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

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

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

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

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

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

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

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

Правый язык состояния $q'$ $d(\mathcal{A})$ эквивалентен объединению правых языков состояний $q$ автомата $\mathcal{A}$, принадлежащих множеству $q'$.

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

Левое отношение (англ. left quotient) регулярного языка $L$ для слова $u$ из $\Sigma^{*}$ — язык $u^{-1}L = \{ v \in X^{*} \mid uv \in L \}$.

Минимальный автомат $\mathcal{A}_{L}$ для регулярного языка $L$ определяется следующим образом:

• множество состояний — это множество левых отношений языка $L$,
• начальное состояние — $L$,
• терминальные состояния — множество отношений, содержащих пустое слово,
• функция перехода $\delta(u^{-1}L, x) = (ux)^{-1}L$.

Автомат $\mathcal{A}_L$ уникален с точностью до изоморфизма и имеет минимальное количество состояний.

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

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

$\triangleright$

Рассмотрим состояния $q$ и $q'$ ($q \neq q'$) в ДКА. Пусть их правые языки $L_d(q) = L_d(q')$. Тогда состояния $q$ и $q'$ можно объединить в одно. Если состояние $q$ недостижимо из начального состояния $s$, то его можно удалить из автомата — это никак не повлияет на язык $L$.

$\triangleleft$

Алгоритм

Описание

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

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

Введём следующие обозначения:

• $\mathcal{A}$ — конечный автомат,
• $d(\mathcal{A})$ — детерминизированный автомат для $\mathcal{A}$,
• $r(\mathcal{A})$ — обратный автомат для $\mathcal{A}$,
• $dr(\mathcal{A})$ — результат $d(r(\mathcal{A}))$. Аналогично для $rdr(\mathcal{A})$ и $drdr(\mathcal{A})$.

Теорема (Бржозовский, 1962):

Пусть $\mathcal{A}$ — автомат (необязательно детерминированный), распознающий язык $L$. Минимальный детерминированный автомат $\mathcal{A}_L$ может быть вычислен следующим образом: $\mathcal{A}_L = drdr(\mathcal{A})$.

Доказательство:

$\triangleright$

По построению автомат $drdr(\mathcal{A})$ детерминированный. Согласно утверждению 2, он распознает язык $L$. Покажем, что все правые языки $drdr(\mathcal{A})$ различны. Из утверждения 1, левые языки $dr(\mathcal{A})$ попарно не пересекаются. Из утверждения 3, правые языки $rdr(\mathcal{A})$ являются левыми языками $dr(\mathcal{A})$. Таким образом, они попарно не пересекаются. Согласно утверждению 4, правый язык $drdr(\mathcal{A})$ — объединение правых языков $rdr(\mathcal{A})$. Поскольку правые языки $rdr(\mathcal{A})$ попарно не пересекаются, все правые языки $drdr(\mathcal{A})$ различны. Так как все правые языки $drdr(\mathcal{A})$ различны, согласно утверждению 5 автомат $drdr(\mathcal{A})$ минимальный.

$\triangleleft$

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

1. Исходный НКА $\mathcal{A}$:
   
2. Первый шаг, $r(\mathcal{A})$:
   
3. Второй шаг, $dr(\mathcal{A})$:
   
   В детерминизированных автоматах состояния переименованы, так что $0$ всегда является начальным состоянием.
4. Третий шаг, $rdr(\mathcal{A})$:
   
   После выполнения этого шага алгоритма оба состояния $2$ и $3$ являются начальными.
5. Заключительный шаг, $drdr(\mathcal{A})$:
   

Заключение

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

См. также

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

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

• J.-M. Champarnaud, A. Khorsi, T. Paranthoen — Split and join for minimizing: Brzozowski's algorithm
• Пётр Советов — Алгоритм Бржозовского для минимизации конечного автомата