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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Заключение)
(Корректность)
Строка 23: Строка 23:
  
 
===Корректность===
 
===Корректность===
 +
[http://www.researchgate.net/publication/255626373_Split_and_join_for_minimizing__Brzozowski%27s_algorithm]
 +
 
==Пример работы==
 
==Пример работы==
 
* Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>):
 
* Исходный [[Недетерминированные конечные автоматы|НКА]] (<tex>FA</tex>):

Версия 01:25, 27 декабря 2014

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


Алгоритм

Описание

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

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

[math]mFA = det(rev(det(rev(FA))))[/math], где

  • [math]FA[/math] это исходный КА,
  • [math]rev[/math] это процедура обращения КА,
  • [math]det[/math] это процедура детерминизации КА,
  • [math]mFA[/math] это минимизированный КА.

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

[1]

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

  • Исходный НКА ([math]FA[/math]):

Исходный НКА

  • Первый шаг алгоритма ([math]rev(FA)[/math]):

Первый шаг

  • Второй шаг алгоритма ([math]det(rev(FA))[/math]):

Второй шаг

[math]det()[/math] переименовывает состояния, после этого [math]0[/math] всегда является начальным состоянием

  • Третий шаг алгоритма ([math]rev(det(rev(FA)))[/math]):

Третий шаг

После выполнения этого шага алгоритма оба состояния [math]2[/math] и [math]3[/math] являются начальными.

  • Заключительный шаг алгоритма ([math]det(rev(det(rev(FA))))[/math]):

Заключительный шаг

Заключение

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

См. также

Литература

  1. Алгоритм Бржозовского для минимизации конечного автомата
  2. Deian Tabakov, Moshe Y. Vardi. Experimental evaluation of classical automata constructions