Алгоритм Бржозовского
| Задача: |
| Пусть дан автомат . Требуется построить автомат с наименьшим количеством состояний, распознающий тот же язык, что и . |
Алгоритм
Описание
Алгоритм минимизации конечных автоматов Бржозовского (Janusz A. (John) Brzozowski) выделяется, по крайней мере, следующими качествами:
- Он элегантен и весьма оригинален.
- Он эффективен.
- Он работает даже с недетерминированными конечными автоматами.
Обладая обычными процедурами обращения и детерминизации конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры:
, где
- это исходный КА,
- это процедура обращения КА,
- это процедура детерминизации КА,
- это минимизированный КА.
Корректность
Пример работы
- Исходный НКА ():
- Первый шаг алгоритма ():
- Второй шаг алгоритма ():
переименовывает состояния, после этого всегда является начальным состоянием
- Третий шаг алгоритма ():
После выполнения этого шага алгоритма оба состояния и являются начальными.
- Заключительный шаг алгоритма ():
Заключение
Самым эффективным алгоритмом минимизации принято считать алгоритм Хопкрофта, который, как и прочие традиционные алгоритмы, работает только с ДКА. Его асимптотическое время выполнения зависит от логарифма исходных данных. С другой стороны очевидно, что алгоритм Бржозовского в худшем случае будет обладать экспоненциальным временем выполнения, ведь этого требует процедура детерминизации, выполняемая дважды. На практике же наблюдается парадокс, алгоритм Бржозовского во многих случаях опережает прочие подходы к минимизации, включая и алгоритм Хопкрофта. В работе [6], сравнивающей оба алгоритма, показано, что алгоритм Бржозовского оказывается эффективнее алгоритма Хопкрофта для автоматов с большим числом переходов.
