Transduktor (Informatik)
Das Wort Transduktor bezeichnet in der theoretischen Informatik ganz allgemein Automaten, die eine Quellsprache in eine Zielsprache überführen (übersetzen). Da die formalen Eigenschaften dieser Sprachen variieren können, unterscheidet man verschiedene Untertypen, die im folgenden näher beschrieben werden.
Endlicher Transduktor
Endliche Transduktoren sind endliche Automaten, die zusätzlich eine Ausgabefunktion besitzen. Diese Funktion ist in der klassischen Definition mit den Übergängen und den Endzuständen des Automaten verknüpft. Abbildung 1 zeigt einen auf dem Alphabet {a,b,c,d,e,x} basierenden Transduktor, der jedes Vorkommen von ab in einer Zeichenkette durch ein einzelnes x ersetzt. Aus acabd beispielsweise wird acxd. Im Zustand 1 kann der Transduktor beispielsweise ein a lesen, dafür ein x ausgeben und in den Zustand 2 übergehen. Zustand 2 ist kein Endzustand, da ja nun ein b gelesen werden muß. Da im Beispielfall das zu Ersetzende und das Ersetzte unterschiedlich lang sind, wird beim Übergang von 2 nach 0 beim Lesen von b das leere Wort ε ausgegeben.
Mathematische Definition
Ein Transduktor ist ein 6-Tupel < Σ, Γ, Q, q0, δ, ω >, wobei:
- Σ ist das Eingabealphabet (eine endliche nicht leere Menge von Symbolen),
- Γ ist das Ausgabealphabet (eine endliche nicht leere Menge von Symbolen),
- Q ist eine endliche Menge von Zuständen,
- q0 ist der Anfangszustand und ein Element aus Q,
- δ ist die Zustandsübergangsfunktion: δ: Q x Σ ∪ {ε} → 2Q,
- ω ist die Ausgabefunktion.
Die Ausgabefunktion δ ist diejenige eines nichtdeterministischen endlichen Transduktors, d.h. der Transduktor kann beim Lesen eines Symbols a im Zustand q prinzipiell in mehrere Folgezustände übergehen. Ist der Transduktor hingegen deterministisch, sieht die Ausgabefunktion folgendermaßen aus:
δ: Q x Σ → Q.
Die Ausgabefunktion ist im nichtdeterministischen Fall durch
ω: Q x Σ ∪ {ε} x Q → Γ*
gegeben. Bei der deterministischen Variante vereinfacht sie sich zu
ω: Q x Σ → Γ*
Algebraische Operationen
Korrespondierende Sprachklasse
Die zu endlichen Transduktoren korrespondierende Sprachklasse umfasst die sog. regulären Relationen. Vgl. auch Formale Sprachen , Chomsky-Hierarchie.