Mealy-Automat


Wenn bei einem endlichen Automaten das erste Zeichen des Eingabewortes verarbeitet wird, wechselt der Automat seinen Zustand. Wenn das Eingabewort vollständig abgearbeitet wurde und sich der Automat in einem Endzustand befindet, gibt der endliche Automat die Ausgabe "das Eingabewort wird akzeptiert" aus.

Wenn der endliche Automat sich nach der Verarbeitung des Eingabewortes nicht in einem Endzustand befindet, gibt der Automat die Ausgabe "das Eingabewort wird nicht akzeptiert" aus.

Damit kennt ein Deterministischer Endlicher Automat (DEA) nur zwei Ausgaben:

  • "das Eingabewort wird akzeptiert" und
  • "das Eingabewort wird nicht akzeptiert"

Man kann sich endliche Automaten denken, die neben der Eingabe bei jedem Übergang zu einem nächsten Zustand auch eine Ausgabe ausgeben. Einen solchen endlichen Automaten nennt man einen Mealy-Automaten.

Ein Mealy-Automat ist wie folgt definiert:

  • es gibt eine endliche Menge von Zuständen
  • genau einer der Zustände ist der Anfangszustand
  • es gibt ein Eingabealphabet mit endlich vielen Zeichen
  • es gibt ein Ausgabealphabet mit endlich vielen Zeichen
  • jedem möglichen Übergang von einem Zustand zu einem anderen Zustand ist eine eindeutige Kombination aus einem Zeichen des Eingabealphabets und einem Zeichen des Ausgabealphabets zugeordnet.

Mealy-Automaten

Folgender Automat ist ein Beispiel für einen Mealy-Automaten:

Mealy 1

Wenn man das Eingabewort "abaababba" dem Automaten übergibt, erhält man als Ausgabe die Zeichenfolge "010010110". Der Mealy-Automat ersetzt das Zeichen "a" mit dem Zeichen "0" und das Zeichen "b" mit dem Zeichen "1":

Mealy 2

Vollziehen Sie die Funktionsweise des Mealy-Automaten nach, indem Sie den Automaten in der Simulation mit dem Eingabewort "abaababba" starten: FLACI-Link:

Variieren Sie das Eingabewort.


Aufgabe 1: Zeichen-Verschiebung

Denken Sie sich einen Mealy-Automaten mit dem Eingabealphabet E = {a, b, c, d, e, f} aus, der bei einem gegebenen Eingabewort als Ausgabe die Buchstaben zyklisch (auf f folgt a) um einen Buchstaben nach rechts verschiebt.

Beispiel: Aus "affe" wird "baaf".

Mögliche Lösung: hier klicken...

A1.1 FLACI-Link:

Die Simulation liefert zum Eingabewort "affe" das Ausgabewort "baaf": A1.2


Aufgabe 2: Addition

Denken Sie sich einen Mealy-Automaten aus, der vier Zustände hat. Das Eingabealphabet sei E = {0, 1, 2, 3} und das Ausgabealphabet sei A = {0, 1, 2, 3, 4, 5, 6}. Der Mealy-Automat soll die zwei Ziffern des Eingabewortes addieren und die Summe ausgeben.

Beispiele: "13" liefert "4" (1 + 3 = 4), "30" liefert "3" (3 + 0 = 3).

Mögliche Lösung: hier klicken...

A2.1 FLACI-Link:

Die Simulation liefert zum Eingabewort "13" das Ausgabewort "4": A2.2

Die Simulation liefert zum Eingabewort "30" das Ausgabewort "3": A2.3


Überarbeiten ! und Lösung einstellen.

Aufgabe 3: Paritätsbit

In der Datenübertragung (zum Beispiel in einem Netzwerk) wird mit verschiedenen Mitteln versucht, Fehler in der Übertragung zu erkennen. Eine einfache Möglichkeit ist der Einsatz des so genannten Paritätsbits. Das Paritätsbit für eine Binärzahl ist 1, wenn die Anzahl der 1er ungerade ist, sonst ist das Paritätsbit 0. Ein Beispiel: 01100101 besitzt vier Einsen. Da 4 eine gerade Zahl ist, ist das Paritätsbit 0.