3813100530

jeśli istnieje obliczenie

sosi • • • Sm+l

maszyny A na słowie u takie, że s_m+i G F.

Oto przykłady automatów skończonych i słów przez nie akceptowanych. Przykład 1.14.

Niech £ = {a, b}. Rozważmy automat skończony K, = (A,F), gdzie

1.    A = ({so,si,S2}, (so},T).

2.    Funkcja przejścia T jest zilustrowana na diagramie 1.1.

3.    F = {si,S2}

Rysunek 1.1: Diagram przejść automatu K..

Niech u — ababaa G £* będzie słowem wejściowym automatu skończonego tC. Ciąg stanów

S0S1S0S1S0S1S2

jest obliczeniem K, na u takim, że S2 € F. Zatem słowo u jest akceptowane przez automat skończony K.

Przykład 1.15.

Rozważmy automat skończony K' = (A', F') nad alfabetem £ = {a, 6} taki, że

1.    A! = {so> si, s₂,s₃,S4,s₅}, {s₀},T).

2.    Funkcję przejścia T opisuje diagram na rysunku 1.2.

3.    F = {sq, $2}-

Rysunek 1.2: Diagram przejść automatu K!.

Niech u' = aaaaaabb G £* będzie słowem wejściowym automatu skończonego K!. Obliczeniem, poprzez które K,' akceptuje słowo u' jest:

S0S1S2S0S1S2S3S5S0.

13