Мінімізація числа станів автомата методом еквівалентного розбиття

Алгоритм мінімізації заснований на розбитті усієї множини станів на класи еквівалентних станів, що попарно не перетинаються, і заміні усього класу еквівалентності одним станом. Отриманий в результаті мінімізований автомат міститиме стільки станів на скільки класів еквівалентності було розбито початкову безліч станів.

Уведені відношення еквівалентності та k - еквівалентності можуть бути використані для розподілу множини станів автомата на попарно непересічні класи (так званий p -розподіл).

p - розподіл визначає замкнену сукупність класів сумісності, якщо для будь-якого його блоку виконується умова: внутрішній стан у мить (t + 1), у який перейде автомат з будь-якого стану одного блоку, завжди буде зна­ходитись у будь-якому, але тільки одному блоці цього розподілу.

p - розподіл дозволяє визначити надмірні елементи множини внутрішніх станів. Якщо, наприклад, стани q_s та q _m еквівалентні, формують один і той же вихідний сигнал, то один із них можна вилучити, унаслідок чого одержимо мінімізований автомат.

Розглянемо алгоритм мінімізації повністю визначених абстрактних автоматів Мілі, запропонований Ауфенкампом і Хоном. Основна ідея цього методу полягає в розбитті усіх станів початкового абстрактного автомата на попарно не пересічні класи еквівалентних станів і заміні кожного класу еквівалентності одним станом.

Відповідне розбиття на класи еквівалентних і k - еквівалентних станів позначатимемо p та p_k. Розподіл p дозволяє визначити надмірні елементи в множині станів Q. Нехай, наприклад, q_m і q_s еквівалентні. Це означає, що відносно зору реакцій автомата на всілякі вхідні слова неважливо, знаходиться автомат в стані q_m або q_s, і одне і них, наприклад q_s, може бути видалено з множини Q. Якщо кожен клас еквівалентності містить тільки один стан, множина Q нескоротна. Якщо ж один або декілька класів містять більше за один елемент, усі елементи, окрім одного в кожному клас, можуть бути виключені з множини Q, внаслідок чого виходить автомат з мінімальним числом станів.