Приклад мінімізації автомата Мілі

Таблиця 1.25 - Таблиця переходів не мінімального автомата Мілі

Таблиця 1.26 - Таблиця виходів не мінімального автомата Мілі

Безпосередньо по таблиці виходів (табл. 1.26) l отримуємо розбиття p1 на класи одно еквівалентних станів, об'єднуючи в еквівалентні класи однакові стовпці: p1={b1, b2} b1={q1, q 2, q5, q7, q8} b2={q3, q4, q6, q9, q10, q11, q12}. Дійсно, два стани p1 - еквівалентні, якщо їх реакції на всілякі вхідні слова довжини 1 співпадають, тобто відповідні цим станам стовпці в таблиці виходів мають бути однакові. Будуємо таблицю p1, замінюючи стани в таблиці переходів (табл. 1.25) відповідними класами 1- еквівалентності.

Таблиця 1.27 - Розбиття p1 станів автомата Мілі

Очевидно, що 1- еквівалентні стани q_m і q_s будуть 2 - еквівалентними, якщо вони переводяться будь-яким вхідним сигналом також в 1 - еквівалентні. По таблиці T3 отримуємо розбиття p2={C1, C2, C3, C4}; C1= {q1, q2}, C2={q5, q7, q8}, C3={q3, q4, q6, q9, q11}, C4= {q10, q12}.

Таблиця 1.28 - Розбиття p2 станів автомата Мілі

Аналогічно побудуємо p3 ={D1, D2, D3, D4, D5}; D1={q1, q2}, D2={q5, q7}, D3={q8}, D4={q3, q4, q6, q9, q11 }, D5={q10, q12} і, нарешті p4 ={E1, E2, E3, E4, E5}, яке співпадає з p3. Процедура розбиття завершена. Розбиття p3 є розбиття множини станів автомата Мілі на класи еквівалентних між собою станів.

Таблиця 1.29 - Розбиття p3 станів автомата Мілі

Викреслюємо з D1 q2, з D2 q7, з D4 q4, q6, q9, q11, з D5 q12 визначуваний мінімальний автомат Мілі.

Таблиця 1.30 - Таблиця переходів мінімального автомата Мілі

Таблиця 1.31 - Таблиця виходів мінімального автомата Мілі