Ereignisse als Input

Ein Automat kommuniziert mit der Umgebung über seine Bänder. Die Ereignisse zu jedem Zeitpunkt bilden die Ereignismenge für eine Zelle. Der Output ist der Task, der aktuell ausgeführt wird.

Figure 12.5: Endlicher Automat mit Input und Output

Die formale Definition eines endlichen Input-Output Automaten -auch Mooreautomat genannt- lautet normalerweise:

$$FA_{MOORE}(x) iff x=\langle Q, I, F, \Sigma, \Xi, \Delta, \Lambda \rangle$$ (12.1)

$$I,F \subseteq Q$$ (12.2)

$$\Delta \subseteq Q \times \Sigma \times Q$$ (12.3)

$$\Lambda \subseteq Q \times \Xi$$ (12.4)

mit den Bedeutungen:

1. $Q$ := Endliche Menge von Zuständen
2. $I \subseteq Q$ := Menge von Startzuständen
3. $F \subseteq Q$ := Menge von Endzuständen
4. $\Sigma$ := Endliche Menge von Zeichen als Input Alphabet
5. $\Xi$ := Endliche Menge von Zeichen als Output Alphabet
6. $\Delta \subseteq Q \times \Sigma \times Q$ := Menge von Übergängen
7. $\Lambda \subseteq Q \times \Xi$ := Menge von Ausgaben

Figure 12.6: Inputereignisse aus dem Beispiel

Versucht man, diese Definition des Automaten auf die Inputereignisse anzuwenden, dann stellt man schnell fest, dass (i) diese Definition zusammengesetzte Inputereignisse nicht zuläßt, und dass (ii) im Falle von zusammengesetzten Inputereignissen der Automat mehr als einen Übergang pro Befehlszeile zulassen muss. D.h. Der Automat ist nicht deterministisch. Man müsste die Definition also erweitern zu

$$NFA_{MOORE}(x) iff x=\langle Q, I, F, \Sigma, \Xi, \Delta, \Lambda \rangle$$ (12.5)

$$I,F \subseteq Q$$ (12.6)

$$\Delta : Q \times \Sigma^{*} \longmapsto 2^{Q}$$ (12.7)

$$\Lambda : Q \longmapsto Xi$$ (12.8)