5.4.  Sprachen von EA

Reguläre Sprachen und EA  
Die Menge der regulären Sprachen ist gleich der Menge der von EA akzeptierten Sprachen.

Wichtige in xfst berechenbare Eigenschaften von EA 
Tests bezüglich endlicher Automaten auf dem Stack

Wichtige in xfst berechenbare Beziehungen von EA 


EA2 =pict

EA1 =pict


Abbildung 5.4: EA2 über EA1 auf dem Stapel

Tests bezüglich endlicher Automaten auf dem Stack (EA2 auf EA1)

Anstelle von apply up kann man auch apply down sagen. Statt test lower-universal auch upper-universal. Diese Sprechweisen hängen mit den Transduktoren zusammen, welche eine “obere” und “untere” Sprache haben. Bei den endlichen Automaten sind aber beide Sprachen gleich.

5.4.1.  DEA

Sprache eines DEA 

Definition 5.4.1 (Zustandsübergangsfunktion für Zeichenketten).

Die auf Zeichenketten erweiterte Übergangsfunktion δ : Φ × ΣΦ bestimmt den Zustand nach dem vollständigen Lesen eines Wortes.

Für alle T Φ,w Σ,x Σ eines DEA A = Φ,Σ,δ,S,F
  δ∗(T, ϵ) =   T
δ∗(T,wx ) =   δ(δ∗(T, w),x)

Definition 5.4.2.

Die Sprache L(A) eines DEA A = Φ,Σ,δ,S,Fist die Menge aller Zeichenketten, für die δ ausgehend vom Startzustand einen Endzustand ergibt.

LA  = {w ∈ Σ∗ | δ∗(S,w ) ∈ F }

Beispiel-Berechnung für δ aus Beispiel 5.1.2 

  1. δ(0,aba)
  2. = δ(δ(0,ab),a)
  3. = δ(δ(δ(0,a),b),a)
  4. = δ(δ(δ(δ(0),a),b),a)
  5. = δ(δ(δ(0,a),b),a)
  6. = δ(δ(1,b),a)
  7. = δ(1,a)
  8. = 1

Beispiel-Evaluation
Siehe Abb. 5.5 auf Seite 131.


PIC PIC PIC PIC PIC PIC PIC PIC

Abbildung 5.5: Beispielevaluation der erweiterten Übergangsfunktion für DEA

5.4.2.  NEA

Sprache von NEA 

Definition 5.4.3 (Zustandsübergangsfunktion für Zeichenketten).

Die auf Zeichenketten erweiterte Übergangsfunktion δ : Φ × Σ(Φ) bestimmt die Menge der erreichbaren Zustände nach dem vollständigen Lesen einer Zeichenkette.

Für alle T Φ,w Σ,x Σ eines NEA A = Φ,Σ,δ,S,F
  δ∗(T,ϵ)  =  {T }
 ∗               ⋃        ′
δ (T,wx )  =           δ(T ,x)
              T′∈δ∗(T,w)

Definition 5.4.4.

Die Sprache L(A) eines NEA A = Φ,Σ,δ,S,Fist die Menge aller Zeichenketten, für die δ ausgehend vom Startzustand mindestens einen Endzustand enthält.

LA = {w ∈ Σ ∗ | (δ∗(S,w )∩ F ) ⁄= ∅}

Beispiel-Berechnung für δ 

  1. δ∗(0,ab)
  2.    ⋃
=    T′∈ δ∗(0,a)δ(T′,b)
  3.    ⋃
=   T ′∈⋃  ′′ ∗   δ(T′′,a)δ(T ′,b)
         T ∈δ(0,ϵ)
  4.    ⋃
=   T ′∈⋃  ′′   δ(T′′,a)δ(T′,b)
         T ∈{0}
  5.    ⋃
=   T ′∈δ(0,a)δ(T′,b)
  6.    ⋃
=    T′∈ {1,2} δ(T ′,b)
  7. =  δ(1,b) ∪δ(2,b)
  8. =  {2}∪ ∅
  9. =  {2}

Sprache von NEA mit ϵ

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

Für alle T Φ,w Σ,x Σ eines ϵ-NEA A = Φ,Σ,δ,S,F
  δ∗(T,ϵ)  =  δ∗(T)
 ∗             ϵ   ⋃       ∗  ′
δ (T,wx )  =              δϵ(T )
              T′∈δ(δ∗(T,w),x)

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

Reflexive und transitive Hülle der ϵ-Übergänge 

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


Falls pict , dann pict

Abbildung 5.6: Rekursiver Erweiterungsschritt der Hülle

5.4.3.  Äquivalenz von EAs

Äquivalenz der Sprachen von DEA, NEA und ϵ-NEA  

Entfernung von ϵ-Übergängen

Für jeden ϵ-NEA lässt sich ein NEA (ohne ϵ) konstruieren, der die gleiche Sprache akzeptiert.
xfst[1]: epsilon-remove net

Entfernung von Nicht-Determinismus

Für jeden NEA lässt sich ein DEA konstruieren, der die gleiche Sprache akzeptiert.
xfst[1]: determinize net

Entfernung unnötiger Zustände

Für jeden DEA lässt sich ein DEA mit minimaler Anzahl Zustände konstruieren, der die gleiche Sprache akzeptiert.
xfst[1]: minimize net

Der Befehl minimize net beinhaltet die Entfernung von ϵ-Übergängen und die Determinisierung. D.h. ein minimisierter EA ist immer deterministisch und ohne ϵ-Übergängen.

Beispiel für äquivalente EA 
Siehe Abb. 117 auf Seite 140.




pict pict
ϵ-NEA nach epsilon-remove


pict pict
nach determinize nach minimize



Abbildung 5.7: Effekt der 3 EA-Transformationen