4.2.  Endliche Automaten

4.2.1.  Deterministische endliche Automaten

Deterministische Endliche Automaten (DEA)

Idee des akzeptierenden deterministischen endlichen Automaten

Ein endlicher Automat ist eine (abstrakte) Maschine zur zeichenweisen Erkennung von Wörtern einer regulären Sprache. Sie ist nach jedem Verarbeitungsschritt in genau einem Zustand. Bei jedem Schritt wird ein Zeichen gelesen und aufgrund des aktuellen Zustands und dem Lesezeichen in einen Nachfolgezustand gewechselt. Wenn kein Zeichen mehr zu lesen ist und die Maschine in einem Endzustand ist, gilt die gelesene Zeichenkette als akzeptiert. Beim Einlesen des ersten Zeichens einer Zeichenkette ist der Automat immer im sogenannten Startzustand.

Definition 4.2.1 (DEA, finite state automaton).

Ein deterministischer endlicher Automat A = Φ,Σ,δ,S,Fbesteht aus

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

Hinweis

Die Übergangsfunktion δ bestimmt den Folgezustand, der ausgehend vom aktuellen Zustand beim Lesen eines einzelnen Zeichens erreicht wird.

Zustandübergangsdiagramme
Es stellt einen EA anschaulich als gerichteten Graphen dar.

Beispiel 4.2.2.

A = 〈{0,1},{a,b},δ,0,{1}〉 mit δ = {〈〈0,a,1,〈〈0,b,1,〈〈1,a,1,〈〈1,b,1〉}


pict

Abbildung 4.1: Zustandsübergangsdiagramm


Sprache eines DEA

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

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

Für alle T ΦΣ,x Σ eines DEA A = Φ,Σ,δ,S,F
  δ∗(T, ε) =   T
δ∗(T,ωx ) =   δ(δ∗(T, ω),x)

Definition 4.2.4.

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

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

Beispiel-Berechnung für δ aus Beispiel 4.2.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. 4.2.1 auf Seite 124.


PIC PIC PIC PIC PIC PIC PIC PIC

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

Partielle Zustandübergangsdiagramme
Die Definition von δ als totale Funktion verlangt für alle Zustände und Zeichen aus Σ eine Kante. In der Linguistik zeigt man oft nur Knoten und Kanten, die für das Akzeptieren einer Zeichenkette besucht werden.

Beispiel 4.2.5 (Partieller und vollständiger Automat).

pict

pict

Fehlerzustand (error state) und Fehlerübergänge

Um ein partielles Übergangsdiagramm zu vervollständigen, füge einen Zustand E∕∈F dazu, und mache ihn zum Endknoten aller nicht-bestehenden Kanten.

EA im XFST-Prolog-Format

Beispiel 4.2.6 (Direktes Einlesen von EA im PROLOG-Format).

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

pict

Textuelle Ausgabe von EA

Beispiel 4.2.7 (Anzeige von Informationen zum obersten EA auf dem Stack).

xfst[1]: print net  
Sigma: a b  
Size: 2  
Net: ex2  
Flags: epsilon_free  
Arity: 1  
s0: a -> s1.  
s1: b -> fs2.  
fs2: (no arcs)

Wichtige berechenbare Eigenschaften von EA
Tests bezüglich endlicher Automaten auf dem Stack (EA2 liegt 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.

4.2.2.  Nicht-deterministische endliche Automaten

Nicht-deterministischer endlicher Automat (NEA)

Idee des akzeptierenden nicht-deterministischen endlichen Automaten

Im Gegensatz zum DEA kann ein NEA nach jedem Verarbeitungsschritt in mehr als einem Zustand sein. Bei jedem Schritt wird ebenfalls ein Zeichen gelesen und aufgrund der möglichen aktuellen Zustände und dem Lesezeichen in die zulässigen Nachfolgezustände gewechselt.

Beispiel-Evaluation
Siehe Abb. 4.2.2 auf Seite 124.


PIC PIC PIC PIC PIC PIC

Abbildung 4.3: Beispielevaluation der erweiterten Übergangsfunktion für NEA

Definition 4.2.8 (NEA, non-deterministic finite state automaton).

Ein nicht-deterministischer endlicher Automat A = Φ,Σ,δ,S,Funterscheidet sich von einem DEA nur in der Übergangsfunktion. Vom aktuellen Zustand kann man mit einem Zeichen zu beliebig vielen Folgezuständen übergehen.

δ : Φ × Σ → ℘(Φ)

Beispiel 4.2.9 (Tabellendarstellung und Zustandsdiagramm).

δ a b



s0 {s1,fs2} {fs2}
s1 {fs2}
fs2

pict

Sprache von NEA

Definition 4.2.10 (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 ΦΣ,x Σ eines NEA A = Φ,Σ,δ,S,F
  δ∗(T,ε)  =  {T }
 ∗               ⋃        ′
δ (T,ωx )  =           δ(T ,x)
              T′∈δ∗(T,w)

Definition 4.2.11.

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 = {ω ∈ Σ  | δ (S,ω )∩ 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}

4.2.3.  Nicht-deterministische endliche Automaten mit ε

Idee des akzeptierenden nicht-deterministischen endlichen Automaten mit ε

Bei jedem Schritt wird wie beim NEA ein Zeichen gelesen und aufgrund der möglichen aktuellen Zustände und dem Lesezeichen in die zulässigen Nachfolgezustände gewechselt.

Die aktuellen Zustände umfassen aber immer auch alle Zustände, welche durch beliebig viele ε-Übergange verbunden sind.

Bei einem ε-Übergang wird kein Zeichen gelesen.

Definition 4.2.12 (ε-NEA, non-deterministic finite state automaton).

Ein nicht-deterministischer endlicher Automat mit ε-Übergängen A = Φ,Σ,δ,S,Funterscheidet sich von einem NEA nur in der Übergangsfunktion.

δ : Φ × Σ ∪{ε}(Φ)

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

Definition 4.2.13.

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

Sprache von NEA mit ε

Definition 4.2.14 (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 Sprache eines ε-NEA ist gleich definiert wie bei NEA ohne ε.

QUIZ Leichtes QUIZ zu endlichen Automaten

Ä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. 78 auf Seite 142.




pict pict
ε-NEA nach epsilon-remove


pict pict
nach determinize nach minimize



Abbildung 4.4: Effekt der 3 EA-Transformationen