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ądz
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
ł: Q W  funkcja wyjścia
� i ł  określone dla wszystkich elementów swoich dziedzin
start Automat Moore'a
q�!q0
konfiguracja początkowa:
$ a ...
$ a ...
we
q00
q
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 = {a, b}
Q = {A, B, D}
W = {0,1}
q0 = A
R = {1}
�: ł:
a b stan wy
stan
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
stan
B/0
odpowiadające
mu wyjście
A/0
D/1
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 b bb$ $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  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).
b
a
a
b
a
b
Automat
start
Mealy'ego
q�!q0
konfiguracja początkowa:
$ a ...
$ a ...
we
q00
q
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 = {a, b} ł:
�:
Q = {A, B}
a b a b
stan stan
we we
W = {0,1}
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
Słowo analizowane: aabbabb
�ł łł �ł łł �ł łł �ł łł �ł łł
$ a abbabb$ $a a bbabb$ $aa b babb$ $aab babb$ $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 =
� "L(AMoore)
Wy: AMealy =
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 . wyjści
Wy
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
ab b
b/1
a/0 b/0 a/1
b
D/0 C/1
b/0
a
D C
a/1
Przekształcenie AMealy AMoore
We: AMealy =
Wy: AMoore =
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/0 a/0
A A / 0 B / 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
A. MOORE A
� :
S01/0 S11/0
ł :
akt. nast. stan
wy
a
stan a b
S0 S01 S02 dow.
b a b
a
S0
S01 S01 S02 0
S02 S11 S12 0
b
S11 S11 S12 0
b
S12 S11 S12 1
S02/0 S12/1
b
Przekształcenia AMoore "! determinist. ARabina-Scotta
(i) We: AMoore =
Wy: ARabina-Scotta = - deterministyczny
F := {q"Q : ł(q)"R};
T, Q, q0, � - bez zmian
(ii) We: ARabina-Scotta = - deterministyczny
Wy: AMoore =
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
a b wy
A B D
A B D 0
�!
B C A
B C A 1
C D B
C D B 0
D A C
D A C 1
Rabina-Scotta F = {B, D}
R = {1} Moore