Transduktor
Definition: Transduktor
Ein deterministischer endlicher Automat mit Ausgabe (Transduktor) ist ein 6-Tupel {A := ( X, Y, Z, \delta, \lambda, z_0 )}, 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 \rightarrow z}
– \lambda ist eine Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) ein Ausgabewort zuordnet: {\lambda : X \times Z \rightarrow Y^{*}}
– {z_0 \in Z} ist der Anfangszustand
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)
- die verwendeten Zeichen für die einzelnen Bestandteile eines Transduktors können (je nach Literatur) abweichen, häufig findet man z. B. auch: {A := ( Q, \Sigma, \Gamma, \delta, \omega, q_0 )}
- Transduktoren besitzen in der Regel keine Endzustände, in manchen Definitionen sind diese jedoch angegeben.
Anschauliche Darstellung
Das Eingabeband wird zeichenweise (von links nach rechts) gelesen. Mit Hilfe des Eingabezeichens und des aktuellen Zustandes wird ein Folgezustand eingestellt und ein Ausgabezeichen auf das Ausgabenband geschrieben.
Mealy-Automat
Mealy-Automaten sind eingeschränkte Transduktoren. Während Transduktoren Zeichenfolgen in der Ausgabefunktion zulassen, erlaubt ein Mealy-Automat nur ein einzelnes Ausgabezeichen.
Definition: Mealy-Automat
Ein deterministischer endlicher Automat mit Ausgabe (Transduktor; Mealy-Automat) ist ein 6-Tupel {A := ( X, Y, Z, \delta, \lambda, z_0 )}, 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 \rightarrow z}
– \lambda ist eine Ausgabefunktion, welche jedem Paar (Eingabezeichen, Zustand) ein Ausgabewort zuordnet: {\lambda : X \times Z \rightarrow Y}
– z_0 ist der Anfangszustand: {z_0 \in Z}
