8299308031

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 odrzucone1.

Ł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.



Wyszukiwarka

Podobne podstrony:
mikroekonomia ćwiczenia (10) d. 1. Załóżmy, że w danym okresie popyt konsumentów na przejazdy tramw
Depresja u dzieci i mlodzieży 9 (21) Josś Collados Zorragulno _    ■ ga na przykład
CCF20101004007 22 1. W pro wad zen i e Stosowanie warunku (1.1.13) wyjaśnimy na następującym przykł
Przykład.Załóżmy, że jednostka gospodarcza XYZ na dzień 1 stycznia 200X roku wykazywała następujące
32718 mikroekonomia ćwiczenia (10) d. 1. Załóżmy, że w danym okresie popyt konsumentów na przejazdy
Progowanie jasności Dla przykładu załóżmy, że obraz f(x,y) zawiera ciemne obiekty umieszczone na jas
CCF20101004007 22 1. Wprowadzenia Stosowanie warunku (1.1.13) wyjaśnimy na następującym przykładzie
32718 mikroekonomia ćwiczenia (10) d. 1. Załóżmy, że w danym okresie popyt konsumentów na przejazdy
img057 gdzie / (a) = 10.1 (#.-1) i odrzucamy hipotezę zerową, gdy t > 2ol 1 («-1) Przykład. 5.1.
s390 390 Poznaj Linux kwestii. Dla przykładu załóżmy, że użytkownik o nazwie vector sformował właśni
IMG47 (2) Przykład 2 Układ regulacji automatycznej ma strukturę przedstawioną na rysunku. Regulator
Slajd7 4 Podatek VAT - przykład Załóżmy, że zakupiłeś materiały do produkcji za 10 000 zł netto, >

więcej podobnych podstron