Transduktor (Informatik)
aus Wikipedia, der freien Enzyklopädie
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.
Inhaltsverzeichnis |
[Bearbeiten] 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 muss. 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.
[Bearbeiten] Mathematische Definition
Ein Transduktor ist ein 7-Tupel < Q, Σ, Γ, q0, δ,F, ω >, wobei:
- Q ist eine endliche Menge von Zuständen,
- Σ ist das Eingabealphabet (eine endliche, nicht-leere Menge von Symbolen),
- Γ ist das Ausgabealphabet (eine endliche, nicht-leere Menge von Symbolen),
- q0 ist der Anfangszustand und ein Element aus Q,
- δ ist die Zustandsübergangsfunktion: δ: Q x Σ ∪ {ε} → 2Q,
- F ist eine endliche Menge von Endzuständen ( F ⊆ Q)
- ω ist die Ausgabefunktion ω: Q x Σ ∪ {ε} x Q → Γ*.
Die Übergangsfunktion δ 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 Übergangsfunktion 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 Σ → Γ*.
Oft werden Übergangs- und Ausgabefunktion auch zu einer Übergangsrelation T ⊆ Q x (Σ ∪ {ε}) x Γ* x Q zusammengefasst.
[Bearbeiten] Algebraische Operationen
Die Menge der endlichen Transduktoren ist abgeschlossen unter folgenden Operationen:
- Verkettung: Sind T1 und T2 Transduktoren, so ist auch T1 ⋅ T2 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 ε:x bzw. x:ε-Übergänge besitzen, abgeschlossen.
Nicht abgeschlossen sind Transduktoren unter:
Ferner gibt es einige Optimierungsoperationen für Transduktoren:
- Entfernung von ε:ε-Ü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 dienigen, die eine Funktion Σ* → Γ* 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 soweit wie möglich in Richtung Startzustand. Durch Pushing in Verbindung mit Determinisierung kann eine eindeutige Normalform hergestellt werden.
[Bearbeiten] Korrespondierende Sprachklasse
Die zu endlichen Transduktoren korrespondierende Sprachklasse umfasst die sog. regulären Relationen. Vgl. auch Formale Sprachen , Chomsky-Hierarchie.
[Bearbeiten] Erweiterungen
[Bearbeiten] p-Subsequentielle Transduktoren
Die Überführung eines Transduktors in einen p-subsequentiellen Transduktor wird determinisierung genannt. Dabei werden die Ausgaben verzögert und durch eine zusätzliche Endausgabefunktion φ an den Enzuständen ausgegeben, p entspricht der Anzahl der Ausgaben. Sollte p = 0 sein, spricht man von einen sequentiellen Transduktor. Alle azyklischen Transduktoren lassen sich in einen p-Subsequentiellen umwandeln. Bei einem zyklischen Transduktor kann die Determinierbarkeit mit Hilfe der „twins Property“ festgestellt werden.
[Bearbeiten] Mathematische Definition
Ein p-subsequentieller Transduktor ist ein 8-Tupel < Q, Σ, Γ, q0, δ, F, ω, φ >, wobei:
- Q ist eine endliche Menge von Zuständen,
- Σ ist das Eingabealphabet (eine endliche, nicht-leere Menge von Symbolen),
- Γ ist das Ausgabealphabet (eine endliche, nicht-leere Menge von Symbolen),
- q0 ⊆ Q ist der Anfangszustand,
- δ ist die Zustandsübergangsfunktion: δ: Q x Σ → Q,
- F ⊆ Q ist eine endliche Menge von Endzuständen
- ω ist die Ausgabefunktion ω: Q x Σ x Q → Γ*.
- φ ist die Endausgabefunktion φ: F → (Γ*)p
Die Endausgabefunktion φ gibt bis zu p-verschiedene Strings an den Endzuständen aus, dabei ist p die finite Anzahl der Ambiguitäten eines Transduktors.
Ein Algorithmus zur determinisierung ist der von Mohri.
[Bearbeiten] Verwendung von Gewichten
[Bearbeiten] Anwendungen
[Bearbeiten] Siehe auch
[Bearbeiten] Kellertransduktor
| Dieser Artikel oder Abschnitt bedarf einer Überarbeitung. Näheres ist auf der Diskussionsseite angegeben. Hilf bitte mit ihn zu verbessern und entferne anschließend diese Markierung. |
