} {Er} {Er} {Er} {Er} 0 {F 1 } {Er} {F 2 } {Er} {Er} {Er} {Er} {Er} 0 {Z} {Er} {Er} {Er} {Er} {Er} {Er} {Er} 1 {E} {Er} {Er} {Er} {S} {Er} {Z} {Er} 0 {S 4 } {Er} {Er} {Er} {Er} {Er} {B} {Er} 0 {S 2 } {Er} {Er} {Er} {Er} {Er} {Er} {A} 0 {F 8 } {Er} {Er} {Er} {Er} {Z} {Er} {Er} 0 {F 2 } {Er} {F 3 } {Er} {Er} {Er} {Er} {Er} 0 {B} {Er} {Er} {Z} {Er} {Er} {E} {Er} 0 {A} {Er} {Er} {Z} {Er} {Er} {D} {Er} 0 {F 3 } {Er} {Er} {Er} {Er} {Z} {Er} {Er} 0 {D} {Er} {Er} {Er} {S} {Er} {Z} {Er} 0 {F 5 } {F 6 } {Er} {Er} {Er} {Er} {Er} {Er} 0 {F 6 } {Er} {Er} {Er} {Er} {Er} {Z} {Er} 0 {Er} {Er} {Er} {Er} {Er} {Er} {Er} {Er} 0
. ПОБУДОВА МІНІМАЛЬНОГО АВТОМАТА
Для отримання мінімального автомата скористаємося методом розбиття. Метод розбиття полягає в розбитті безлічі станів на непересічні підмножини (блоки), такі, що нееквівалентні стану потрапляють в різні блоки. p align="justify"> Умови еквівалентності станів:
Умова подібності: стану S і T повинні бути або обидва допускають, або обидва отвергающими.
Умова наступності: для всіх вхідних символів стану S і T повинні переходити в еквівалентні стану, тобто їх наступники еквівалентні.
Спочатку стану розбиваються на 2 блоки. Один містить тільки допускають, інший - що відкидають. Очевидно, ніяке з станів 1-го блоку не еквівалентно жодному станом другого блоку, що випливає з умови подібності. Потім відбувається розбиття цих блоків на більш дрібні за наступним алгоритмом:
. Якщо під дією якого-небудь вхідного символу якась частина станів даного блоку переходить в стану з іншого блоку, що порушує умову наступності, то необхідно розбити даний блок на частини так, щоб не порушувалося в одному блоці умова наступності. p align="justify"> 2. Необхідно повторювати крок 1 до тих пір, поки подальше розбиття неможливо. p align="justify"> 3. За один раз можна розбити тільки один блок. p align="justify"> Позначимо {S 1 S 3 } за {Y}.
.1 Ділимо на групи допускають, недопускати станів
