Mealy-Automat - Automat mit Ausgabe
Abschnittsübersicht
-
-
Endliche Automaten mit Ausgabe
Beginnen wir mit der Suche nach dem Modell für eine universelle Maschine. Das von-Neumann-Modell beschreibt den Computer als universelle Maschine. Dies wissen wir aus Klasse 10. Darüber hinaus kennen wir das EVA(S)-Prinzip bereits seit Klasse 5.
Sind Automaten auch universelle Maschinen? Wir finden sie z. B. in Form von Geldautomaten, Parkscheinautomaten, Getränkeautomaten oder Bonbon-Automaten. Solche Automaten lassen sich durch das Modell des endlichen Automaten mit Ausgabe (Mealy-Automat) beschreiben. Es geht auf die 1955 veröffentliche Arbeit "A Method for Synthesizing Sequential Circuits" des US-amerikanischer Mathematiker George H. Mealy zurück.
Definition des Mealy-Automat
Ein Mealy-Automat MA = (X, Y, Z, δ, λ, z0) ist ein endlicher Automat mit Ausgabe. Dabei gilt:
-
- X ... Eingabealphabet (nichtleere, endliche Menge)
- Y ... Ausgabealphabet (nichtleere, endliche Menge)
- Z ... Zustandsmenge (nichtleere, endliche Menge)
- δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
- λ ... Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) genau ein Ausgabezeichen zuordnet
- z0 ∈ Z ist der Anfangszustand
Aufbau eines Funktionsmodells
Arbeitsweise
- Der Automat liest ein Zeichen vom Eingabeband.
- In Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen wechselt der Automat in einen Folgezustand und gibt auf dem Ausgabeband ein Zeichen aus. Anschließend werden beide Bänder um eine Zelle weiter bewegt.
- Der Vorgang beginnt von vorn, solange noch ungelesene Zeichen auf dem Eingabeband sind.
-
-
Beispiel: Blumenstraußautomat
Ein Blumenstraußautomat bietet Blumensträuße für 4 EUR an. Der Kunde wirft 1- oder 2-Euro-Münzen ein und erhält die Blumen. Andere Münzwerte akzeptiert der Automat nicht. Zu viel gezahltes Geld wird nicht erstattet.
Der Blumenstraußautomat kann als Mealy-Automat MA = (X, Y, Z, δ, λ, q0) modelliert werden mit
- X = {1_EUR, 2_EUR}
- Y = {-, Blumen}
- Z = {q0, q1, q2, q3}
- δ, λ als Tabelle
oder als Graph
- q0
-
Der Mealy-Automat MA = (X, Y, Z, δ , λ , q0) simuliert ein Verschlüsselungsverfahren, das nur mit Ziffern als Eingabezeichen arbeitet. Die Abbildung zeigt den Graph der Überführungsfunktion.
- Geben Sie die Mengen X, Y und Z an.
- Verschlüsseln Sie die Zahlenfolge 0 - 8 - 1 - 5 und entschlüsseln Sie die Nachricht 18 - 24 - 12 - 14.
- Entwickeln Sie einen Automaten mit Ausgabe, der nach diesem Prinzip verschlüsselte Nachrichten entschlüsselt. Der Automat soll dabei die Eingabe ziffernweise entgegen nehmen, also für obiges Beispiel statt 18 - 24 - 12 - 14 die Form 1 - 8 - 2 - 4 - ...
-