13.2.4 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.

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.

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".

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).