To tylko jedna z 7 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
4.5 Deterministyczne i zupełne automaty Moore’a i
Mealy’ego
Automaty Moore’a i Mealy’ego będziemy rozważać tylko w wersji deterministycznej i
zupełnej. W definicjach tych automatów nie pojawia się pojęcie stanów końcowych, za to
mamy taśmę wyjściową, na którą automat zapisuje symbole z alfabetu wyjściowe (to jest
nowa kategoria). Po przeczytaniu całego słowa analizowany jest ostatni symbol zapisany na
taśmie wyjściowej. Jeżeli jest to symbol należący do pewnego podzbioru R alfabetu
wyjściowego, uznajemy wówczas, że słowo zostało zaakceptowane. Jeśli ostatni zapisany na
taśmie wyjściowej symbol nie należy do podzbioru R, to uważamy, że słowo nie zostało
zaakceptowane. Automat Moore’a wpisuje symbole na taśmę wyjściową przy każdorazowym
ustaleniu stanu (także pisze na wyjście w stanie początkowym), więc potrafi zaakceptować
lub odrzucić słowo puste, gdyż przy pustym wejściu zapisywany jest jakiś symbol na taśmę
wyjściową. Automat Mealy’ego robi zapisy na wyjściu tylko podczas kroku, tzn. podczas
przejścia z jednego stanu do drugiego, co w automacie deterministycznym jest związane z
przeczytaniem symbolu z wejścia. Wobec tego nie jest w stanie zaakceptować bądź odrzucić
słowa pustego, ponieważ nie wykonując czytania z pustego wejścia nie ma możliwości
zapisania czegokolwiek na wyjściu. Ogólny schemat omawianych automatów jest ilustruje
poniższy przykładowy rysunek:
taśma wejściowa
$ a b b a a a b a b a $
q∈Q
δ,γ
taśma wyjściowa
0 1 1 0 1
Automat zupełny i deterministyczny Moore’a
A =
T – alfabet terminalny (wejściowy)
Q – zbiór stanów
W – alfabet wyjściowy
q0∈Q – stan początkowy
R ⊂ W – podzbiór alfabetu wyjściowego
δ: Q × T ! Q – funkcja przejścia
– funkcja wyjścia
γ: Q !W
δ i γ – określone dla wszystkich elementów swoich dziedzin
start
Automat Moore'a
q←q0
konfiguracja początkowa:
$ ...
$ aa ...
we
qq0
0
wy
zapis γ(q) na taśmie
wyjściowej
przesuń obie głowice: we i
wy o 1 klatkę w prawo
czytaj a∈T U{$} z taśmy
wejściowej
a=$
a=$
wyznacz nowy
stan
q←δ(q,a)
stop
Słowo wejściowe jest akceptowane przez automat Moore'a, gdy ostatni zapisany na taśmie
wyjściowej symbol należy do R i słowo zostało przeczytane do końca
Przykład:
AMoore =
T = {a, b}
Q = {A, B, D}
W = {0,1}
q0 = A
R = {1}
δ:
stan
we
a
b
A
A
B
B
A
D
D
A
D
stan w następnym takcie
γ:
stan wy
A
0
B
0
D
1
symbole zapisywane
na
taśmie
wy
stan
B/0
b
odpowiadające
mu wyjście
a
a
b
A/0
D/1
b
a
Słowo analizowane: aababbb
$ a a b a b b b $
$ a a b a b b b$
$a a b a b b b$
$ a a b a b b b$
$ a a b a b b b$
A
! A
! A
!
!
B
A
ε
0
0 0
0 00
0 0 0 0
$ a a b a b b b$
$ a a b a b b b$
$a a b a b b b $
$a a b a b b b$
!
B
!
D !
D !
⋅
0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
tu już nie wyznaczamy nowego
stanu
1∈R ⇒ aababbb∈L(AMoore)
Automat zupełny i deterministyczny Mealy’ego
A=
T – alfabet terminalny
... zobacz całą notatkę
Komentarze użytkowników (0)