8299308031

Przykład 1.2

Załóżmy, że automat A= (Q, E, S, qo, F) dany jest na stępująco:

•    Q1S {l,2,3,Śm}

•    E = {a, b, c}

•    funkcja 5 będzie dana tabelką

5	a	b	c
1	2	Śm	1
2	Śm	3	Sm
3	2	Śm	1
Sm	Śm	Śm	Śm

• <70 = 1

Rysunek obok przedstawia ten właśnie automat.

Kółka to stany. Kółko ze strzałeczką to stan początkowy.

Kółka podwójne to stany końcowe — w tym przypadku jest tylko jeden stan końcowy, w dodatku pokrywający się ze stanem początkowym.

Funkcja przejścia oznaczona jest strzałkami między stanami, na strzałkach stoją litery alfabetu. Ponieważ to jest funkcja, musi mieć określony wynik dla każdej pary (stan, litera), co rysunkowo oznacza, że z każdego kółka musi wychodzić po jednej strzałce dla każdej litery alfabetu.

Stan Śm to „śmietnik” zbierający wszystkie niepotrzebne strzałki; wyjść od niego można tyko z powrotem do śmietnika.

□

Automat można traktować jako planszę do „gry” wynikiem której jest akceptacja lub odrzucenie danego słowa w złożonego z liter pochodzących z alfabetu E. Gra zaczyna się od pionka stojącego w stanie początkowym (w przykładzie 1.2 — na polu 1); następnie pionek jest przesuwany na kolejne pola po strzałkach odpowiadającym kolejnym literom w, aż do wyczerpania wszystkich liter. Jeśli to doprowadziło pionek do stanu akceptującego, to słowo „wygrało”, czyli zostało zaakceptowane; jeśli do stanu nieakceptującego, to słowo zostało odrzucone¹.

Łatwo widać, że w przykładzie 1.2:

•    słowo abba prowadzi do stanu Sm, więc jest odrzucone;

•    słowo abca prowadzi do stanu 2, więc również jest odrzucone;

•    słowo ababc prowadzi do stanu 1, więc jest akceptowane;

•    słowo puste (nie zawierające żadnej litery) prowadzi do stanu 1, więc jest akceptowane; takie słowo będziemy oznaczać przez e.

5

1

Porządna matematyczna definicja akceptowania słowa przez automat wykorzystuje funkcję przejścia <5 z definicji automatu i nie wspomina o ruchach pionka.