Vorlesung Informatik 3 Einführung in die Theoretische Informatik (03 – Nichtdeterminierte endliche Automaten)Prof. Dr. Th. Ottmann
Vorlesung Informatik 3 Einführung in die Theoretische Informatik (03 – Nichtdeterminierte endliche Automaten)
Prof. Dr. Th. Ottmann
Endliche Automaten
Deterministische endliche Automaten
Ein deterministischer endlicher Automat (DFA) ist gegeben durch
eine endliche Menge S von Zuständen
eine endliche Menge von Eingabezeichen
einen Anfangszustand s0 S
eine Endzustandsmenge F S
eine Übergangsfunktion δ : S x → S
Kurz: A = (, S, δ, s0, F)
δ kann auch durch einen Zustandsübergangs Graphen oder als Menge von Tripeln (s, a, t) mit δ (s, a) = t gegeben sein
δ ist manchmal nicht total (überall definiert)
Motivation für nichtdeterministische Automaten
Bei DFA ist der Nachfolgezustand immer eindeutig bestimmt, δ ist Funktion
Für bestimmte Aufgaben lassen sich die Automaten einfacher entwerfen, wenn mehr als ein Nachfolgezustand zur Verfügung steht.
Bsp.: Entwerfe Ar3n1 für die Sprache
Lr3n1 = {w {0, 1}*; w = u0v, u {0, 1}*, v {0, 1}2 }
Problem: Ar3n1 kann nicht voraussehen, wie viele Zeichen des Wortes noch folgen.
Lösung: Ar3n1 darf raten, wann der drittletzte Übergang stattfindet. Ein Wort wird akzeptiert, wenn es eine Folge von Zustandsübergängen gibt, die zu einem Finalzustand führen.
Nichtdeterministische endliche Automaten
Ein Nichtdeterministischer endlicher Automat (NFA) besteht aus
einer endlichen Menge S von Zuständen
einer endlichen Menge von Eingabezeichen
Einer Menge von Anfangszuständen S0 S
einer Endzustandsmenge F S
einer Zustandsübergangsrelation δ S x x S
Kurz: A = (S, , δ, S0, F)
δ kann als Menge von Tripeln (s, a, t) oder als Tabelle mit Mengen-Einträgen notiert werden, Bsp.:
δ = {(s0, 0, s0), (s0, 0, s1), (s0, 1, s0), (s1, 1, s2), (s2, 0, s3), (s2, 1, s3)}
Übergangsrelation
δ = {(s0, 0, s0), (s0, 0, s1), (s0, 1, s0), (s1, 1, s2), (s2, 0, s3), (s2, 1, s3)}
δ s0 s1 s2 s3
0
1
Fasst man die Folgezustände je Paar (Zustand, Eingabezeichen) zu einer Menge zusammen, kann man δ auch als mengenwertige Funktion auffassen:
δ : S x → 2S
Konfigurationen, Übergänge, Sprache eines NFA
Konfigurationen k = (s, v) und Konfigurationsübergänge (s, v) ├ (t, w) werden für einen NFA analog zu DFAs definiert:
K = (s, v) mit s S, v * ist der aktuelle Verarbeitungszustand.
Der Übergang (s, v) ├ (t, w) kann erfolgen, wenn v =aw und t δ(s, a)
Die von einem NFA A = (S, , δ, S0, F) akzeptierte Sprache ist
L(A) = {w * ; (s0, w) ├* (s, ε), s0 S0, s F}
DFAs sind spezielle NFAs
Jeder DFA A = (S, , δ, s0, F) kann als spezieller NFA aufgefasst werden, der dieselbe Menge von Worten akzeptiert.
Beispiel:
Erweiterung der Zustandsüberführung bei NFA
Die mengenwertige Zustandsüberführung δ : S x → 2S kann leicht erweitert werden zu
δ* : 2S x * → 2S definiert durch
δ* (R, ε) = R für alle R S
δ* (R, aw) = δ* ( s Rδ (s, a) , w) für alle R S, a , w *
Für einen NFA A kann die Sprache L(A) daher auch so definiert werden:
L(A) = {w *; δ* (S0, w) ∩ F ≠ }
Comments