Transduktor (Informatik)

Grundidee und Arbeitsweise

Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat, der im Gegensatz zu einem Akzeptor nicht nur Eingaben verarbeitet, sondern zusätzlich eine Ausgabe erzeugt. Er überführt eine Quellsprache in eine Zielsprache. Je nach den formalen Eigenschaften der betrachteten Sprachen gibt es verschiedene Untertypen.

Ein endlicher Transduktor besitzt Zustände, liest Symbole eines Eingabeworts und erzeugt dabei Wörter über einem Ausgabealphabet. Die Ausgabe kann an Übergänge und an Endzustände des Automaten gebunden sein. Dadurch können Eingaben übersetzt, Zeichen ersetzt oder Ausgaben unterschiedlich verzögert erzeugt werden.

Ein Beispiel ersetzt jedes Vorkommen von „ab“ durch ein einzelnes „x“. Für die Eingabe „acab d“ ohne Leerzeichen, also „acabd“, lautet die Ausgabe „acxd“. Liest der Transduktor im Zustand 1 ein „a“, kann er dafür ein „x“ ausgeben und in den Zustand 2 wechseln. Zustand 2 ist kein Endzustand, weil anschließend noch ein „b“ gelesen werden muss. Da „ab“ aus zwei Zeichen besteht, „x“ aber nur aus einem, wird beim Übergang von Zustand 2 nach Zustand 0 beim Lesen von „b“ das leere Wort ε ausgegeben.

Formale Beschreibung und Determinismus

Ein Transduktor ist ein 7-Tupel (Q, Σ, Γ, q₀, δ, F, ω) mit folgenden Bestandteilen:

• Q ist eine endliche Menge von Zuständen.
• Σ ist das Eingabealphabet, also eine endliche, nicht-leere Menge von Symbolen.
• Γ ist das Ausgabealphabet, ebenfalls eine endliche, nicht-leere Menge von Symbolen.
• q₀ ∈ Q ist der Anfangszustand.
• δ ist die Zustandsübergangsfunktion δ: Q × (Σ ∪ {ε}) → 2^Q.
• F ⊆ Q ist eine endliche Menge von Endzuständen.
• ω ist die Ausgabefunktion ω: Q × (Σ ∪ {ε}) × Q → Γ*.

Die Funktion δ gehört in dieser allgemeinen Definition zu einem nichtdeterministischen endlichen Transduktor. Beim Lesen eines Symbols a im Zustand q kann der Automat daher prinzipiell in mehrere Folgezustände übergehen. ε bezeichnet das leere Wort beziehungsweise einen Übergang, bei dem kein Eingabesymbol gelesen wird. Γ* ist die Menge aller endlichen Wörter über dem Ausgabealphabet.

Bei einem deterministischen Transduktor wird δ zu δ: Q × Σ → Q vereinfacht. Die Ausgabefunktion lautet dann ω: Q × Σ → Γ*. Übergangs- und Ausgabefunktion können außerdem zu einer Übergangsrelation Δ zusammengefasst werden: Δ ⊆ Q × (Σ ∪ {ε}) × Γ* × Q.

Die Determinisierung des Eingabebands ist jedoch nicht immer möglich. Nicht alle Transduktoren, auch nicht alle Transduktoren, die eine Funktion Σ* → Γ* realisieren, lassen sich determinisieren. Ein Transduktor kann insbesondere durch ε-Übergänge im strengen Sinne nichtdeterministisch bleiben. Diese Eigenschaft unterscheidet endliche Transduktoren von endlichen Automaten und wirkt sich auf die Entscheidbarkeit des Äquivalenzproblems aus.

Operationen und Sprachklasse

Die Menge der endlichen Transduktoren ist unter mehreren algebraischen Operationen abgeschlossen. Sind T₁ und T₂ Transduktoren, ist auch ihre Verkettung T₁ · T₂ ein Transduktor. Weitere abgeschlossene Operationen sind Vereinigung, Stern- und Plushüllenbildung, Umkehrung, Invertierung und Komposition. Bei der Invertierung werden Ein- und Ausgabeband vertauscht.

Unter dem Schnitt sind nur azyklische Transduktoren oder Transduktoren abgeschlossen, die keine ε:x- beziehungsweise x:ε-Übergänge besitzen. Unter Komplementierung und Differenz sind Transduktoren dagegen nicht abgeschlossen.

Für die Optimierung gibt es verschiedene Verfahren:

• ε:ε-Übergänge können entfernt werden.
• Das Eingabeband kann determinisiert werden, soweit dies möglich ist.
• Für eine Teilklasse der Transduktoren existieren äquivalente minimale Varianten.
• Beim Pushing werden Ausgabesymbole so weit wie möglich in Richtung des Startzustands verschoben. Zusammen mit der Determinisierung kann dadurch eine eindeutige Normalform entstehen.

Die zu endlichen Transduktoren korrespondierende Sprachklasse umfasst die regulären Relationen. Eine reguläre Relation beschreibt dabei die durch einen endlichen Transduktor hergestellte Beziehung zwischen Eingaben und Ausgaben.

P-subsequentielle und gewichtete Transduktoren

Die Überführung eines Transduktors in einen p-subsequentiellen Transduktor wird Determinisierung genannt. Dabei werden Ausgaben verzögert und an den Endzuständen mithilfe einer zusätzlichen Endausgabefunktion φ erzeugt. Die Zahl p entspricht der Maximalanzahl der Ausgaben. Für p = 1 spricht man von einem sequentiellen Transduktor. Sind bei einem sequentiellen Transduktor alle Zustände Endzustände, heißt er subsequentiell.

Alle azyklischen Transduktoren lassen sich in äquivalente p-subsequentielle Transduktoren überführen, wobei Äquivalenz bedeutet, dass dieselbe String-Funktion realisiert wird. Bei einem zyklischen Transduktor kann die Determinierbarkeit mithilfe der „Twins Property“ festgestellt werden. Ein Algorithmus zur Determinisierung ist der von Mohri.

Ein p-subsequentieller Transduktor ist ein 8-Tupel (Q, Σ, Γ, q₀, δ, F, ω, φ). Zusätzlich zur Grundstruktur gilt:

• δ: Q × Σ → Q,
• ω: Q × Σ → Γ*,
• φ: F → (Γ*)^p.

Die Endausgabefunktion φ gibt an den Endzuständen bis zu p verschiedene Strings aus. p ist dabei die finite Anzahl der Ambiguitäten eines Transduktors.

Ein gewichteter endlicher Transduktor besitzt zusätzlich eine Gewichtsfunktion, die den Transitionen Werte aus einem beliebigen Halbring K zuweist. Er wird als 8-Tupel (Q, Σ, Γ, I, Δ, F, λ, ρ) beschrieben. I ⊆ Q ist die Menge der Anfangszustände, Δ die Relation Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) × K × Q, λ: I → K weist Anfangszuständen Gewichte zu, und ρ: F → K weist Endzuständen Gewichte zu. In der Sprachsynthese können Gewichte beispielsweise unterschiedlich wahrscheinliche Aussprachemöglichkeiten für ein Eingabezeichen kennzeichnen. Die Wahrscheinlichkeiten können durch maschinelles Lernen ermittelt werden.

Anwendungen und Kellertransduktoren

Endliche Transduktoren werden unter anderem für folgende Aufgaben eingesetzt:

• morphologische Analyse,
• robuste syntaktische Analyse,
• Datenkompression,
• Kodierung.

Ein Kellertransduktor ist ein LR-Parser zu einer gegebenen kontextfreien Grammatik. Er ist damit ein Kellerautomat, der zusätzlich eine Ausgabe erzeugt.