Ein Moore-Automat ist ein Fünftupel A = (X, Y, Z, f, h)

I.1.3. Moore-Automaten
Definition: Ein Moore-Automat ist ein Fünftupel A = (X, Y, Z, f, h) mit nichtleeren
endlichen Mengen X, Y, Z und Abbildungen
f: Z x X Z
(X und Y mit der gleichen Bedingung wie
h: Z Y
beim Mealy-Automaten)
Beim Moore-Automaten ist die Ausgabefunktion nicht direkt von der
Eingabe abhängig.
Bei der Darstellung in Tabellenform benötigt man für die Darstellung von h nur eine
Spalte:
x2
z1
f(z1,x1)
z2
...
xn
h
f(z1,x2)
f(z1,xn)
h(z1)
f(z2,x1)
f(z2,x2)
f(z2,xn)
h(z2)
f(zk,x1)
f(zk,x2)
f(zk,xn)
h(zk)
...
x1
zk
Bei der Darstellung mittels gerichteter Graphen wird das Ausgabezeichen in die
Knotenbeschriftung einbezogen und die Kanten werden dem entsprechend nur mit
den Eingabezeichen beschriftet.
z.B.
1
z1|0
0
z3|1
1
z2|1
0
0
1
0
1
h
z1
z3
z2
0
z2
z4
z1
1
z3
z1
z4
z4
z4
z4
1
1
z4|1
0,1
mit
X = Y = {0,1},
Z = {z1, ... ,z4}
Arbeitsablauf gegenüber Mealy-Automaten modifiziert;
für jeden "durchlaufenen" Zustand wird das zugehörige Ausgabezeichen generiert.
1
Die Auffassung von der Arbeitsweise eines Moore-Automaten ist allerdings etwas
anders:
Anfangszustand z setzen
Auf Ausgabeband Zeichen y = h(z) schreiben
Lesekopf auf 1. Zeichen der Eingabe setzen
while
Feld unter Lesevorrichtung nicht leer do
Zeichen x unter Lesekopf setzen
Zustand z := f(z, x)
Ausgabeband um ein Feld weiterrücken
Auf Ausgabeband Zeichen y = h(z) schreiben
Eingabeband um 1 Feld weiterrücken.
Die Ausgabe erfolgt also nach Annahme des neuen Zustandes.
Insbesondere wird auch bei eingegebenem leerem Wort ε ein Zeichen ausgegeben,
und bei Eingabe eines Strings der Länge n hat der Ausgabestring die Länge n+1,
wobei das 1. Zeichen i.Allg. nicht relevant ist.
Z.B. ist beim obigen Automaten, wenn in z1 gestartet
Eingabe: ε
Ausgabe
0
Eingabe 0
Ausgabe
01
Eingabe 011
Ausgabe
0111
Dementsprechend ist also auch die erweiterte Ergebnisfunktion hier wie folgt zu
definieren: (vgl. Mealy-Automat g*)
h* : Z x X* Y*
h*(z, ε) = h(z),
h*(z, px) = h*(z, p) h(f*(z, px))
hz*
*
*
: X Y mit
hz*(p)
und
*
= h (z, p)
Alle Ergebnisse und Definitionen für Mealy-Automaten finden dann ihre
Entsprechung bei Moore-Automaten. Bei der Reduktion hat allerdings der
Algorithmus mit 0-äquivalenten Zuständen zu beginnen, d.h. mit Zuständen, die bei
2
Eingabe von ε die gleiche Ausgabe erzeugen, d.h. die Zustände mit gleichen
Ausgaben sind für Π0 zusammenzufassen.
o
z1 ~ z2
g.d.w.
h(z1) = h(z2)
Zusammenhang von Meal y- und Moore-Automaten
Wegen der verschiedenen Längen der Ausgabestrings bei gleichem Eingabestring
bei Moore- und Mealy-Automaten kann ein Moore-Automat nicht zu einem MealyAutomat äquivalent sein.
Es stört dabei das (redundante) 1. ausgegebene Zeichen.
Deshalb (Idee: 1. Zeichen weglassen):
Definition: Die beschränkte Leistung eines Zustandes z eines Moore-Automaten A
(wie oben) h ∗z ist definiert
h*(z, ε) hz∗ ( p ) = hz∗ (p) ∀p ∈ X ∗
(d.h. h ∗ ( z , p) ist h ∗ ( z , p) , wobei das 1. Zeichen gestrichen wird).
Definition: Der Mealy-Automat A1 = (X, Y, Z1, f1, g1) und der Moore-Automat
A2 = (X, Y, Z2, f2, h2) heißen gleichwertig, wenn die Menge der
Leistungen von A1 mit der Menge der beschränkten Leistungen von A2
übereinstimmt.
Offenbar gibt es zu jedem Moore-Automaten A = (X, Y, Z, f, h) einen
gleichwertigen Mealy-Automaten A' = (X, Y, Z', f', g').
Anschaulich: Der Graph von A geht in den von A' über, indem jeder Teil
z1y1
x
z1
x | y2
z2y2
ersetzt wird durch
3
z2
Formal:
Z' := Z, f' := f, g'(z, x) = h (f (z, x))
Beispiel: . . .
[Umkehrung möglich?
Ja, aber die Konstruktion lässt sich nicht unmittelbar umkehren.
Man braucht mehr Zustände.]
Also sind in diesem Sinne Moore-Automaten spezielle Mealy-Automaten!
FRAGE:
Können Mealy-Automaten echt mehr leisten?
ANTWORT: Nein!
Satz 1.4.:
Zu jedem Mealy-Automaten A = (X, Y, Z, f, g) gibt es einen
gleichwertigen Moore-Automaten A' = (X, Y, Z', f', h').
Beweis:
Z' := Z x Y;
∀ x ∈ X , y ∈Y , z ∈ Z
f'((z, y),x) := ( f(z,x), g(z,x))
h'((z, y)) := y
Sei y0 ∈ Y beliebig. Es genügt zu zeigen, dass
(#)
g * (z, p ) = h '
∗
((z, y 0 ), p )
∀ p ∈ X* , ∀ z ∈ Z
Sei p = xi1 xi2 ... xi r ∈ X*
Man hat
z
xi1|yt1
zj1
xi2|yt2
...
zj2.....
xir|ytr
zj r
= f*(z,p)
mit g* (z, p) = yt1 ... yt r.
Nach Definition von f' und h' wird:
xi1
xi2
(zj1,yt1)yt1
(z,y0)y
0
in A', d. h. h'* ((z, y0), p) = y0yt1 …ytr.
Beispiel:
(zj2,yt2)yt2
Mausefalle ohne Speck:
m| t
z
m|t
z
m t
m t
4
...
xir
(zjr,ytr)ytr
Es wird
m
(z1, t)t
m
(z2, t)t
m, m
m
(z1, t ) t
(z2, t ) t
m, m
m
5

Download Report