3813100543

1.1.1. Pojęcie skończenie stanowej maszyny

Niech E będzie alfabetem.

Definicja 1.1. Niedeterministyczną skończenie stanową maszyną nad alfabetem E nazywamy trójkę uporządkowaną A = (S,I,T), gdzie

1.    S jest niepustym, skończonym zbiorem,

2.    ICS,

3.    T : 5 x E —» V(S).

W dalszym ciągu niniejszej pracy magisterskiej „niedeterministyczną skończenie stanową maszynę” będziemy nazywać krótko „maszyną”.

Zgodnie z definicją, maszyna jest układem złożonym z trzech elementów: skończonego zbioru 5 - zwanego zbiorem stanów maszyny, jego podzbioru I - tzw. zbioru stanów początkowych - tzn. takich stanów, od których maszyna rozpoczyna działanie. Ostatnim elementem układu jest funkcja przejścia T. Można ją traktować jako zbiór reguł przechodzenia od stanu do stanu. Przejścia te zachodzą w warunkach, gdy maszyna znajduje się w konkretnym stanie s € S i czyta konkretny symbol a € E. Istotą niedeterminizmu jest to, że dla dowolnego symbolu wejściowego a czytanego w danym stanie s, może być wiele - albo i żaden — dopuszczalnych stanów, do których maszyna czytając ten symbol może przejść. Stanowią one zbiór T(s, er). Tak więc informację „T(s, er) = S'”, gdzie s € 5, er € E, S' € V(S) interpretuje się następująco: jeśli maszyna A znajduje się w stanie s i czyta symbol er, to może ona przejść do jednego ze stanów należących do S'.

Szczególnym przypadkiem niedeterministycznej skończenie stanowej maszyny jest tzw. deterministyczna skończenie stanowa maszyna.

Definicja 1.2. Deterministyczną skończenie stanową maszyną nazywamy trójkę uporządkowaną A = (S, (so},T) taką, że

1.    S jest skończonym, niepustym zbiorem,

2.    s₀ € S,

3.    f : S x E -► 5.

Maszyna deterministyczna składa się ze skończonego, niepustego zbioru stanów S, jednego stanu początkowego so oraz funkcji przejścia T. Tym razem dla dowolnego symbolu wejściowego istnieje dokładnie jedno przejście z każdego stanu odpowiadające temu symbolowi. Zatem T(s,a) = s', gdzie s,s' G S, a € E, interpretujemy następująco: jeśli maszyna deterministyczna A znajduje się w stanie s i czyta symbol a to wchodzi w stan s'.

Z każdą maszyną wiążemy diagram przejść. Diagram przejść to graf skierowany zdefiniowany w następujący sposób: wierzchołki grafu odpowiadają stanom

7