у.
еквівалентність автомат распознаватель мінімізація
2. Практична частина
Приклад 1
Мінімізація кінцевого автомата Мілі, заданого таблицею переходів (табл. 3) проводиться послідовним побудовою разбиений? 0,? 1, ...
Таблиця 3 - таблиця переходів для прикладу 1
S ?? x1x2x1x2012y1y2134y3y2245y3y2364y1y2465y1y2563y1y2660y1y2
0) Початкове розбиття являє собою один блок, що включає в себе всі стану, оскільки вхідні слова довжиною 0 (пусте слово?) Не розрізняють станів: незалежно від того, в якому стані автомат знаходився при подачі входу? , виходом теж буде?.
Тому? 0={A 0={0,1,2,3,4,5,6}}.
1) Розбиття? 1 в один блок об'єднує ті стани, які не можна розрізнити при подачі слів довжиною 1.
Функція виходів? при подачі слів x 1 і x 2 не може розрізнити 0,3,4,5,6 оскільки для кожного з цих станів при подачі на вхід автомата x 1 він видає y 1, а при подачі на вхід x 2 він видає y 2.
Стани 1 і 2 потрапляють в інший блок, але між собою вхідним словом довжини 1 їх розрізнити не можна.
Тому? 1={А 1={0,3,4,5,6,}, B 1={1,2}}
2) Наступне розбиття? 2 об'єднує в один блок ті стани, які не можна розрізнити при подачі слів довжиною 2.
Побудуємо таблицю переходів (табл.2), але замість значення стану? (S, x) будемо писати блок розбиття? 1, в яке потрапляє? (S, x).
Таким чином, наприклад,? (0, x 1)=1, а цей стан знаходиться в блоці B 1; ? (0, x 2)=2, а цей стан знаходиться в блоці B 1.
Таблиця 4 - таблиця переходів для розбиття? 2.
S ??? 1 x1x2x1x2B1B1012y1y2A1A1134y3y2A1A1245y3y2A1A1364y1y2A1A1465y1y2A1A1563y1y2A1A1660y1y2A1A1
Після такої побудови видно, що стану 0,3,4,5,6, потрібно розбити на 2 блоку {0} і {3,4,5,6}. Стани 1 і 2 потрапляють в одні й ті ж блоки попереднього розбиття? 1, тому вони потраплять в один і той же блок розбиття? 2. Таким чином, ? 2={A 2={0}, B 2={3,4,5,6}, C 2={1,2}}.
) Аналогічно будується розбиття? 3.
Таблиця 5 - Таблиця переходів для розбиття? 3
S ??? 1? 2 x1x2x1x2B1B1C2C2012y1y2A1A1B2B2134y3y2A1A1B2B2245y3y2A1A1B2B2364y1y2A1A1B2B2465y1y2A1A1B2B2563y1y2A1A1B2B2660y1y2A1A1B2A2
На даному кроці блок {3,4,5,6} потрібно розбити на два блоки {3,4,5} і {6}.
Таким чином,? 3={A 3={0}, B 3={3,4,5}, C 3={6}, D 3={1,2}}.
) Побудуємо? 4.
Таблиця 6 - Таблиця переходів для розбиття? 4
S ??? 1? 2? 3 x1x2x1x2B1B1C2C2D3D3012y1y2A1A1B2B2B3B3134y3y2A1A1B2B2B3B3245y3y2A1A1B2B2C3B3364y1y2A1A1B2B2C3B3465y1y2A1A1B2B2C3B3563y1y2A1A1B2B2C3B3660y1y2A1A1B2A2C3A3
? 4={A 4={0}, B 4={3,4,5}, C 4={6}, D 4={1,2}}.
Розбиття? 4 збігається з розбиттям? 3. На підставі теореми 3 шукане розбиття? ? збігається з? 3.
Отже, мінімальний автомат з еквівалентним поведінкою має 4 стану, що представляють собою блоки розбиття? 3, а його функції переходів і виходів представлені в таблиці 7, а граф переходів на рис. 6.
Таблиця 7 - Таблиця переходів і виходів для минимизированного автомата з прикладу 1
S ?? X1X2X1X2ADDy1y2BBCy1y2CCAy1y2DBBy3y2
Малюнок 6 - Мінімізований автомат (приклад 1)
Приклад 2
Мінімізація кінцевого автомата Мілі, заданого таблицею переходів (табл. 8)
Таблиця 8 - Таблиця переходів для прикладу 2
S ???????? 122511121440113225111432201156431116896011762811184471119797011
) Початкове розбиття являє собою один блок, що включає в себе всі стану, оскільки вхідні слова довжиною 0 (пусте слово?) Не розрізняють станів: незалежно від того, в якому стані автомат знаходився при подачі входу?, виходом теж буде?.
Тому? 0={A 0={1,2,3,4,5,6,7,8,9}}.
) Розбиття? 1 в один блок об'єднує ті стани, які не можна розрізнити при подачі слів довжиною 1.
Функція виходів? при подачі слів?,? і? не може розрізнити 1,3,5,7 і 8, оскільки для кожного з цих станів при подачі на вхід автомата? він видає 1, при подачі на вхід?- 1 і при подачі на вхід? він видає 1.
Стани 2,4,6 і 9 потрапляють в інший блок, але між собою вхідним словом довжини 1 їх розрізнити не можна.
Тому? ...
