Mealy-Automat - Automat mit Ausgabe
Abschnittsübersicht
-
-
Endliche Automaten mit Ausgabe
Beginnen wir mit der Suche nach einem Modell für eine universelle Maschine. Das von-Neumann-Modell beschreibt den Computer als universell einsetzbare Maschine. Dies kennen wir bereits aus Klasse 10. Darüber hinaus begleitet uns das EVA(S)-Prinzip seit Klasse 5: Informatiksysteme nehmen Eingaben entgegen, verarbeiten sie und erzeugen Ausgaben.
Gilt dies auch für Automaten? Sind Automaten ebenfalls universelle Maschinen?
Automaten begegnen uns beispielsweise als Geldautomaten, Parkscheinautomaten oder Getränkeautomaten. Auch sie nehmen Eingaben entgegen, verarbeiten diese abhängig von ihrem aktuellen Zustand und erzeugen Ausgaben. Solche Automaten lassen sich durch das Modell des endlichen Automaten mit Ausgabe (Mealy-Automat) beschreiben. Es geht auf die 1955 veröffentlichte Arbeit "A Method for Synthesizing Sequential Circuits" des US-amerikanischen Mathematikers George H. Mealy zurück.
Definition des Mealy-Automat
Ein Mealy-Automat MA = (X, Y, Z, δ, λ, z~0~) 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, die jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
- λ ... Ausgabefunktion, die jedem Paar (Eingabezeichen, Zustand) genau ein Ausgabezeichen zuordnet
- z0 ∈ Z ist der Anfangszustand
Aufbau eines Funktionsmodells
Arbeitsweise des Funktionsmodells
- SOLANGE noch ungelesene Zeichen auf dem Eingabeband vorhanden sind:
- liest das aktuelle Zeichen vom Eingabeband
- wechselt in Abhängigkeit vom aktuellen Zustand und vom gelesenen Zeichen in einen Folgezustand und schreibt ein Zeichen auf das Ausgabeband
- bewege das Eingabe- und Ausgabeband um eine Zelle weiter
-
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 nimmt der Automat nicht an. 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 entgegennehmen, also für obiges Beispiel statt 18 - 24 - 12 - 14 die Form 1 - 8 - 2 - 4 - ...
-