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

2014-12-27T14:16:49Z

78.25.120.95:

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

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

* Он элегантен и весьма оригинален.
* Он эффективен.
* Он работает даже с [[Недетерминированные конечные автоматы|недетерминированными конечными автоматами]].

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

<tex>mFA = \operatorname {det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))</tex>, где

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

===Корректность===
[http://www.researchgate.net/publication/255626373_Split_and_join_for_minimizing__Brzozowski%27s_algorithm]

==Пример работы==
# Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>): [[Файл:Fa.png|Исходный НКА]]
# Первый шаг алгоритма (<tex>\operatorname{rev}(FA)</tex>): [[Файл:Rfa.png|Первый шаг]]
# Второй шаг алгоритма (<tex>\operatorname{det}(\operatorname{rev}(FA))</tex>): [[Файл:Drfa.png|Второй шаг]] <tex>\operatorname{det}</tex> переименовывает состояния, после этого <tex>0</tex> всегда является начальным состоянием
# Третий шаг алгоритма (<tex>\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA)))</tex>): [[Файл:Rdrfa.png|Третий шаг]] После выполнения этого шага алгоритма оба состояния <tex>2</tex> и <tex>3</tex> являются начальными.
# Заключительный шаг алгоритма (<tex>\operatorname{det}(\operatorname{rev}(\operatorname{det}(\operatorname{rev}(FA))))</tex>): [[Файл:Drdrfa.png|Заключительный шаг]]

== Заключение ==
Самым эффективным алгоритмом минимизации принято считать [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]]. В [http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=EF3DD7271F6E8907A154A540D93F2B0C?doi=10.1.1.59.8276 работе], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритма Хопкрофта]] для автоматов с большим числом переходов.

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

==Литература==
# [http://sovietov.com/txt/minfa/minfa.html Алгоритм Бржозовского для минимизации конечного автомата]
# [http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=EF3DD7271F6E8907A154A540D93F2B0C?doi=10.1.1.59.8276 Deian Tabakov, Moshe Y. Vardi. Experimental evaluation of classical automata constructions]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]

Викиконспекты - Вклад участника [ru]

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