Алгоритм минимизации DFA + пример

Здесь мы рассматриваем задачу минимизации количества состояний в детерминированном конечном автомате (ДКА). Ключевым моментом здесь является выявление пар состояний, которые «различимы» в том смысле, что чтение любой строки из обоих автоматов в конечном итоге приведёт к состоянию «принято» в одном случае и к состоянию «непринято» в другом. Затем мы рекурсивно строим определение различимых состояний. В заключение приведём два примера ДКА: один, из которого невозможно удалить ни одно состояние, и другой, из которого можно удалить несколько состояний.

Сайт Easy Theory: https://www.easytheory.org
GoFundMe: https://www.gofundme.com/f/easy-theor...
Patreon:   / easytheoryyt  
Fourthwall: https://easy-theory-llc-shop.fourthwa...
Канал «Решение задач»: @easytheoryprobsolve

Хронология:
0:00 — Вступление
0:30 — Цели видео
1:04 — Пример различения состояний
4:07 — Пример различения строк
7:17 — Определение различения состояний
9:40 — Пример 1 минимизации DFA
15:35 — Пример 2 минимизации DFA
20:18 — Заключение

Если вам понравился этот контент, подпишитесь на мой канал:    / @easytheory