Алгоритм Бржозовского — различия между версиями
(→Пример) |
(→Описание) |
||
| Строка 2: | Строка 2: | ||
==Алгоритм== | ==Алгоритм== | ||
===Описание=== | ===Описание=== | ||
| + | Обладая обычными процедурами обращения (rev) и детерминизации (det) конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры: | ||
| + | mFA = det(rev(det(rev(FA)))), где | ||
| + | |||
| + | FA это исходный КА, | ||
| + | rev это процедура обращения КА, | ||
| + | det это процедура детерминизации КА, | ||
| + | mFA это минимизированный КА. | ||
| + | |||
===Корректность=== | ===Корректность=== | ||
==Пример работы== | ==Пример работы== | ||
Версия 05:34, 18 ноября 2014
Эта статья находится в разработке!
Содержание
Алгоритм
Описание
Обладая обычными процедурами обращения (rev) и детерминизации (det) конечного автомата, мы, с помощью идеи Бржозовского, можем немедленно приступить к минимизации заданного автомата. Для этого надо дважды провести его через обе вышеуказанные процедуры: mFA = det(rev(det(rev(FA)))), где
FA это исходный КА, rev это процедура обращения КА, det это процедура детерминизации КА, mFA это минимизированный КА.
Корректность
Пример работы
Псевдокод
См. также
- Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
