614372774

automat, zaczynając działanie w stanie 9 i przetwarzając dostarczony ciąg w. Funkcja 5 posiada indukcyjną definicję po długości łańcucha wejściowego:

Podstawa: 6(q, e) = q, jeśli automat znajduje się w stanie q i nie został odczytany żaden symbol wejściowy, to automat nadal znajduje się w stanie q.

Krok Indukcyjny: Zakładamy, że w jest łańcuchem o postaci xa, co oznacza iż symbol a jest ostatnim symbolem w, a x jest łańcuchem składającym się ze wszystkich symboli w poza ostatnim. Czyli, słowo w = 1101 zostałoby rozbite na a: = 110 oraz a = 1. Taka definicja pozwala na stwierdzenie iż

%«;) = <$(%,*),«).

Wyjaśnienie powyższego zapisu jest następujące. Aby obliczyć S(q,w), obliczamy S(q,x), czyli stan, w którym znajdzie się automat po przetworzeniu wszystkich symboli w poza ostatnim. Jeśli założymy, że tym stanem jest p, czyli S(q, x) = p. Toteż, dokonując przejścia ze stanu p na wejściu a, w przypadku ostatniego symbolu w, otrzymamy S(q,w), czyli ostatecznie otrzymamy 6(q,w) = 5(p, a). □ 1.2.1 Język o parzystej liczbie zer i jedynek

Przykładem ilustrującym zastosowania rozszerzonej funkcji przejścia będzie skończony automat deterministyczny, rozpoznający czy podany wyraz należy do języka o parzystej liczbie zer i jedynek. O takim automacie można powiedzieć iż będzie zliczał wystąpienia zer bądź jedynek modulo 2. Stan będzie używany do pamiętania, czy widziana dotąd liczba zer bądź jedynek jest parzysta bądź nieparzysta. Można wyróżnić cztery stany, a ich opis przedstawia się następująco:

<7o: ujrzana dotąd liczba jedynek oraz zer jest parzysta,

9i: ujrzana liczb zer jest parzysta, ale liczb jedynek jest nieparzysta, q2'. ujrzana liczb jedynek jest parzysta, ale liczb zero jest nieparzysta,

93: ujrzana dotąd liczba jedynek oraz zer jest nieparzysta.

Z opisu wynika, że stan qn jest stanem początkowym oraz końcowym. Diagram przejść jest przedstawiony na rysunku 3. Tabela przejść przyjmuje następującą postać:

0

-* 9o *9i

92

93

92

93

90

91

91 9o 93

92

Funkcja 5 nadaje się bardzo dobrze do ilustracji działania, bądź też sprawdzenia czy automat został dobrze zaprojektowany np.: chcemy sprawdzić czy S(qo, 110101) = 90. Sposób obliczanie wartości funkcji S(qo, w) polega na obliczanie wartości dla każdego prefiksu w, poczynając od s i idąc w kierunku rosnącej długości, przedstawia się to następująco:

•    S(q₀,£) = qo,

•    <5(90,1) = S(6(q₀,e), 1) = %o, 1) = 9i ,

•    <5(9o, 11) = <5(<5(9o, 1), 1) = 5(9i. 1) = 9o ,

•    <5(9o, HO) = 5(5(ę₀,ll),0) = <5(9o,0) =92 ,

•    S(qo, 1101) = <5(<5(9o, 110), 1) = 5(92,1) = 93 ,

•    5(9o, 11010) = 5(5(9o, 1101), 0) = 5(93,0) = 91 ,

. 5(90,110101) = 5(5(9o, 11010), 1) = 5(_9l, 1) = 90 ■

4