є таблиця 4.
Таблиця 4. Таблиця переходів детермінованого автомата
x0x1x2x3x4x5x6x7SErrFErrCErr {S1, S3} ErrErr0 {S1,
Побудуємо граф переходів детермінованого автомата (мал. 3). Для полегшення читаності графа не показано стан помилки і переходи з усіх станів детермінованого автомата в стан помилки по залишилися вхідним символам.
Граф переходів детермінованого автомата
В
Рис. 3
6. Побудова мінімального автомата
Для отримання мінімального автомата скористаємося методом розбиття. Метод розбиття полягає в розбитті безлічі станів на непересічні підмножини (блоки), такі, що нееквівалентні стану потрапляють в різні блоки. p align="justify"> Умови еквівалентності станів:
- умова подібності: стану S і T повинні бути або обидва допускають, або обидва отвергающими;
- умова наступності: для всіх вхідних символів стану S і T повинні переходити в еквівалентні стану, тобто їх наступники еквівалентні.
Спочатку стану розбиваються на 2 блоки. Один містить тільки допускають, інший - що відкидають. Очевидно, ніяке з станів 1-го блоку не еквівалентно жодному станом другого блоку, що випливає з умови подібності. Потім відбувається розбиття цих блоків на більш дрібні за наступним алгоритмом:
) Якщо під дією якого-небудь вхідного символу якась частина станів даного блоку переходить в стану з іншого блоку, що порушує умову наступності, то необхідно розбити даний блок на частини так, щоб не порушувалося в одному блоці умова наступності.
) Необхідно повторювати крок 1 до тих пір, поки подальше розбиття неможливо.
) За один раз можна розбити тільки один блок.
Позначимо {S1, S3} як {M}.
Поділимо на групи допускають, недопускати станів:
{{S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, { A1, B1, C1, D1, E1, F4, F8, F11}}.
Розіб'ємо {S, M, S2, S4, A, B, C, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} повходуx4:
{{S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err}, {A, B, C} , {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьемблок {S, M, S2, S4, D, E, F, F1, F2, F3, F5, F6, F7, F9, F10, Err} повходуx5:
{{S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10}, {A1, B1, C1, D1, E1, F4, F8, F11}}.
Разобьемблок {S, M, S2, S4, D, E, F, F1, F2, F5, F6, F9, Err} повходуx5:
{{S, M, S2, S4, F, F1, F2, F5, F6, F9, Err}, {A, B, C}, {F3, F7, F10},
{D, E}, {A1, B1,...
