Transduktor (Informatik)

Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Akzeptor eine Ausgabe erzeugt. Er überführt (übersetzt) eine Quellsprache in eine Zielsprache. 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 im Unterschied zu Akzeptoren 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 ${\displaystyle \{a,b,c,d,e,x\}}$ basierenden Transduktor, der jedes Vorkommen von ${\displaystyle ab}$ in einer Eingabezeichenkette durch ein einzelnes ${\displaystyle x}$ in der Ausgabe ersetzt. Für die Eingabe ${\displaystyle acabd}$ beispielsweise wird ${\displaystyle acxd}$ ausgegeben. 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 muss. Da im Beispiel das zu Ersetzende und das Ersetzte unterschiedlich lang sind, wird beim Übergang von 2 nach 0 beim Lesen von b das leere Wort ${\displaystyle \varepsilon }$ ausgegeben.

Abb. 1: Transduktor, der ab durch x ersetzt

Abb. 2: Nichtdeterministischer Transduktor

Abb. 3: Deterministische Version des Transduktors aus Abb. 2

Abb. 4: Nichtdeterminisierbarer Transduktor

Mathematische Definition

Ein Transduktor ist ein 7-Tupel ${\displaystyle (Q,\Sigma ,\Gamma ,q_{0},\delta ,F,\omega )}$, wobei:

• ${\displaystyle Q}$ ist eine endliche Menge von Zuständen,
• ${\displaystyle \Sigma }$ ist das Eingabealphabet (eine endliche, nicht-leere Menge von Symbolen),
• ${\displaystyle \Gamma }$ ist das Ausgabealphabet (eine endliche, nicht-leere Menge von Symbolen),
• ${\displaystyle q_{0}\in Q}$ ist der Anfangszustand und ein Element aus ${\displaystyle Q}$,
• ${\displaystyle \delta }$ ist die Zustandsübergangsfunktion ${\displaystyle \delta \colon Q\times \Sigma \cup \{\varepsilon \}\to 2^{Q}}$,
• ${\displaystyle F}$ ist eine endliche Menge von Endzuständen (${\displaystyle F\subseteq Q}$),
• ${\displaystyle \omega }$ ist die Ausgabefunktion ${\displaystyle \omega \colon Q\times \Sigma \cup \{\varepsilon \}\times Q\to \Gamma ^{*}}$.

Die Übergangsfunktion ${\displaystyle \delta }$ 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, lässt sich die Übergangsfunktion folgendermaßen definieren:

${\displaystyle \delta \colon Q\times \Sigma \to Q}$.

Die Ausgabefunktion vereinfacht sich im deterministischen Fall zu ${\displaystyle \omega \colon Q\times \Sigma \to \Gamma ^{*}}$.

Oft werden Übergangs- und Ausgabefunktion auch zu einer Übergangsrelation ${\displaystyle \Delta }$ mit ${\displaystyle \Delta \subseteq Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma ^{*}\times Q}$ zusammengefasst.

Algebraische Operationen

Die Menge der endlichen Transduktoren ist abgeschlossen unter folgenden Operationen:

• Verkettung: Sind ${\displaystyle T_{1}}$ und ${\displaystyle T_{2}}$ Transduktoren, so ist auch ${\displaystyle T_{1}\cdot T_{2}}$ ein Transduktor.
• Vereinigung
• Stern- und Plushüllenbildung
• Umkehrung
• Invertierung: Vertauschen von Ein- und Ausgabeband.
• Komposition

Unter Schnitt sind nur azyklische Transduktoren oder solche, die keine ${\displaystyle \varepsilon }$:x bzw. x:${\displaystyle \varepsilon }$-Übergänge besitzen, abgeschlossen.

Nicht abgeschlossen sind Transduktoren unter:

• Komplementierung
• Differenz

Ferner gibt es einige Optimierungsoperationen für Transduktoren:

• Entfernung von ${\displaystyle \varepsilon }$:${\displaystyle \varepsilon }$-Übergängen
• Determinisierung des Eingabebands des Transduktors. Abb. 3 zeigt die deterministische Variante des Transduktors aus Abb. 2 (zu beachten ist, dass dieser Transduktor im strengen Sinne durch seine Epsilon-Übergänge nicht deterministisch ist. Vgl. Subsequentielle Transduktoren). Allerdings können nicht alle Transduktoren, noch nicht mal diejenigen, die eine Funktion ${\displaystyle \Sigma ^{*}\to \Gamma ^{*}}$ realisieren, determinisiert werden. Abb. 4 zeigt einen nicht determinisierbaren Transduktor. Dies unterscheidet endliche Transduktoren von endlichen Automaten und hat Konsequenzen für die Entscheidbarkeit des Äquivalenzproblems (s. u.)
• Eine Teilklasse der Transduktoren erlaubt äquivalente minimale Varianten.
• Pushing: Verschieben von Ausgabesymbolen so weit wie möglich in Richtung Startzustand. Durch Pushing in Verbindung mit Determinisierung kann eine eindeutige Normalform hergestellt werden.

