3813100537

K-2 będąc w stanie {so} i czytając „6” następuje przejście do stanu 0.

Ze stanu {si} automat K2 przechodzi do stanu {si, S2}, czytając symbol wejściowy „6”, gdyż K.2 będąc w stanie si i czytając „6” może wejść w stan S2, bądź pozostać w s\. Ponieważ automat K2 będąc w stanie s\ i czytając symbol „a” może tylko pozostać w si oraz nie istnieje przejście tego automatu ze stanu $2 poprzez „a”, automat deterministyczny K2 znajdujący się aktualnie w {si}, po przeczytaniu „a” pozostanie w {si}.

Będąc w stanie {si,S2} po przeczytaniu „6”, K2 nie zmieni stanu, bowiem w automacie K2 nie istnieje przejście od stanu S2 poprzez „6” oraz będąc w stanie si automat K.2 może pozostać w si lub wejść w S2- Z kolei będąc w stanie {si, S2} i czytając symbol „a” nastąpi przejście K2 do {si}, ponieważ w K2 nie istnieje przejście od stanu S2 poprzez „a” oraz będąc w si i czytając „a”, automat K2 może tylko pozostać w si.

Postępując dalej w podobny sposób, dostaniemy kompletny diagram 1.3 dla K2. Otrzymany automat deterministyczny możemy uprościć, zauważając, że nie ma krawędzi prowadzących do stanów {S2}, {so, ^si}> (^s0) ^s2} i {so> si, S2}. Po usunięciu wspomnianych stanów otrzymamy nowy automat (Rysunek 1.4.), ale będzie on nadal rozpoznawał ten sam język co automat K2-

b

a

a

b

Rysunek 1.4:

19