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

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Задача:

Пусть дан автомат [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}[/math], в котором [math]q[/math] является уникальным начальным состоянием.

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

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Обратное слово (англ. reverse of the word) [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].

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

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

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

Обратный автомат (англ. reverse of the automaton) для автомата [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[/math] автомата [math]\mathcal{A}[/math], принадлежащих множеству [math]q'[/math].

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

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

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

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Алгоритм

Описание

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

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

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

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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

Заключение

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

См. также

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

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

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