614372775

Rysunek 3: Deterministyczny automat skończony akceptujący wyrazy zbudowane z parzystej liczby zer oraz jedynek

1.3 Niedeterministyczny automat skończony

Niedeterministyczny automat skończony jest zbudowany w dość podobny sposób jak automat deterministyczny, posiada skończony zbiór symboli wejściowych, jeden stan początkowy oraz zbiór stanów akceptujących. Istnieje także funkcja 5 jednak to ona stanowi o zasadniczej różnicy pomiędzy automatami. Funkcja 6 podobnie jak w przypadku automaty deterministyczne za argumenty przyjmuje stan oraz symbol wejściowy jednak w wyniki może wygenerować zbiór stanów. Co oznacza iż automat niedeterministyczny może znajdować się w kilku stanach naraz.

Formalna definicja niedeterministyczne automatu skończonego to następująca piątka (identyczna jak w przypadku automatu deterministycznego):

A = (Q,E,<S,g₀,F)    (5)

gdzie

1.    Q jest skończonym zbiorem stanów,

2.    E jest skończonym zbiorem symboli wejściowych,

3.    <7o £ Q to stan początkowy,

4.    F CQ - jest zbiorem stanów końcowych lub akceptujących,

5.    6 jest funkcją przejścia, która przyjmuje jako argumenty stan z Q i symbol wejściowy E i zwraca podzbiór

Q-

Rysunek 4 przedstawia niedeterministyczny automat akceptujący łańcuchy zero-jedynkowe, które na końcu zawierają ciąg 01. Stan początkowy to stan go- Automat pozostaje w tym stanie, gdy jeszcze nie „zgadł”, iż rozpoczął się końcowy łańcuch 01. Bowiem, zawsze jest możliwe, iż następny symbol nie rozpoczyna końcowego 01, nawet gdy tym końcowym symbolem jest 0.

Jeśli jednak następnym symbolem jest końcowe 0, to automat zgaduje, że końcowe 01 się rozpoczęło. Zatem łuk o etykiecie 0, kieruje nas do stanu go ale drugi z łuków przenosi nas do stanu gj. Inaczej mówiąc automat znajduje się w tych dwóch stanach. Będąc jednak w stanie gi, jeśli automat zobaczy 1 to przechodzi do stanu g2 i łańcuch zostanie zaakceptowany.

Rysunek 4: Niedeterministyczny automat skończony akceptujący wyrazy kończące się wyrażeniem 01