Sie sind hier:

Mealy-Automaten (neu im BP: Item 7)

Die sogenannten Mealy-Automaten gelten als besonders anschaulich: Sie können in jedem Schritt außer der Änderung des internen Zustands auch eine Ausgabe erzeugen⁴ und erlauben damit die Modellierung z.B. von Getränke-, Fahrkarten- oder ähnlichen Automaten, was für den Unterricht eine sprachliche Parallele zwischen Automaten des Alltags und der Automatentheorie erlaubt.

Abbildung 1: Mealy-Getränkeautomat, der Cola, Apfelsaft bzw. nicht verbrauchtes Guthaben ausgibt. ZPG Informatik [CC BY-SA 4.0 DE], aus zpg_sprachenautomaten_hintergrund.odt

Als Beispiel⁵ soll ein Getränkeautomat dienen, der die Tasten A, C und S hat (für Apfelsaft, Cola und Stop) und Münzen à €1 und €2 annimmt, so dass die Menge der „Zeichen“ {C, A, S, 1, 2} sein Alphabet, also die möglichen Eingaben darstellt. Die Abbildung zeigt einen solchen Automaten in Form eines anschaulichen (Zustands-)Übergangsgraphen⁶. Der Automat befindet sich immer in genau einem der runden Zustände; anfangs ist es für Schüler hilfreich, ihn als Spielplan anzusehen, auf dem man „mit einer Spielfigur Züge macht“. Der Automat beginnt immer im Startzustand, der mit einem zusätzlichen Pfeil (hier Dreieck) „von links“ markiert wird. Jede Eingabe bewirkt einen „Zug“ (Übergang oder Transition genannt, dargestellt durch einen Pfeil zu einem anderen Zustand) und bei Mealy-Automaten auch eine Ausgabe.

Der Übergang „C; Colaflasche“ wird beispielsweise durchlaufen, wenn der Automat im Zustand q1 ist und dort die Eingabe „C“ erhält; dabei gibt er eine Colaflasche aus und wechselt in den Zustand q0.

Der obige Graph ist allerdings unvollständig: Auch im Zustand q2 könnte der Kunde ja die a-Taste drücken, aber der Graph zeigt nicht, was der Automat dann tun soll. Per Konvention gibt es daher in jedem Übergangsgraphen einen weiteren, unsichtbaren „Fehler“zustand, zu dem grundsätzlich alle „fehlenden“ Transitionen hinführen; zugunsten der Übersicht werden aber weder der Fehlerzustand, noch die Übergange dorthin eingezeichnet. Eine weitere Konvention besagt, dass der Automat aus dem Fehlerzustand nie (durch keine Eingabe) wieder herauskommt.

Oft wird im Unterricht und auch in Klausuren wegen der Anschaulichkeit nur der Übergangsgraph verwendet. Zu einer formal korrekten, vollständigen, insbesondere maschinenlesbaren Beschreibung⁷ des Automaten gehören aber weitere Angaben:

… allgemein:	… im Beispiel:
das Eingabealphabet ∑_E	∑_E = {S, C, A, 1, 2} dessen Elemente hier für die „Knöpfe“ Stop, Cola, Apfelsaft bzw. den Einwurf von Münzen à €1 und €2 stehen.
eine Menge ℚ von Zuständen	ℚ ={q0, q1, q2}
der Startzustand	s = q0
das Ausgabealphabet ∑_A	∑_A = {Apfelsaftflasche, Colaflasche, €1 Rückgeld, €2 Rückgeld, „Guthaben €1“, „Guthaben €2“}

sowie eine Funktion für Übergänge und eine für die Ausgaben, die jeweils als Tabelle oder als Graph angegeben werden können:

Übergangsfunktion δ: ℚ⊗ ∑_E → ℚ
Eingabe → alter Zust. ↓	s	a	c	1	2
q0	q0	qF	qF	q2	q1
q1	q0	q0	q0	qF	qF
q2	q0	qF	qF	q1	qF
qF	qF	qF	qF	qF	qF

Ausgabefunktion λ: ℚ⊗ ∑_E → ∑_A
Eingabe → alter Zust. ↓	s	a	c	1	2
q0	-	-	-	„Guthaben €1“	“Guthaben €2“
q1	€2 Rückgeld	Apfelsaftflasche	Colaflasche	-	-
q2	€1 Rückgeld	-	-	“Guthaben €2“	-
qF	-	-	-	-	-

