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, Q, W, q0, R, δ, γ> 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 γ: Q !W
– funkcja wyjścia
δ i γ – określone dla wszystkich elementów swoich dziedzin
Automat Moore'a
q←q0
konfiguracja początkowa:
$ a ...
$ a ...
we
q0q0
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
stop
stan
q←δ(q,a)
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, Q, W, q0, R, δ, γ> T = {a, b}
Q = {A, B, D}
W = {0,1}
q0 = A
R = {1}
δ:
γ:
stan
a b
stan wy
we
A 0
A A B
B 0
B A D
D
1
D A D
symbole zapisywane na taśmie wy
stan w następnym takcie
B/0
b
a
a
odpowiadające
A/0
mu wyjście
b
a
D/1
b
Słowo analizowane: aababbb
$ aababbb$
$a ababbb$
$a a babbb$
$aa babbb$
$aab a bbb$
A
! A
! A
!
B
!
A
ε
0
00
000
0000
$aaba bbb$
$aabab b b$
$aababb b $
$aababbb$
!
B
!
D
!
D !
⋅
00000
000000
0000001
00000011
tu już nie wyznaczamy nowego
stanu
1∈R ⇒ aababbb∈L(AMoore)
Automat zupełny i deterministyczny Mealy’ego A= <T, Q, W, q0, R, δ, γ>
T – alfabet terminalny (wejściowy) Q – zbiór stanów
W – alfabet wyjściowy
R – podzbiór alfabetu wyjściowego q0 – stan początkowy
δ: Q × T ! Q – funkcja przejścia γ: Q × T ! W – funkcja wyjścia
δ i γ – określone dla wszystkich elementów swoich dziedzin Automat Mealy’ego nie akceptuje słowa pustego (ε). Dowodzi się, że automat Mealy’ego jest równoważny automatowi Moore’a (z wyjątkiem akceptacji słowa pustego). Dowodzi się dalej, że automat Moore’a jest równoważny deterministycznemu automatowi Rabina-Scotta.
Wszystkie te automaty akceptują wyłącznie języki regularne. Wszystkie czytają słowo wejściowe do końca (są deterministyczne i zupełne). Decyzja o akceptacji zależy od ostatniego zapisanego na taśmie wyjściowej symbolu (aut. Moore’a i Mealy) lub od stanu, w którym automat zatrzyma się (aut. Rabina-Scotta).
start
Mealy'ego
q←q0
konfiguracja początkowa:
$ a ...
$ a ...
we
q0q0
wy
czytaj a∈T U{$} z taśmy
wejściowej
a=$
a=$
zapisz γ(q,a) na
stop
taśmie wy
wyznacz nowy
stan
q←δ(q,a)
przesuń obie
głowice: we i wy o
1 klatkę w prawo
Słowo wejściowe jest akceptowane przez automat Mealy’ego, gdy ostatni zapisany na taśmie wyjściowej symbol należy do R i słowo zostało przeczytane do końca. Automat Mealy’ego NIE akceptuje słowa pustego (nic wtedy nie pisze na taśmie wyjściowej).
Przykład:
AMealy = <T, Q, W, q0, R, δ, γ> T = {a, b}
δ:
γ:
Q = {A, B}
stan
a b
stan
a b
W = {0,1}
we
we
q0 = A
A
A B
A
0 0
R = {1}
B
A B
B
0
1
stan w następnym
symbole zapisywane
takcie
na taśmie wy
a/0
b/1
b/0
A
B
a/0
$ a abbabb$
$a a bbabb$
$aa b babb$
$aabbabb$
$aabba bb$
A
! A
!
A
!
B
!
B
ε
0
00
000
0001
$aabba b b$
$aabbabb$
$aabbabb$
!
A !
B !
B
00010
000100
0001001
1∈R ⇒ aabbabb∈L(A)
Przekształcenie AMoore → AMealy
We: AMoore = <T, Q, W, q0, R, δ, γ> ε∉L(AMoore)
Wy: AMealy = <T, Q, W, q0, R, δ, γ’> takie,
że: L(AMealy) = L(AMoore)
Funkcje przejścia bez zmian.
Funkcja wyjścia: (∀α∈T) (∀q∈Q) (γ’(q,a) = γ(δ(q,a))) Przykład:
T = {a,b}, Q = {A, B, C, D}, q0 = A, W = {0, 1}, R = {1}
A. MOORE’A
A. MEALY
δ:
δ:
γ:
γ:
akt Nast.
akt
Nast. stan /
.
stan Wy
.
wyjści
sta a b
sta
a b
n
n
A D B 0
A
D / 0
B / 1
B A C 1
B
A / 0
C / 1
C B D 1
C
B / 1
D / 0
D C A 0
D
C / 1
A / 0
a
A/0
B/1
a/0
b
A
B
b/1
a
b
b
a
a/0
b/0
b/1
a/1
b
D/0
C/1
b/0
a
D
C
a/1
Przekształcenie AMealy → AMoore We: AMealy = <T, Q, W, q0, R, δ, γ> Wy: AMoore = <T, Q’, W, q0’, R, δ’, γ’> takie,
że: L(AMoore) = L(AMealy)
1. Numerujemy stany i symbole terminalne Q = {q0, q1, ..., qn}
T = {a1, ..., am.}
2. Każdej parze [qi, aj] przypisujemy nowy stan Sij∈Q’
Sij = [qi, aj] qi∈Q, i = 0,...,n aj∈T, j = 1,...,m.
3. Stanowi q0 dodatkowo przypisujemy nowy stan S0∈Q’
4. Tworzymy nową funkcję przejść δ’(Sij, ak) = [δ(qi, aj), ak]
δ’(S0, ak) = [q0, ak] = S0k
5. Tworzymy nową funkcję przejść γ’(Sij) = γ(qi, aj)
γ’(S0) – dowolne (nieokreślone)
Mamy:
Q’ = {Sij : i = 0,...,n; j = 1,...,m.}∪{S0}
q0’ = S0
δ’ i γ’ zdefiniowane jak wyżej
Przykład:
T = {a, b}, Q = {A, B}, W = {0, 1}, q0 = A, R = {1}
A. MEALY’EGO
δ:
γ:
akt.
nowy stan / wy
stan
a b
A
A / 0
B / 0
a/0
a/0
B
B / 0
B / 1
b/0
A
B
tablica kodowania nowych znaków
b/1
1
2
a
b
A/S0
A / S01
B / S02
B
B / S11
B / S12
a
a
δ’:
γ’:
S /0
S /0
01
11
akt.
nast. stan
wy
stan
a b
a
S0
S01
S02
dow.
b
a
b
a
S
S0
01
S01
S02
0
S02
S11
S12 0
b
S11
S11
S12
0
S
b
12
S11
S12
1
S /0
S /1
02
12
b
Przekształcenia AMoore ↔ determinist. ARabina-Scotta
(i) We: AMoore = <T, Q, W, q0, R, δ, γ> Wy:
ARabina-Scotta = <T, Q, F, q0, δ> - deterministyczny F := {q∈Q : γ(q)∈R};
T, Q, q0, δ - bez zmian
(ii) We: ARabina-Scotta = <T, Q, F, q0, δ> - deterministyczny Wy:
AMoore = <T, Q, W, q0, R, δ, γ> L(ARabian-Scotta) = L(AMoore)
W := {ω0, ω1};
for q∈Q\F do γ(q) := ω0;
for q∈F do γ(q) := ω1;
R := {ω1};
T, Q, q0, δ - bez zmian
δ:
γ:
δ:
a b wy
a b
A
B D 0
A
B D
B
C A 1
⇔
B
C A
C
D B 0
C
D B
D
A C 1
D
A C
R = {1}
Moore
Rabina-Scotta F = {B, D}