Алгоритм Бржозовского — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Заключение)
Строка 33: Строка 33:
  
 
== Заключение ==
 
== Заключение ==
Самым эффективным алгоритмом минимизации принято считать [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]]. В работе<ref>[http://citeseer.uark.edu:8080/citeseerx/viewdoc/summary;jsessionid=EF3DD7271F6E8907A154A540D93F2B0C?doi=10.1.1.59.8276]</ref>, сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритма Хопкрофта]] для автоматов с большим числом переходов.
+
Самым эффективным алгоритмом минимизации принято считать [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]], который, как и прочие традиционные алгоритмы, работает только с [[Детерминированные_конечные_автоматы|ДКА]]. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритм Хопкрофта]]. В работе<ref>[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]</ref>, сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее [[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))|алгоритма Хопкрофта]] для автоматов с большим числом переходов.
  
 
== См. также ==
 
== См. также ==
Строка 39: Строка 39:
 
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
  
 +
==Примечания==
 +
<references/>
 
==Источники информации==
 
==Источники информации==
 
# [http://sovietov.com/txt/minfa/minfa.html Алгоритм Бржозовского для минимизации конечного автомата]
 
# [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]
 
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Автоматы и регулярные языки]]
 
[[Категория: Автоматы и регулярные языки]]

Версия 23:07, 30 декабря 2014

Эта статья находится в разработке!
Задача:
Пусть дан автомат [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] это минимизированный КА.

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

[1]

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

  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]):
    Заключительный шаг

Заключение

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

См. также

Примечания

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

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