Die Darstellungen könnten vereinfacht auch in einer einzigen Tabelle zusammengefasst werden, die dann in der gleichen Zelle jeweils den neuen Zustand und die Ausgabe vereint.

Vor allem die Tabellen erfordern im Unterricht eine genaue Erklärung und etwas Übung⁸ : Die eine Achse ist mit den Zuständen, die andere mit den Zeichen des Eingabealphabets beschriftet. Für jede Kombination aus altem Zustand und Eingabe enthält die Tabelle den neuen Zustand bzw. (bei Mealy-Automaten) die Ausgabe, die beim Zustandsübergang erfolgen soll.

Auch wenn man im Graphen auf den Fehlerzustand qF und die Transitionen dorthin verzichtet, sollte qF bei der Darstellung als Tabelle berücksichtigt werden: Damit wird nämlich deutlich, dass der Übergangsgraph eher für einen menschlichen Betrachter gedacht ist, der sich qF „hinzudenkt“ und von einem übersichtlicheren Diagramm profitiert; die Tabelle hingegen soll einer Maschine die vollautomatische Simulation des DEA erlauben und muss dafür vollständig sein.

Die vierte Zeile der Übergangstabelle sorgt dafür, dass der Automat den Fehlerzustand nicht wieder verlassen kann. Dieses Verhalten ist für einen realen Getränkeautomaten natürlich nicht erwünscht, für eine einfache Modellierung aber oft vorteilhaft.

Didaktischer Tipp: Wichtige Grundvorstellungen für alle Typen von Automaten

Ob der Unterrichtsgang nun mit Mealy- oder anderen Automaten beginnt – in jedem Fall sollten die Schüler beim Umgang mit Automaten vor allem folgende Grundvorstellungen entwickeln:

Automaten bestehen aus diskreten Zuständen.
Auch die Eingabe besteht aus diskreten Zeichen (oder „Ereignissen“) eines festen Alphabets.
Die Eingabe „steuert“ den Automaten zwischen den Zuständen.
Ähnlich wie ein Programm benötigt der Automat weder Intuition noch Überblick: Er „weiß“ nicht, welche Eingaben später noch folgen, und auch nicht, wie der Graph insgesamt aussieht, sondern trifft alle Entscheidungen lokal, sofort und nach einfachen Regeln.
Der Ablauf wird nicht vom Zufall beeinflusst, sondern ist vollkommen deterministisch.
Das in der Informatik allgegenwärtige EVA-(Eingabe-Verarbeitung-Ausgabe)-Prinzip ist bei Automaten besonders klar und offensichtlich. Es bietet sich an, es bei dieser Gelegenheit nochmals zu besprechen (bzw. einzuführen).

⁴ Bei einem weiteren Typ, den sogenannten Moore-Automaten, steht die Ausgabe nicht an den Transitionen, sondern in den Zuständen. Moore-Automaten produzieren also beim Erreichen eines bestimmten Zustands immer die gleiche, zu diesem Zustand gehörige Ausgabe (und nicht beim Durchlaufen einer bestimmten Transition).

⁵ Die Automaten in diesem Dokument wurden mit der sehr empfehlenswerten Software JFLAP (https://www.jflap.org/jflaptmp/) konstruiert. Sie erlaubt nicht nur das Zeichnen des Graphen, sondern auch die Simulation des Automaten mit vorgegebenen Eingaben und kann sogar zwischen verschiedenen äquivalenten Darstellungen umwandeln, etwa einen Automaten in eine Grammatik, einen regulären Ausdruck umwandeln usw. Eine ebenfalls empfehlenswerte Alternative dazu ist der „Exorciser“ (https://www.swisseduc.ch/informatik/exorciser/).

⁶ Die Bezeichnungen Übergangs- oder Transitionsdiagramm sind ebenfalls üblich.

⁷ Diese Beschreibung wird im schriftlichen Abitur auch verlangt.

⁸ Umwandlungen von Graph zu Tabelle und umgekehrt sind Standardaufgaben im schriftlichen Abitur.

Hintergrundinformationen: Herunterladen [odt][669 KB]

Weiter zu Deterministische endliche Automaten DEA