Page 48 - 4128

w 2 b 2
b 1 Z 1 b 3
Z 2 Z 1
w 4 w 5
Z 1 Z 2
w 2 Z 2
Z 1 w 1 w 1
w 1
Z 2
b 4
Z 2
w 3
w 3 b 7
Z 1
w 2
Z 2
w 2
Z 1 w 2
Z 2
w 2
w 2 Z 2
b 5
b 6

Рисунок 2.7 - Автомат Мілі S 1, еквівалентний автомату Мура
S b
Внаслідок транзитивності відношення еквівалентності
два автомати Мілі S 1 і S a також будуть еквівалентними, але у
останнього будуть на 3 стани більше. Тобто, еквівалентні між
собою автомати можуть мати різну кількість станів, у зв'язку з
чим виникає задача знаходження мінімального (тобто з
мінімальною кількістю станів) автомата в класі еквівалентних
між собою автоматів.

2.3 Мінімізація кількості внутрішніх станів повністю
визначених автоматів

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