Минимизация ДКА (Bnunbn[genx :TG)
Минимизация ДКА — построение по детерминированному конечному автомату (ДКА) эквивалентного ДКА, имеющего наименьшее возможное число состояний.
Минимальный ДКА
[править | править код]Для любого регулярного языка существует минимальный ДКА, который его принимает, то есть, ДКА с наименьшим возможным числом состояний. Такой автомат единственен с точностью до изоморфизма.
Алгоритмы
[править | править код]Алгоритм Хопкрофта
[править | править код]1. Разделить все состояния ДКА на две группы: группу конечных состояний и группу неконечных состояний.
2. Для каждого символа алфавита, проверить, в какую из групп перейдет автомат из каждого состояния, используя данный символ. Если из состояний A и B можно перейти в состояния C и D соответственно, то состояния A и B будут считаться эквивалентными по данному символу, если состояния C и D принадлежат одной и той же группе.
3. На основе этой информации разделить каждую группу на подгруппы, где состояния, эквивалентные по всем символам алфавита, находятся в одной подгруппе.
4. Повторять шаги 2 и 3 до тех пор, пока группы перестанут разделяться.
5. Построить новый автомат, используя полученные подгруппы в качестве новых состояний. Переходы между состояниями будут соответствовать переходам между подгруппами.
6. Удалить недостижимые состояния.
Этот раздел не завершён. |
Алгоритм Бжозовского
[править | править код]Пусть — ДКА. Обозначим через инвертированный автомат . Через обозначим детерминизированный автомат, полученный из процедурой построения подмножеств. Имеет место следующий результат[1]:
Пусть автомат распознаёт язык . Тогда минимальный ДКА для языка может быть найден как
См. также
[править | править код]Примечания
[править | править код]- ↑ Thomas Paranthoën, Ahmed Khorsi, Jean-Marc Champarnaud. Split and join for minimizing: Brzozowski's algorithm (англ.). undefined (2002). Дата обращения: 27 июля 2019. Архивировано 27 июля 2019 года.
Литература
[править | править код]- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to automata theory, languages, and computation, 2nd edition // ACM SIGACT News. — 2001-03-01. — Т. 32, вып. 1. — С. 60. — ISSN 0163-5700. — doi:10.1145/568438.568455.
Ссылки
[править | править код]- Алгоритм Бржозовского // Викиконспекты Университета ИТМО
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n)) // Викиконспекты Университета ИТМО
Это заготовка статьи по математике. Помогите Википедии, дополнив её. |