Transduktor (Informatik)

Endlicher Transduktor

Endliche Transduktoren sind endliche Automaten, die im Unterschied zuAkzeptoren 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.

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

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Transduktor (Informatik) aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung