Page 49 - 4128

Для користування методом введемо декілька означень.
Два стани абстрактного автомата називаються 1-
еквівалентними в тому випадку, якщо реакції автомата в цих
станах на будь-які вхідні слова співпадають.
Об'єднання всіх 1-еквівалентних станів абстрактного
автомата утворює 1-клас еквівалентності.
1-еквівалентні стани автомата називаються 2-
еквівалентними, якщо вони переводяться будь-яким вхідним
сигналом також в 1-еквівалентні стани.
Об'єднання всіх 2-еквівалентних станів утворює 2-клас
еквівалентності.
По індукції можна розповсюдити визначення до i-
еквівалентних станів і i-класів еквівалентності.
Якщо для деякого i розбиття станів автомата на ( i +1) -
класи співпадає з розбиттям на i-класи, то воно є розбиттям і
на  - класи еквівалентності.
Розбиття безлічі внутрішніх станів автомата на  -
класи і є необхідним розбиттям на класи еквівалентності, при
цьому таке розбиття може бути одержане за кінцеву кількість
кроків.
Все вищевикладене безпосередньо застосовується для
мінімізації автомата Мілі. При мінімізації повністю
визначених автоматів Мура вводиться поняття 0-
еквівалентності станів і розбиття безлічі станів на 0-
еквівалентні класи: до такого класу відносяться однаково
відмічені стани автомата Мура.
Якщо два 0-еквівалентні стани будь-яким вхідним
сигналом переводиться в два 0-еквівалентні стани, то вони
називаються 1-еквівалентними. Всі подальші класи
еквівалентності станів для автомата Мура визначаються
аналогічно приведеному для автоматів Мілі.
Розглянемо приклад мінімізації автомата Мілі,
заданого таблицями переходів і виходів:

48