imported>Orthographus: \colon

2020-06-05T10:10:45Z

\colon

Neue Seite

Ein '''Transduktor''' ist in der [[Theoretische Informatik|theoretischen Informatik]] ein spezieller [[endlicher Automat]]. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem [[Akzeptor (Informatik)|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 [[Endlicher Automat|endliche Automaten]], die im Unterschied zu
[[Akzeptor (Informatik)|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 (Mathematik)|Alphabet]] <math>\{a,b,c,d,e,x\}</math> basierenden Transduktor, der jedes Vorkommen von <math>ab</math> in einer Eingabe[[zeichenkette]] durch ein einzelnes <math>x</math> in der Ausgabe ersetzt. Für die Eingabe <math>acabd</math> beispielsweise wird <math>acxd</math> 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 [[Leeres Wort|leere Wort]] <math>\varepsilon</math> ausgegeben.

[[Datei:Transduktor Informatik1.png|rechts|miniatur|200px|Abb. 1: Transduktor, der ''ab'' durch ''x'' ersetzt]]
[[Datei:Transduktor Informatik3.png|rechts|miniatur|300px|Abb. 2: Nichtdeterministischer Transduktor]]
[[Datei:Transduktor Informatik4.png|rechts|miniatur|400px|Abb. 3: Deterministische Version des Transduktors aus Abb. 2]]
[[Datei:Transduktor Informatik2.png|rechts|miniatur|200px|Abb. 4: Nichtdeterminisierbarer Transduktor]]

=== Mathematische Definition ===
Ein Transduktor ist ein 7-[[Tupel]] <math>(Q, \Sigma, \Gamma, q_0, \delta,F, \omega) </math>, wobei:

* <math>Q</math> ist eine endliche Menge von Zuständen,
* <math>\Sigma</math> ist das [[Alphabet (Mathematik)|Eingabealphabet]] (eine endliche, nicht-leere Menge von Symbolen),
* <math>\Gamma</math> ist das [[Alphabet (Mathematik)|Ausgabealphabet]] (eine endliche, nicht-leere Menge von Symbolen),
* <math>q_0\in Q</math> ist der Anfangszustand und ein Element aus <math>Q</math>,
* <math>\delta</math> ist die [[Zustandsübergangsfunktion]] <math>\delta\colon Q \times \Sigma \cup \{\varepsilon\} \to 2^Q</math>,
* <math>F</math> ist eine endliche Menge von Endzuständen (<math>F \subseteq Q</math>),
* <math>\omega</math> ist die Ausgabefunktion <math>\omega\colon Q \times \Sigma \cup \{\varepsilon\} \times Q \to \Gamma^*</math>.

Die Übergangsfunktion <math>\delta</math> ist diejenige eines [[Nichtdeterminismus|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 [[Determinismus (Algorithmus)|deterministisch]], lässt sich die Übergangsfunktion folgendermaßen definieren:

<math>\delta\colon Q \times \Sigma \to Q</math>.

Die Ausgabefunktion vereinfacht sich im deterministischen Fall zu
<math>\omega\colon Q \times \Sigma \to \Gamma^*</math>.

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

=== Algebraische Operationen ===

Die Menge der endlichen Transduktoren ist abgeschlossen unter folgenden Operationen:

* [[Konkatenation (Formale Sprache)|Verkettung]]: Sind <math>T_1</math> und <math>T_2</math> Transduktoren, so ist auch <math>T_1 \cdot T_2</math> ein Transduktor.
* [[Mengenlehre#Vereinigungsmenge|Vereinigung]]
* [[Kleene-Stern|Stern]]- und Plus[[Hüllenoperator|hüllenbildung]]
* Umkehrung
* Invertierung: Vertauschen von Ein- und Ausgabeband.
* [[Komposition (Mathematik)|Komposition]]

Unter [[Schnittmenge|Schnitt]] sind nur [[Graph (Graphentheorie)#Gerichteter azyklischer Graph|azyklische]] Transduktoren oder solche, die keine <math>\varepsilon</math>:x bzw.
x:<math>\varepsilon</math>-Übergänge besitzen, abgeschlossen.

Nicht abgeschlossen sind Transduktoren unter:

* [[Komplement (Mengenlehre)|Komplementierung]]
* [[Mengenlehre#Differenz und Komplement|Differenz]]

Ferner gibt es einige Optimierungsoperationen für Transduktoren:

* Entfernung von <math>\varepsilon</math>:<math>\varepsilon</math>-Ü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 <math>\Sigma^* \to \Gamma^*</math> 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 [[Äquivalenzproblem]]s (s. u.)
* Eine Teilklasse der Transduktoren erlaubt äquivalente [[Deterministischer endlicher Automat#Minimierung|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äre Relation|regulären Relationen]]. Vgl. auch [[Formale Sprache]]n, [[Chomsky-Hierarchie]].

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

===== Mathematische Definition =====
Ein <math>p</math>-subsequentieller Transduktor ist ein 8-Tupel <math>(Q, \Sigma, \Gamma, q_0, \delta, F, \omega, \varphi)</math>, wobei:

* <math>Q</math> ist eine endliche Menge von Zuständen,
* <math>\Sigma</math> ist das [[Alphabet (Mathematik)|Eingabealphabet]] (eine endliche, nicht-leere Menge von Symbolen),
* <math>\Gamma</math> ist das [[Alphabet (Mathematik)|Ausgabealphabet]] (eine endliche, nicht-leere Menge von Symbolen),
* <math>q_0 \in Q</math> ist der Anfangszustand,
* <math>\delta</math> ist die Zustandsübergangsfunktion <math>\delta \colon Q \times \Sigma \to Q</math>,
* <math>F \subseteq Q</math> ist eine endliche Menge von Endzuständen,
* <math>\omega</math> ist die Ausgabefunktion <math>\omega \colon Q \times \Sigma \to \Gamma^*</math>,
* <math>\varphi</math> ist die Endausgabefunktion <math>\varphi \colon F \to {(\Gamma^*)}^p</math>.

Die Endausgabefunktion <math>\varphi</math> gibt bis zu <math>p</math> verschiedene Strings an den Endzuständen aus,
dabei ist <math>p</math> die finite Anzahl der [[Ambiger Transduktor|Ambiguitäten eines Transduktors]].

Ein Algorithmus zur Determinisierung ist der von [[Algorithmus von Mohri|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 (Algebraische Struktur)|Halbring]] <math>\mathbb{K}</math> stammen.

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

* <math>Q,\Sigma,\Gamma, F</math> wie oben,
* <math>I\subseteq Q</math> ist eine Menge von Anfangszuständen,
* <math>\Delta</math> ist die Relation <math>\Delta \colon Q \times (\Sigma \cup \{\varepsilon\})\times (\Gamma\cup\{\varepsilon\}) \times \mathbb{K}\times Q</math>,
* <math>\lambda</math> ist die Gewichtsfunktion <math>\lambda \colon I \to \mathbb{K}</math>, die den Anfangszuständen Gewichte zuweist,
* <math>\rho</math> ist die Gewichtsfunktion <math>\rho \colon F \to \mathbb{K}</math>, 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 (Computerlinguistik)|Morphologische Analyse]]
* Robuste [[Parsing|syntaktische Analyse]]
* [[Datenkompression]]
* [[Kodierung]]

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

== Siehe auch ==
* [[Akzeptor (Informatik)|Akzeptor]]
* [[Compiler]]
* [[Kellerautomat]]
* [[Parser]]

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Automatentheorie]]

Transduktor (Informatik) - Versionsgeschichte

imported>Orthographus: \colon