Алгоритми мінімізації скінченних автоматів

Мінімальна форма автомата S (позначається як Š) у теорії автоматів являє собою автомат з ň станами, що утворюють множину {σ₁..σ_ň}. Мінімальний автомат з S будується так. Характеристичні функції автоматів S та Š позначаються g_s, g_z і g'_s , g'_z відповідно. Тоді, якщо
${\displaystyle ~{g_{s}(\xi _{i},\sigma ^{(u)})=\xi _{j}\qquad \qquad g_{z}(\xi _{i},\sigma ^{(u)})=\sigma ^{(v)}}}$, то
${\displaystyle ~{g'_{s}(\xi _{i},\sigma ^{u})=\xi _{j}\qquad \qquad \ \;g'_{z}(\xi _{i},\sigma ^{u})=\sigma ^{v}}}$.

Таким чином, при побудові Š за заданою умовою не виникає ніякої невизначеності.

Алгоритм знаходження мінімального автомата запропонували Ауфенкамп і Хон. Вони показали, що для знаходження мінімального автомата необхідно знаходити послідовні розбиття P_i автомата S на класи 1, 2, …, k, (k+1) — еквівалентних між собою станів, аж поки на якомусь (k+1) кроці не виявиться, що P_k = P_k+1. Таким чином, розбиття P_k дає всі класи еквівалентності станів автомата S. Всім станам S, що належать до класу еквівалентності Σ_l можна приписати загальне позначення, наприклад, σ_l. Таким чином, автомат Š виходить з автомата S «​​об'єднанням» однаково позначених станів у один стан. Способи, якими це об'єднання проводиться, істотно залежать від того, яким способом визначено автомат — таблицею, графом чи матрицею.

Якщо Š є мінімальною формою автомата S, то:

1. Š є єдиною мінімальної формою з точністю до позначення станів
2. Š = S
3. Ніякі два стани Š не є еквівалентними
4. Не існує автомата, еквівалентного S і меншого (з меншим числом станів), ніж Š.

• Скінченний автомат
• Мінімізація ДСкА

• Артур Гилл. Введение в теорию конечных автоматов^{[недоступне посилання з червня 2019]}