614372779

•    Dla 5(9o,5) obliczenia są następujące:

1.    W pierwszej kolejności należy obliczyć przejścia na wejściu 5 ze stanów 90 i 91, które otrzymano po obliczeniu 8(qo,e):

5(90,5) U<5(<?i,5) = 0U {91,94} = {91,94}

2.    Następnie trzeba wyznaczyć e-domknięcia w kroku (1). Otrzymamy:

ED(ęi) U ED(ę₄) = {91} U {94} = {91,94}

Otrzymaliśmy taki sam zbiór jak dla funkcji 5(90, 5).

•    Obliczenia dla <$(90,5.) przy wykorzystaniu zbioru wyznaczonego w poprzednim punkcie:

1.    <S(ęi,.)U<5(g₄,.) = {92} U {93} = {92,93}

2.    <5(ę₀,5.) = ED(ę₂) U ED(g₃) = {92} U {93,95} = {92,93,95 }

•    Obliczenia dla <5(ęo> 5.6):

1.    5(92,6) U 5(93,6) U 0(95,6) = {93} U {93} U 0 = {93}

2.    5(9o,5.6) = ED(ę₃) = {93,95}

Ponieważ wartość dla 5(<jo, 5.6) zawiera stan akceptujący 95, więc łańcuch 5.6 należy do języka automatu z rysunku 6.

Pozwala to na ogólne zdefiniowanie języka dla automatu niedeterministycznego, niech E = {<5, E,5, qo, F} to podobnie jak w pozostałych dwóch typach automatów L(E) = {w 15(9o, iu) fi F / 0}. Język automatu E to zbiór takich słów w przeprowadzających stan początkowy na co najmniej jeden stan akceptujący.

2 Własności automatów

Automat skończony A jest zupełny (znakiem # wyjątkowo oznaczamy moc zbioru), gdy:

Voes V,₆q #5(9, a) > 1 Automat skończony A jest deterministyczny:

(i)    ^v«eQ #<5(9, e) = 0

(ii) V_aeEV_9eQ #5(9, a) < 1

Automat skończony A jest deterministyczny i zupełny:

0) V_9€q #5(9, s) =0 (ii)V_oe2V_geQ #5(9, a) = 1

Automat skończony zupełny nazywamy automatem Rabina-Scotta. Natomiast automat skończony, deterministyczny oraz zupełny nazywa się deterministycznym automatem Rabina-Scotta.

2.1 Równoważność skończonych automatów deterministycznych oraz niedetermi-nistycznych

Niech A = {Q,E, 5,90, F} będzie deterministycznym automatem skończonym. Język automatu A to słowa należące do L(A):

L(A) = {w 15(90, w) 6 F}.

Język automatu A to zbiór łańcuchów w przeprowadzających stan początkowy 90 w jeden ze stanów akceptujących. Jeśli L = L(A) dla pewnego automatu A, to o języku L możemy powiedzieć, że jest językiem regularnym.

Język dla niedeterministycznego automatu skończonego, również można określić w podobny sposób. Fakt iż automat ten znajduje się w wielu stanach naraz nie przeszkadza, gdy na pracę automatu spojrzy się całościowo.