Transduktor (Informatik)

Endlicher Transduktor

Mathematische Definition

Ein Transduktor ist ein 7-Tupel < Q, Σ, Γ, q₀, δ,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),
• q₀ ist der Anfangszustand und ein Element aus Q,
• δ ist die Zustandsübergangsfunktion: δ: Q x Σ ∪ {ε} → 2^Q,
• 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.

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