6.2.  Endliche Transduktoren

Endliche Transduktoren (ET) 

Idee der endlichen Transduktoren

Endliche Transduktoren erweitern das Konzept des endlichen Automaten, indem auf zwei statt auf einem Band Zeichenketten verarbeitet werden.

Unterschiedliche Interpretationen der Bänder

Lexikalischer Transduktor bei Wortform-Generierung 
Siehe Abb. 128 auf Seite 155.


pict


Lexikalischer Transduktor bei Wortform-Analyse 
Siehe Abb. 6.2 auf Seite 158.


pict


6.2.1.  ϵ-NET

Nicht-deterministischer endlicher Transduktor (ϵ-NET) 

Definition 6.2.1 (non-deterministic finite state transducer). Ein nicht-deterministischer endlicher Transduktor T = Φ,Σ,δ,S,Fbesteht aus

  1. einer endlichen Menge Zustände Φ
  2. einem endlichen Alphabet Σ
  3. einer Zustandsübergangsfunktion δ : Φ × Σϵ × Σϵ (Φ)
  4. einem Startzustand S Φ
  5. einer Menge von Endzuständen F Φ

Hinweise

Die Notation Σϵ steht für Σ ∪{ϵ}, wobei ϵ∈∕Σ. Ein Transduktor unterscheidet sich nur in der Übergangsfunktion von einem EA.

ET im XFST-Prolog-Format 

Beispiel 6.2.2 (Direktes Einlesen von ET im PROLOG-Format).

xfst[0]: read prolog  
        Type one or more networks in prolog format.  
        Use ^D to terminate input.  
arc(ex2,0,1,"0":"0").  
arc(ex2,1,2,"0":"b").  
final(ex2,2).

pict

Übergangsfunktion auf Paare von Zeichenketten  
Die Bestimmung der Übergangsfunktion δ auf Paare von Zeichenketten setzt auf der reflexiven und transitiven Hülle der ϵ:ϵ-Übergänge auf.

Definition 6.2.3. Die ϵ-Hülle δϵ : Φ (Φ) eines ϵ-NET für einen Zustand T Φ ist rekursiv definiert durch:


pict pict

Abbildung 6.3: Rekursiver Erweiterungsschritt der ϵ-Hülle


Hinweis

Das Vorgehen ist analog zur Behandlung in ϵ-NEA.

Sprach-Relation von ϵ-NET  

Definition 6.2.4 (Zustandsübergangsfunktion für Zeichenketten). Die auf Zeichenketten erweiterte Übergangsfunktion δ : Φ × Σϵ× Σϵ(Φ) bestimmt die Menge der erreichbaren Zustände nach dem vollständigen Lesen eines Paars von Zeichenketten.

Für alle T Φ,u,w Σ,x,y Σϵ (mit xy = ϵ) eines ϵ-NET
    δ∗(T, ϵ,ϵ)  =  δ∗ϵ(T )
δ∗(T,wx, uy)  =        ⋃        δ∗(T′)
                   ′  ∗          ϵ
                 T ∈δ(δ(T,w,u),x,y)

Die Sprach-Relation eines ϵ-NET ist die Menge aller Paare von Zeichenketten, für die δ ausgehend vom Startzustand mindestens einen Endzustand enthält.

                ∗    ∗    ∗
LT  = {〈w,u〉 ∈ Σ  × Σ  | (δ(S, w,u)∩ F ) ⁄= ∅}

6.2.2.  Zugrundeliegender EA eines ET

Zugrundeliegender EA 
Jeder ET kann als EA aufgefasst werden, der die Symbole auf den beiden Bändern des ET als Symbolpaar auf einem Band verarbeitet.

Definition 6.2.5 (zugrundeliegender EA). Ein zugrundeliegender EA eines ET = (Φ,Σ,δ,S,F) ergibt sich als ,Σ,S,F): Für alle a,b Σ und T Φ

        Σ ′ =   Σ × Σ
δ′(T,〈a,b〉) =   δ(T,a,b)

6.2.3.  NET

Nicht-deterministischer endlicher Transduktor (NET) 
Jeder ϵ-NET kann in einen äquivalenten NET umgewandelt werden, der keine ϵ:ϵ-Übergänge enthält, indem im zugrundeliegenden EA die entsprechende ϵ-Eliminierung gemacht wird.

Der NET kann jedoch weiterhin Übergänge vom Typ ϵ:a bzw. a:ϵ mit a Σ enthalten.

Beispiel 6.2.6 (Entfernen von ϵ:ϵ-Übergängen).

xfst[1]: epsilon-remove net  
xfst[1]: print net  
Sigma: b  
Flags: epsilon_free, loop_free  
Arity: 2  
s0 [non-det]: <0:b> -> fs1.  
fs1:  (no arcs)

pict

pict

EA-Minimale Transduktoren in XFST 
Das Minimieren von ET bezieht sich in XFST immer auf den zugrundeliegenden EA.

Beispiel 6.2.7 (xfst und Zustandsdiagramm).

xfst[0]: read regex [ a:0 0:b ] ;  
xfst[1]: minimize net  
xfst[1]: print flags  
deterministic, pruned, minimized, epsilon_free, loop_free,  

pict

Hinweis

Die Relation kann leicht durch einen Automaten mit nur zwei Zuständen ausgedrückt werden. XFST führt eine solche Minimierung aber nicht automatisch durch. Für einfache Fälle der Form a:0 0:b führt der Stackbefehl cleanup allerdings doch noch zum erwünschten Ergebnis.

EA-Deterministische Transduktoren in XFST 
Das Flag für Determiniertheit von ET bezieht sich in XFST immer auf den zugrundeliegenden EA.

Beispiel 6.2.8 (xfst und Zustandsdiagramm).

xfst[0]: set minimal OFF  
xfst[0]: read regex a:b c:a | a:b c:b;  
xfst[1]: print net  
...  
s0 [non-det]: <a:b> -> s1, <a:b> -> s2.  
...  
xfst[1]: determinize net  
xfst[1]: print net  
Flags: deterministic, pruned,  
       epsilon_free, loop_free

pict


pict

Hinweis

EA-Deterministische Transduktoren in XFST erlauben gleiche Symbole auf dem einen Band, welche zu unterschiedlichen Folgezuständen führen.