Теми рефератів
> Реферати > Курсові роботи > Звіти з практики > Курсові проекти > Питання та відповіді > Ессе > Доклади > Учбові матеріали > Контрольні роботи > Методички > Лекції > Твори > Підручники > Статті Контакти
Реферати, твори, дипломи, практика » Курсовые проекты » Еквівалентність та мінімізація кінцевих автоматів

Реферат Еквівалентність та мінімізація кінцевих автоматів





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 - Таблиця переходів для розбитт...


Назад | сторінка 5 з 7 | Наступна сторінка





Схожі реферати:

  • Реферат на тему: Електронна таблиця
  • Реферат на тему: Таблиця Excel
  • Реферат на тему: Хімічна таблиця Менделєєва
  • Реферат на тему: Таблиця форматів стандартної поліграфічної продукції
  • Реферат на тему: Розбиття натурального ряду