614372772

1.1    Definicja deterministycznego automatu skończonego

Deterministyczny automat skończony (w skrócie DAS lub ang. FDA - finite deterministic automata) jest zbudowany z następujących elementów:

1.    skończonego zbioru stanów, oznaczonych symbolem Q

2.    skończonego zbioru symboli wejściowych (nazywanego także alfabetem), oznaczonych symbolem E

3.    funkcji przejścia, przyjmującej za argument stan oraz symbol wejściowy a jej wynikiem jest stan, funkcja przejścia będzie oznaczana przez symbol S

4.    stanu początkowego, jest to jeden wyróżniony stan z Q

5.    zbioru stanów końcowych lub akceptujących F, gdzie F C Q

W skrócie o pewnym określonym DAS można mówić jako o następującej krotce o pięciu elementach:

A=(Q,Z,6,q₀,F)    (1)

gdzie A reprezentuje nazwę automatu, Q - to zbiór stanów, E - zbiór symboli wejściowych, S - funkcja przejścia, qo - stan początkowy, natomiast przez F oznaczamy zbiór stanów akceptujących.

Funkcja przejścia jest określona w następujący sposób: jeśli q jest stanem, natomiast a pewnym symbolem wejściowym, to wartością funkcji S(q, a) jest stan p, co oznacza że ze stanu q można przejść do stanu p jeśli pojawił się symbol a.

Graficzną reprezentacją automatu jest diagram przejść. Dla deterministycznego automatu skończonego A = (Q, E, 6, qo, F), diagram przejść to graf skierowany zbudowany następująco:

a)    każdemu stanowi ze zbioru Q odpowiada wierzchołek,

b)    dla pewnego stanu q 6 Q i dla symbolu wejściowego a € E funkcja S(q, a) = p. W diagramie przejść taka sytuacja oznacza iż istnieje luk z wierzchołka q do wierzchołka p (jeśli istnieje wiele symboli alfabetu E powodujących przejście z q do p, to diagram przejść dla czytelności zawiera tylko jeden luk etykietowany listą symboli),

c)    stan początkowy qn jest wskazywany przez strzałkę z napisem start (strzałka ta nie wychodzi z żadnego wierzchołka),

d)    wierzchołki odpowiadające stanom akceptującym (należą do zbioru F) oznaczane są podwójnym okręgiem, natomiast stany nienależące do F są oznaczane pojedynczym okręgiem.

Wygodnym sposobem reprezentacji funkcji przejścia 6 jest tablica przejść. Jest to tablicowa reprezentacja funkcji S, przyjmującej dwa argumenty i zwracającej jakąś wartość. Wiersze tablicy odpowiadają stanom, natomiast kolumny wejściom. Wpis w wierszu odpowiadającym stanowi q i kolumnie odpowiadającej wejściu o to zapis stanu S(q, a).

1.1.1    Przykład dla ciągów xO\y

Załóżmy chcemy zbudować automat deterministyczny który będzie zdolny do weryfikacji czy podany ciąg znaków spełnia definicję C (inaczej mówiąc przez C rozumiemy pewien język) o następującej postaci:

C = {w | w jest postaci xOly dla pewnych łańcuchów x, y złożonych wyłącznie z zer i jedynek} (2)

Inną, ale naturalnie równoważną definicją jest

C = (x01y | x, ysą dowolnymi łańcuchami zer i jedynek}    (3)

Przykłady łańcuchów należących do języka C są ciągi: 01, 11010 oraz 100011. Przykładami ciągów nienależących do języka C są ciągi £ (czyli ciąg pusty), 0, 111000. Łatwo stwierdzić iż alfabet to tylko dwa znaki E = (0,1}. Istnieje pewien zbiór stanów Q którego na razie nie precyzujemy ale już można wyróżnić stan początkowy qo. Automat musi zostać w taki sposób skonstruowany aby niejako pamiętał ważne fakty odnoście co pojawiło się na wejściu. W przypadku postawionego zadania możemy wyróżnić trzy następujące zdarzenia:

2