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