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

Завдання мінімізації автомата зводиться до пошуку його мінімальної форми (мінімального автомата). Мінімальний автомат — це автомат, що має найменшу можливу кількість станів і реалізує задану функцію виходів.

Принцип побудови

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

Отримана при цьому таблиця є таблицею переходів Š.

Граф переходів

Якщо задано граф переходів (діаграму станів) і еквівалентне розбиття Σ₁..Σ_ň автомата S, то граф переходів Š можна побудувати так:

1. Замінити позначення кожного стану, наявного в графі переходів S, позначенням класу, до якого належить цей стан.
2. Об'єднати всі однаково позначені стани (розглядаючи дуги графу як «гнучкі зв'язки») і подати об'єднані стани одним станом, який має спільне позначення.
3. З кожної групи дуг, що мають спільний початковий і спільний кінцевий стан викреслити всі, крім однієї.

Отриманий у результаті граф буде графом Š.

Матриця переходів

Якщо задано матрицю переходів і еквівалентне розбиття Σ₁..Σ_ň автомата S, то матрицю переходів Š можна побудувати так:

1. Провести симетричну перестановку і симетричне розбиття [S] так, щоб рядки (і стовпці) групувалися за класами еквівалентності S (цю ж матрицю можна отримати при матричному методі еквівалентного розбиття).
2. Замінити всі позначення рядків (і стовпців) кожної групи, що представляє клас еквівалентності, одним позначенням цього класу.
3. Замінити кожну підматрицю в розбитій матриці однією клітинкою, що містить усі пари вхід-вихід, які є в будь-якому рядку цієї підматриці (усі рядки в будь-якій такій підматриці містять одну і ту ж множину пар вхід-вихід).

Отримана в результаті матриця є матрицею переходів Š.

Властивості мінімальної форми

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

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

Див. також

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

Посилання

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