я? 3
S ??? 1? 2 x1x2x1x2x1x21y115A1A1A2B22y225B1A1 - - 3y135A1A1A2B24y142A1B1B2D25y117A1B1A2E26y122B1B1 - - 7y212A1B1 - -
? 3={A 3={1,3}, B 3={4}, C 3={5}, D 3={6}, E 3={2}, F 3={7}}.
4) Побудуємо? 4. Переходи станів 4,5 також можна не розглядати далі, оскільки класи не стануть менше в подальших ітераціях.
Таблиця 17 - Таблиця переходів для розбиття? 4
S ??? 1? 2? 3 x1x2x1x2x1x2x1x21y115A1A1A2B2A3C32y225B1A1 - - - 3y135A1A1A2B2A3C34y142A1B1B2D2 - - 5y117A1B1A2E2- - 6y122B1B1 - - - 7y212A1B1- - - -
? 4={A 4={1,3}, B 4={4}, C 4={5}, D 4={6}, E 4={2}, F 4={7}}.
Розбиття? 4 збігається з розбиттям? 3. На підставі теореми 3 шукане розбиття? ? збігається з? 3.
Отже, мінімальний автомат з еквівалентним поведінкою має 4 стану, що представляють собою блоки розбиття? 3, а його функції переходів і виходів представлені в таблиці 18, а граф переходів на малюнку 8.
Таблиця 18 - Таблиця переходів і виходів для минимизированного автомата із прикладу 3.
S ?? X1X2AACy1BBEy1CAFy1DEEy1EECy2FAEy2
Рисунок 8 - Мінімізований автомат (приклад 3)
Приклад 4
Мінімізація кінцевого автомата Мура, заданого таблицею переходів (табл. 19)
Таблиця 19 - Таблиця переходів для прикладу 4
S ?? x1x2x3ay1daeby1gbbcy2gbbdy2dbgey1dbgfy1cadgy2gbd
0) У даному прикладі початкове розбиття буде являти собою два блоки, що включають в себе всі стани.
Тому? 0={A 0={a, b, e, f}, B 0={c, d, g}}.
1) Розбиття? 1 в один блок об'єднує ті стани, які не можна розрізнити при подачі слів довжиною 1.
Таблиця 20 - Таблиця переходів для розбиття? 1
S ??? 0 x1x2x3x1x2x3ay1daeB0A0A0by1gbbB0A0A0cy2gbbB0A0A0dy2dbgB0A0B0ey1dbgB0A0B0fy1cadB0A0B0gy2gbdB0A0B0
? 1={А 1={a, b}, B 1={e, f}, C 1={c}, D 1={d, g}}.
2) Наступне розбиття? 2 об'єднує в один блок ті стани, які не можна розрізнити при подачі слів довжиною 2.
Побудуємо таблицю переходів (табл.21), але замість значення стану? (S, x) будемо писати блок розбиття? 1, в яке потрапляє? (S, x).
Переходи стану «с» тепер можна не розглядати, оскільки класи розпалися до першого елемента і менше вже не стануть. Позначимо це символами «-» у таблиці.
Таблиця 21 - таблиця переходів для розбиття? 2.
S ??? 0? 1 x1x2x3x1x2x3x1x2x3ay1daeB0A0A0D1A1B1by1gbbB0A0A0D1A1A1cy2gbbB0A0A0---dy2dbgB0A0B0D1D1D1ey1dbgB0A0B0D1D1D1fy1cadB0A0B0C1D1D1gy2gbdB0A0B0C1D1D1
Після побудови видно, що стану a, b і e, f потрібно розбити на 2 блоку {a}, {b} і {e}, {f}.
Таким чином,? 2={A 2={a}, B 2={b}, C 2={e}, D 2={f}, E 2={c}, F 2={d, g}}.
) Побудуємо розбиття? 3. Побудуємо розбиття? 3. Переходи станів «a», «b», «e», «f» можна не розглядати далі, оскільки класи розпалися до першого елемента. Позначимо це символами «-» у таблиці.
Таблиця 22 - Таблиця переходів для розбиття? 3
S ??? 0? 1? 2x1x2x3x1x2x3x1x2x3x1x2x3ay1daeB0A0A0D1A1B1---by1gbbB0A0A0D1A1A1---cy2gbbB0A0A0------dy2dbgB0A0B0D1D1D1F2B2F2ey1dbgB0A0B0D1D1D1---fy1cadB0A0B0C1D1D1---gy2gbdB0A0B0C1D1D1F2B2F2
? 3={A 3={a}, B 3={b}, C 3={e}, D 3={f}, E 3={c}, F 3={d, g}}.
Розбиття? 3 збігається з розбиттям? 2. На підставі теореми 3 шукане розбиття? ? збігається з? 2.
Отже, мінімальний автомат з еквівалентним поведінкою має 4 стану, що представляють собою блоки розбиття? 3, а його функції переходів і виходів представлені в таблиці 23, а граф переходів на рис. 9.
Таблиця 23 - Таблиця переходів і виходів для минимизированного автомата з прикладу 1
S ?? X1X2X3AFACy1BFBBy1CFBFy1DEAFy1EFBBy2FFBFy2
Рисунок 9 - Мінімізований автомат (приклад 4)
Висновок
У процесі написання даної курсової роботи були вивчені кінцеві автомати Мілі та Мура, еквівалентність і їх мінімізація. Детально розібрані приклади розв'язання типових завдань.
Список літератури
1) НОУ Інтуїт, лекція «Кінцеві автомати»
2) Карпов Ю.Г. Теорія автоматів [Навчальне видання для вузів]. Видавництво: «Пітер», 2003р., 206 стор.
) НОУ Інститут, лекція «Мінімізація і еквівалентніст...
