4.1
 Endliche Automaten

4.1.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. Wenn kein Übergang mit dem gelesenen Symbol möglich ist, gilt die zu verarbeitende Zeichenkette als nicht akzeptiert. Beim Einlesen des ersten Zeichens einer Zeichenkette ist der Automat immer im sogenannten Startzustand.

Definition 4.1.1 (DEA, deterministic finite state automaton).

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

  1. einer endlichen Menge Zustände Φ
  2. einem endlichen Eingabealphabet Σ
  3. einer (partiellen) 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übergangsdiagramm 
Es stellt einen EA anschaulich als gerichteten Graphen dar.

Beispiel 4.1.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


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 relevant sind.

Beispiel 4.1.3 (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.1.4 (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.1.5 (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)

4.1.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 einen aktuellen Zustand wechseln. 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. ?? auf Seite ??.


PIC PIC PIC PIC PIC PIC PIC PIC

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

Definition 4.1.6 (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.1.7 (Tabellendarstellung und Zustandsdiagramm).

δ a b



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

pict

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.1.8 (𝜖-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.

δ : Φ × ∪{𝜖}) (Φ)

QUIZ Leichtes QUIZ zu endlichen Automaten