www.wikidata.de-de.nina.az

Transduktor Informatik Ein Transduktor ist in der theoretischen Informatik ein spezieller endlicher Automat Er zeichnet

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 Bearbeiten

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 basierenden Transduktor, der jedes Vorkommen von in einer Eingabezeichenkette durch ein einzelnes in der Ausgabe ersetzt. Für die Eingabe beispielsweise wird 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 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 Bearbeiten

Ein Transduktor ist ein 7-Tupel , wobei:

  • 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),
  • ist der Anfangszustand und ein Element aus ,
  • ist die Zustandsübergangsfunktion ,
  • ist eine endliche Menge von Endzuständen (),
  • ist die Ausgabefunktion .

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, lässt sich die Übergangsfunktion folgendermaßen definieren:

.

Die Ausgabefunktion vereinfacht sich im deterministischen Fall zu .

Oft werden Übergangs- und Ausgabefunktion auch zu einer Übergangsrelation mit zusammengefasst.

Algebraische Operationen Bearbeiten

Die Menge der endlichen Transduktoren ist abgeschlossen unter folgenden Operationen:

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 diejenigen, 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 so weit wie möglich in Richtung Startzustand. Durch Pushing in Verbindung mit Determinisierung kann eine eindeutige Normalform hergestellt werden.

Korrespondierende Sprachklasse Bearbeiten

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

Erweiterungen Bearbeiten

P-subsequentielle Transduktoren Bearbeiten

Die Überführung eines Transduktors in einen -subsequentiellen Transduktor wird Determinisierung genannt. Dabei werden die Ausgaben verzögert und durch eine zusätzliche Endausgabefunktion an den Endzuständen ausgegeben, entspricht hierbei der Maximalanzahl der Ausgaben. Sollte 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) -subsequentielle Transduktoren überführen. Bei einem zyklischen Transduktor kann die Determinierbarkeit mit Hilfe der „Twins Property“ festgestellt werden.

Mathematische Definition Bearbeiten

Ein -subsequentieller Transduktor ist ein 8-Tupel , wobei:

  • 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),
  • ist der Anfangszustand,
  • ist die Zustandsübergangsfunktion ,
  • ist eine endliche Menge von Endzuständen,
  • ist die Ausgabefunktion ,
  • ist die Endausgabefunktion .

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

Ein Algorithmus zur Determinisierung ist der von Mohri.

Verwendung von Gewichten Bearbeiten

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 stammen.

Fasst man wie oben Übergangs- und Ausgabefunktion und dazu die Gewichtsfunktion zu einer Relation zusammen, ist ein gewichteter Transduktor über einem Halbring ein 8-Tupel , wobei

  • wie oben,
  • ist eine Menge von Anfangszuständen,
  • ist die Relation ,
  • ist die Gewichtsfunktion , die den Anfangszuständen Gewichte zuweist,
  • ist die Gewichtsfunktion , 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 Bearbeiten

Kellertransduktor Bearbeiten

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

Siehe auch Bearbeiten

wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 uberfuhrt ubersetzt eine Quellsprache in eine Zielsprache Da die formalen Eigenschaften dieser Sprachen variieren konnen unterscheidet man verschiedene Untertypen die im Folgenden naher beschrieben werden Inhaltsverzeichnis 1 Endlicher Transduktor 1 1 Mathematische Definition 1 2 Algebraische Operationen 1 3 Korrespondierende Sprachklasse 1 4 Erweiterungen 1 4 1 P subsequentielle Transduktoren 1 4 1 1 Mathematische Definition 1 4 2 Verwendung von Gewichten 1 5 Anwendungen 2 Kellertransduktor 3 Siehe auchEndlicher Transduktor BearbeitenEndliche Transduktoren sind endliche Automaten die im Unterschied zu Akzeptoren zusatzlich eine Ausgabefunktion besitzen Diese Funktion ist in der klassischen Definition mit den Ubergangen und den Endzustanden des Automaten verknupft Abbildung 1 zeigt einen auf dem Alphabet a b c d e x displaystyle a b c d e x nbsp basierenden Transduktor der jedes Vorkommen von a b displaystyle ab nbsp in einer Eingabezeichenkette durch ein einzelnes x displaystyle x nbsp in der Ausgabe ersetzt Fur die Eingabe a c a b d displaystyle acabd nbsp beispielsweise wird a c x d displaystyle acxd nbsp ausgegeben Im Zustand 1 kann der Transduktor beispielsweise ein a lesen dafur ein x ausgeben und in den Zustand 2 ubergehen 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 Ubergang von 2 nach 0 beim Lesen von b das leere Wort e displaystyle varepsilon nbsp ausgegeben nbsp Abb 1 Transduktor der ab durch x ersetzt nbsp Abb 2 Nichtdeterministischer Transduktor nbsp Abb 3 Deterministische Version des Transduktors aus Abb 2 nbsp Abb 4 Nichtdeterminisierbarer TransduktorMathematische Definition Bearbeiten Ein Transduktor ist ein 7 Tupel Q S G q 0 d F w displaystyle Q Sigma Gamma q 0 delta F omega nbsp wobei Q displaystyle Q nbsp ist eine endliche Menge von Zustanden S displaystyle Sigma nbsp ist das Eingabealphabet eine endliche nicht leere Menge von Symbolen G displaystyle Gamma nbsp ist das Ausgabealphabet eine endliche nicht leere Menge von Symbolen q 0 Q displaystyle q 0 in Q nbsp ist der Anfangszustand und ein Element aus Q displaystyle Q nbsp d displaystyle delta nbsp ist die Zustandsubergangsfunktion d Q S e 2 Q displaystyle delta colon Q times Sigma cup varepsilon to 2 Q nbsp F displaystyle F nbsp ist eine endliche Menge von Endzustanden F Q displaystyle F subseteq Q nbsp w displaystyle omega nbsp ist die Ausgabefunktion w Q S e Q G displaystyle omega colon Q times Sigma cup varepsilon times Q to Gamma nbsp Die Ubergangsfunktion d displaystyle delta nbsp ist diejenige eines nichtdeterministischen endlichen Transduktors d h der Transduktor kann beim Lesen eines Symbols a im Zustand q prinzipiell in mehrere Folgezustande ubergehen Ist der Transduktor hingegen deterministisch lasst sich die Ubergangsfunktion folgendermassen definieren d Q S Q displaystyle delta colon Q times Sigma to Q nbsp Die Ausgabefunktion vereinfacht sich im deterministischen Fall zu w Q S G displaystyle omega colon Q times Sigma to Gamma nbsp Oft werden Ubergangs und Ausgabefunktion auch zu einer Ubergangsrelation D displaystyle Delta nbsp mit D Q S e G Q displaystyle Delta subseteq Q times Sigma cup varepsilon times Gamma times Q nbsp zusammengefasst Algebraische Operationen Bearbeiten Die Menge der endlichen Transduktoren ist abgeschlossen unter folgenden Operationen Verkettung Sind T 1 displaystyle T 1 nbsp und T 2 displaystyle T 2 nbsp Transduktoren so ist auch T 1 T 2 displaystyle T 1 cdot T 2 nbsp ein Transduktor Vereinigung Stern und Plushullenbildung Umkehrung Invertierung Vertauschen von Ein und Ausgabeband KompositionUnter Schnitt sind nur azyklische Transduktoren oder solche die keine e displaystyle varepsilon nbsp x bzw x e displaystyle varepsilon nbsp Ubergange besitzen abgeschlossen Nicht abgeschlossen sind Transduktoren unter Komplementierung DifferenzFerner gibt es einige Optimierungsoperationen fur Transduktoren Entfernung von e displaystyle varepsilon nbsp e displaystyle varepsilon nbsp Ubergangen 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 Ubergange nicht deterministisch ist Vgl Subsequentielle Transduktoren Allerdings konnen nicht alle Transduktoren noch nicht mal diejenigen die eine Funktion S G displaystyle Sigma to Gamma nbsp realisieren determinisiert werden Abb 4 zeigt einen nicht determinisierbaren Transduktor Dies unterscheidet endliche Transduktoren von endlichen Automaten und hat Konsequenzen fur die Entscheidbarkeit des Aquivalenzproblems s u Eine Teilklasse der Transduktoren erlaubt aquivalente minimale Varianten Pushing Verschieben von Ausgabesymbolen so weit wie moglich in Richtung Startzustand Durch Pushing in Verbindung mit Determinisierung kann eine eindeutige Normalform hergestellt werden Korrespondierende Sprachklasse Bearbeiten Die zu endlichen Transduktoren korrespondierende Sprachklasse umfasst die sog regularen Relationen Vgl auch Formale Sprachen Chomsky Hierarchie Erweiterungen Bearbeiten P subsequentielle Transduktoren Bearbeiten Die Uberfuhrung eines Transduktors in einen p displaystyle p nbsp subsequentiellen Transduktor wird Determinisierung genannt Dabei werden die Ausgaben verzogert und durch eine zusatzliche Endausgabefunktion f displaystyle varphi nbsp an den Endzustanden ausgegeben p displaystyle p nbsp entspricht hierbei der Maximalanzahl der Ausgaben Sollte p 1 displaystyle p 1 nbsp sein spricht man von einem sequentiellen Transduktor Ein sequentieller Transduktor bei dem alle Zustande auch Endzustande sind heisst auch subsequentiell Alle azyklischen Transduktoren lassen sich in aquivalente im Sinne der realisierten String Funktion p displaystyle p nbsp subsequentielle Transduktoren uberfuhren Bei einem zyklischen Transduktor kann die Determinierbarkeit mit Hilfe der Twins Property festgestellt werden Mathematische Definition Bearbeiten Ein p displaystyle p nbsp subsequentieller Transduktor ist ein 8 Tupel Q S G q 0 d F w f displaystyle Q Sigma Gamma q 0 delta F omega varphi nbsp wobei Q displaystyle Q nbsp ist eine endliche Menge von Zustanden S displaystyle Sigma nbsp ist das Eingabealphabet eine endliche nicht leere Menge von Symbolen G displaystyle Gamma nbsp ist das Ausgabealphabet eine endliche nicht leere Menge von Symbolen q 0 Q displaystyle q 0 in Q nbsp ist der Anfangszustand d displaystyle delta nbsp ist die Zustandsubergangsfunktion d Q S Q displaystyle delta colon Q times Sigma to Q nbsp F Q displaystyle F subseteq Q nbsp ist eine endliche Menge von Endzustanden w displaystyle omega nbsp ist die Ausgabefunktion w Q S G displaystyle omega colon Q times Sigma to Gamma nbsp f displaystyle varphi nbsp ist die Endausgabefunktion f F G p displaystyle varphi colon F to Gamma p nbsp Die Endausgabefunktion f displaystyle varphi nbsp gibt bis zu p displaystyle p nbsp verschiedene Strings an den Endzustanden aus dabei ist p displaystyle p nbsp die finite Anzahl der Ambiguitaten eines Transduktors Ein Algorithmus zur Determinisierung ist der von Mohri Verwendung von Gewichten Bearbeiten Ein gewichteter endlicher Transduktor ist ein Transduktor der um eine Gewichtsfunktion erweitert wurde die den Transitionen Werte zuweist Diese Werte konnen aus einem beliebigen Halbring K displaystyle mathbb K nbsp stammen Fasst man wie oben Ubergangs und Ausgabefunktion und dazu die Gewichtsfunktion zu einer Relation zusammen ist ein gewichteter Transduktor uber einem Halbring K displaystyle mathbb K nbsp ein 8 Tupel Q S G I D F l r displaystyle Q Sigma Gamma I Delta F lambda rho nbsp wobei Q S G F displaystyle Q Sigma Gamma F nbsp wie oben I Q displaystyle I subseteq Q nbsp ist eine Menge von Anfangszustanden D displaystyle Delta nbsp ist die Relation D Q S e G e K Q displaystyle Delta colon Q times Sigma cup varepsilon times Gamma cup varepsilon times mathbb K times Q nbsp l displaystyle lambda nbsp ist die Gewichtsfunktion l I K displaystyle lambda colon I to mathbb K nbsp die den Anfangszustanden Gewichte zuweist r displaystyle rho nbsp ist die Gewichtsfunktion r F K displaystyle rho colon F to mathbb K nbsp die den Endzustanden Gewichte zuweist Die Gewichte konnen beispielsweise in der Sprachsynthese dazu verwendet werden fur ein Eingabezeichen verschiedene Aussprachemoglichkeiten anzubieten die unterschiedlich wahrscheinlich sind Die Wahrscheinlichkeiten konnen zum Beispiel durch maschinelles Lernen ermittelt werden Anwendungen Bearbeiten Morphologische Analyse Robuste syntaktische Analyse Datenkompression KodierungKellertransduktor BearbeitenEin Kellertransduktor ist ein LR Parser zu einer gegebenen kontextfreien Grammatik also ein Kellerautomat der eine Ausgabe erzeugt Siehe auch BearbeitenAkzeptor Compiler Kellerautomat Parser Abgerufen von https de wikipedia org w index php title Transduktor Informatik amp oldid 200650222