Korrespondierende Sprachklasse

Die zu endlichen Transduktoren korrespondierende Sprachklasse umfasst die sog. regulären Relationen. Vgl. auch Formale Sprachen, Chomsky-Hierarchie.

Erweiterungen

P-subsequentielle Transduktoren

Die Überführung eines Transduktors in einen ${\displaystyle p}$-subsequentiellen Transduktor wird Determinisierung genannt. Dabei werden die Ausgaben verzögert und durch eine zusätzliche Endausgabefunktion ${\displaystyle \varphi }$ an den Endzuständen ausgegeben, ${\displaystyle p}$ entspricht hierbei der Maximalanzahl der Ausgaben. Sollte ${\displaystyle p=1}$ sein, spricht man von einem sequentiellen Transduktor. Ein sequentieller Transduktor, bei dem alle Zustände auch Endzustände sind, heißt auch subsequentiell. Alle azyklischen Transduktoren lassen sich in äquivalente (im Sinne der realisierten String-Funktion) ${\displaystyle p}$-subsequentielle Transduktoren überführen. Bei einem zyklischen Transduktor kann die Determinierbarkeit mit Hilfe der „Twins Property“ festgestellt werden.

Mathematische Definition

Ein ${\displaystyle p}$-subsequentieller Transduktor ist ein 8-Tupel ${\displaystyle (Q,\Sigma ,\Gamma ,q_{0},\delta ,F,\omega ,\varphi )}$, wobei:

• ${\displaystyle Q}$ ist eine endliche Menge von Zuständen,
• ${\displaystyle \Sigma }$ ist das Eingabealphabet (eine endliche, nicht-leere Menge von Symbolen),
• ${\displaystyle \Gamma }$ ist das Ausgabealphabet (eine endliche, nicht-leere Menge von Symbolen),
• ${\displaystyle q_{0}\in Q}$ ist der Anfangszustand,
• ${\displaystyle \delta }$ ist die Zustandsübergangsfunktion ${\displaystyle \delta \colon Q\times \Sigma \to Q}$,
• ${\displaystyle F\subseteq Q}$ ist eine endliche Menge von Endzuständen,
• ${\displaystyle \omega }$ ist die Ausgabefunktion ${\displaystyle \omega \colon Q\times \Sigma \to \Gamma ^{*}}$,
• ${\displaystyle \varphi }$ ist die Endausgabefunktion ${\displaystyle \varphi \colon F\to {(\Gamma ^{*})}^{p}}$.

Die Endausgabefunktion ${\displaystyle \varphi }$ gibt bis zu ${\displaystyle p}$ verschiedene Strings an den Endzuständen aus, dabei ist ${\displaystyle p}$ die finite Anzahl der Ambiguitäten eines Transduktors.

Ein Algorithmus zur Determinisierung ist der von Mohri.

Verwendung von Gewichten

Ein gewichteter endlicher Transduktor ist ein Transduktor, der um eine Gewichtsfunktion erweitert wurde, die den Transitionen Werte zuweist. Diese Werte können aus einem beliebigen Halbring ${\displaystyle \mathbb {K} }$ stammen.

Fasst man wie oben Übergangs- und Ausgabefunktion und dazu die Gewichtsfunktion zu einer Relation zusammen, ist ein gewichteter Transduktor über einem Halbring ${\displaystyle \mathbb {K} }$ ein 8-Tupel ${\displaystyle (Q,\Sigma ,\Gamma ,I,\Delta ,F,\lambda ,\rho )}$, wobei

• ${\displaystyle Q,\Sigma ,\Gamma ,F}$ wie oben,
• ${\displaystyle I\subseteq Q}$ ist eine Menge von Anfangszuständen,
• ${\displaystyle \Delta }$ ist die Relation ${\displaystyle \Delta \colon Q\times (\Sigma \cup \{\varepsilon \})\times (\Gamma \cup \{\varepsilon \})\times \mathbb {K} \times Q}$,
• ${\displaystyle \lambda }$ ist die Gewichtsfunktion ${\displaystyle \lambda \colon I\to \mathbb {K} }$, die den Anfangszuständen Gewichte zuweist,
• ${\displaystyle \rho }$ ist die Gewichtsfunktion ${\displaystyle \rho \colon F\to \mathbb {K} }$, die den Endzuständen Gewichte zuweist.

Die Gewichte können beispielsweise in der Sprachsynthese dazu verwendet werden, für ein Eingabezeichen verschiedene Aussprachemöglichkeiten anzubieten, die unterschiedlich wahrscheinlich sind. Die Wahrscheinlichkeiten können zum Beispiel durch maschinelles Lernen ermittelt werden.

Anwendungen

• Morphologische Analyse
• Robuste syntaktische Analyse
• Datenkompression
• Kodierung

Kellertransduktor

Ein Kellertransduktor ist ein LR-Parser zu einer gegebenen kontextfreien Grammatik, also ein Kellerautomat, der eine Ausgabe erzeugt.

Siehe auch

• Akzeptor
• Compiler
• Kellerautomat
• Parser