614372766

3.    Fjj składa się ze zbiorów stanów, które zawierają co najmniej jeden stan akceptujący E, Fp = {S | S € Qd oraz 5 fi Fe i=- 0}.

4.    Dla wszystkich a € £ oraz S Q Qd wartość funkcji przejścia 6(S,a) jest obliczana w następujący sposób:

(a)    S= {px,p2,P3> ■ - • ,Pfc},

(b)    następnie należy wyznaczyć U_j=1 Se(Pż>u), wynikiem niech będzie zbiór {rj,r%,rz,.... r_m},

(c)    wtedy, wartość nowej funkcji przejścia jest określona jako Sp(S, a) =    ED(r^).

Automat z rysunku 6 po konwersji może przyjąć postać podobną do diagramu ukazanego na rysunku 9. Na tym diagramie został pominięty martwy stan 0 i wszystkie przejścia do tego stanu. Zastosowanie reguł wymienionych powyżej rozpoczynamy od stanu początkowego </o- Po konwersji stanem początkowym nowego automatu deterministycznego jest ED(ąo) = {9o,9i}- Następnie należy wyznaczyć na które stany przechodzą stany 90 i q\. Rysunek 6 pokazuje iż stan qi nie przechodzi na żaden inny stan przy znakach plus i minus. Jednak qo przechodzi na stan q\. Z tego powodu aby obliczyć «5d({<7o> 9i}, +), zaczynamy od {</[} i obliczamy e-domknięcie. Ponieważ nie ma e przejść z q\, to wartość funkcji przejścia <$d({90i 9i}, +) = {<?i}- Podobna sytuacja następuje w przypadku drugiego symbolu <5d({9o, 9i }, —) = {<7i}.

Kolejny etap to obliczenie wartości Ćd({<Jo> 9i}, •)• Diagram pokazuje że stan qa nie przechodzi na nic innego przy kropce, ale q\ przechodzi na stan 92- Oznacza to konieczność obliczenia ^-domknięcia 92- Nie ma e-przejść z 92, więc ten stan jest swym własnym domknięciem, ostatecznie w tym przypadku £©({90, 91}, •) = {92}-

Zakończenie analizy stanu początkowego wymaga obliczenie wartości funkcji przejścia dla cyfr, dobrym przykładem będzie cyfra zero: 6p({qo, 9i}, 0). Ze stanu 90 przy pomocy cyfry nie przejdziemy do żadnego innego stanu. Jednakże przejście następuje przy stanie 9j, ponownie do stanu 91 oraz 94. Obliczenie wartości funkcji przejścia jest dość łatwe, ponieważ nie ma przejść e: <5d({9o, 91},0) = {91,94}- Wartość dla pozostałych cyfr jest identyczna.

Dla pozostałych stanów sposób wyznaczania przejść jest podobny. Warto zwrócić uwagę iż w oryginalnym automacie mamy stan akceptujący 95. Jednak w wyniku konwersji otrzymamy dwa stany akceptujące {93,95} oraz {92,93,95}-

Rysunek 9: Deterministyczny automat pozbawiony przejść e zbudowany na podstawie 6

2.3 Równoważność skończonych automatów deterministycznych oraz automatów przejściami e

Wprowadzenie pustego przejścia e nie powoduje iż automaty z takimi przejściami mogą rozpoznawać inne języki. Każdy tego typu automat można zamienić na odpowiedni deterministyczny automat. Dalszy wniosek zapisany w postaci twierdzenia, dotyczy rozpoznawania języków:

Twierdzenie 3 Język L jest akceptowany przez pewien niedeterministyczny automat z przejściami e wtedy i tylko wtedy, gdy L jest akceptowany przez pewien deterministyczny automat.

Dowód: Należy sprawdzić dwie implikacje. W pierwszej kolejności zostanie przeanalizowana implikacja -£=. Zakładamy, że L = L(D) dla pewnego automatu deterministycznego D. Automat deterministyczny dość łatwo zamienić na odpowiedni automat niedeterministyczny z przejściami e. Dodajemy dodatkowe przejścia S(q, e) = 0 do wszystkich stanów 9 automatu deterministycznego. Należy także przekształcić przejścia na symbolach

13