Transduktor / Mealy-Automat

Definition: Transduktor

Ein deterministischer endlicher Automat mit Ausgabe (Transduktor) ist ein 6-Tupel $A:= ( X , Y , Z , \delta , \lambda , z_o)$, wobei gilt: X ist eine nicht leere, endliche Menge, das Eingabealphabet, wobei gilt: $x \in X$ Y ist eine nicht leere, endliche Menge, das Ausgabealphabet, wobei gilt: $y \in Y$ Z ist eine nicht leere, endliche Menge, die Zustandsmenge, wobei gilt: $z \in Z$ $\delta$ ist die Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) einen Folgezustand zuordnet: $\delta : X \times Z \to z$ $\lambda$ ist eine Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) ein Ausgabewort zuordnet: $\lambda: X \times Z \to Y^*$ $z_0$ ist der Anfangszustand: $z_0 \in Z$

Bemerkungen

• ein $x \in X$ heißt Eingabezeichen
• ein $y \in Y$ heißt Ausgabezeichen
• ein $z \in Z$ heißt Zustand
• $Y^*$ ist die Menge aller kombinierbaren Worte über Y (endliche Folge aus Zeichen von Y; mit dem leeren Wort $\epsilon$)

Anschauliche Darstellung

Mealy-Automat

Mealy-Automaten sind eingeschränkte Transduktoren, während Transduktoren Zeichenfolge in der Ausgabefunktion zulässt, erlaubt ein Mealy-Automat nur ein einzelnes Ausgabezeichen:

Definition: Mealy-Automat

Ein endlicher Automat (Transduktor) ist ein 6-Tupel $A:= ( X , Y , Z , \delta , \lambda , z_o)$, wobei gilt: X ist eine nicht leere, endliche Menge, das Eingabealphabet, wobei gilt: $x \in X$ Y ist eine nicht leere, endliche Menge, das Ausgabealphabet, wobei gilt: $y \in Y$ Z ist eine nicht leere, endliche Menge, die Zustandsmenge, wobei gilt: $z \in Z$ $\delta$ ist die Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) einen Folgezustand zuordnet: $\delta : X \times Z \to z$ $\lambda$ ist eine Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) ein Ausgabezeichen zuordnet: $\lambda: X \times Z \to Y$ $z_0$ ist der Anfangszustand: $z_0 \in Z$