1={A 1={1,3,5,7,8}, B 1={2,4,6,9}}.
) Наступне розбиття? 2 об'єднує в один блок ті стани, які не можна розрізнити при подачі слів довжиною 2.
Побудуємо таблицю переходів (табл.9), але замість значення стану? (S, x) будемо писати блок розбиття? 1, в яке потрапляє? (S, x).
Таблиця 9 - Таблиця переходів для розбиття? 2
S ??? 1 ????????? 1225111B1B1A12144011A1B1B13225111B1B1A14322011A1B1B15643111B1B1A16896011A1B1B17628111B1B1A18447111B1B1A19797011A1B1A1
Після такої побудови видно, що стану 2,4,6,9 потрібно розбити на 2 блоку {2,4,6} і {9}.
Таким чином,? 2={A 2={1,3,5,7,8}, B 2={2,4,6}, C 2={9}}.
3) Аналогічно? 3 (табл.10)
Таблиця 10 - Таблиця переходів для розбиття? 3
S ??? 1? 2 ???????????? 1225111B1B1A1B2B2A22144011A1B1B1A2B2B23225111B1B1A1B2B2A24322011A1B1B1A2B2B25643111B1B1A1B2B2A26896011A1B1B1A2C2B27628111B1B1A1B2B2A28447111B1B1A1B2B2A29797011A1B1A1A2C2A2
На даному кроці блок {2,4,6} потрібно розбити на два блоки {2,4} і {6}. Таким чином, ? 3={A 3={1,3,5,7,8}, B 3={2,4} C 3={6}, D 3={9}}.
) Побудуємо? 4 (табл.11)
Таблиця 11 - Таблиця переходів для розбиття? 4
S ??? 1? 2? 3 ??????????????? 1225111B1B1A1B2B2A2B3B3A32144011A1B1B1A2B2B2A3B3B33225111B1B1A1B2B2A2B3B3B34322011A1B1B1A2B2B2A3B3B35643111B1B1A1B2B2A2C3B3A36896011A1B1B1A2C2B2A3D3C37628111B1B1A1B2B2A2C3B3A38447111B1B1A1B2B2A2B3B3A39797011A1B1A1A2C2A2A3D3A3
На даному кроці блок {1,3,5,7,8} потрібно розбити на два блоки {1,3,8} і {5,7}.
? 4={A 4={1,3,8}, B 4={5,7} C 4={2,4}, D 4={6}, E 4={9}}.
) Побудуємо? 5 (табл.12)
Таблиця 12 - Таблиця переходів для розбиття? 5
S ??? 1? 2? 3? 4 ?????????????????? 1225111B1B1A1B2B2A2B3B3A3C4C4B42144011A1B1B1A2B2B2A3B3B3A4C4C43225111B1B1A1B2B2A2B3B3B3C4C4B44322011A1B1B1A2B2B2A3B3B3A4C4C45643111B1B1A1B2B2A2C3B3A3D4C4A46896011A1B1B1A2C2B2A3D3C3A4E4D47628111B1B1A1B2B2A2C3B3A3D4C4A48447111B1B1A1B2B2A2B3B3A3C4C4B49797011A1B1A1A2C2A2A3D3A3B4E4B4
? 5={A 5={1,3,8}, B 5={5,7} C 5={2,4}, D 5={6}, E 5={9}}.
Розбиття? 5 збігається з розбиттям? 4. На підставі теореми 3 шукане розбиття? ? збігається з? 4.
Отже, мінімальний автомат з еквівалентним поведінкою має 4 стану, що представляють собою блоки розбиття? 4, а його функції переходів і виходів представлені в таблиці 13, а граф переходів на малюнку 7.
Таблиця 13 - Таблиця переходів і виходів для минимизированного автомата з прикладу 2.
S ???????? ACCB111BDCA111CACC011DAED011EBEB011
Малюнок 7 - Мінімізований автомат (приклад 2)
Приклад 3
Мінімізація кінцевого автомата Мура, заданого таблицею переходів (табл. 14)
Таблиця 14 - Таблиця переходів для прикладу 3
S ?? x1x21y1152y2253y1354y1425y1176y1227y212
) Початкове розбиття являє собою один блок, що включає в себе всі стану, оскільки вхідні слова довжиною 0 (пусте слово?) Не розрізняють станів: незалежно від того, в якому стані автомат знаходився при подачі входу?, виходом теж буде?.
Тому? 0={A 0={1,2,3,4,5,6,7}}.
) Розбиття? 1 в один блок об'єднує ті стани, які не можна розрізнити при подачі слів довжиною 1.
Стани 2 і 7 потрапляють в інший блок, але між собою вхідним словом довжини 1 їх розрізнити не можна.
Тому? 1={А 1={1,3,4,5,6}, B 1={2,7}}
) Наступне розбиття? 2 об'єднує в один блок ті стани, які не можна розрізнити при подачі слів довжиною 2.
Побудуємо таблицю переходів (табл.15), але замість значення стану? (S, x) будемо писати блок розбиття? 1, в яке потрапляє? (S, x).
Таблиця 15 - таблиця переходів для розбиття? 2.
S ??? 1 x1x2x1x21y115A1A12y225B1A13y135A1A14y142A1B15y117A1B16y122B1B17y212A1B1
Після такої побудови видно, що стану 1,3,4,5,6 потрібно розбити на 3 блоки {1,3}, {4,5}, {6}, а стану 2,7- на два блоки {2}, {7}.
Таким чином,? 2={A 2={1,3}, B 2={4,5}, C 2={6}, D 2={2}, E 2={7}}.
3) Переходи станів 2,6,7 тепер можна не розглядати, оскільки класи розпалися до першого елемента і менше вже не стануть. Позначимо це символами «-» у таблиці.
Таблиця 16 - Таблиця переходів для розбитт...
