Vorlesung Informatik 3 Einführung in die Theoretische Informatik (02 – Endliche Automaten)Prof. Dr. Th. Ottmann
Vorlesung Informatik 3 Einführung in die Theoretische Informatik (02 – Endliche Automaten)
Prof. Dr. Th. Ottmann
Motivation
Einfacher Automat (Schalter, Fahrkarten)
Definierter Ablauf von Aktionen
Determinierte Folge von (akzeptierten) Aktionen
Ausstattung eines Automaten A
Eingabe: A wird von außen mit Eingabedaten versorgt
Interne Zustände: A befindet sich immer in einem definierten Zustand. A kann Zustandsübergänge durchführen, etwa unter Einfluss der Eingabe.
Ausgabe: A kann unter gewissen Umständen Ausgabeinformation erzeugen.
Beispiel: Geräteschalter
aus ein Kippschalter drücken Kippschalter drücken Anfangszustand, (gew.) Endzustand, Eingabefolge
Endliche Automaten dienen zur „Klassifikation“ von Eingabefolgen
Endlicher Automat als Black Box
Zustandsdiagramm des Automaten Aswim
Eigenschaften von Aswim:
Münzeingaben mit Werten 50, 100, 200 in beliebiger Reihenfolge
Nach Einwurf von insgesamt ≥ 200 akzeptiert Aswim: Eintritt freigegeben!
Der Gesamtwert der bisherigen Eingabe ist im aktuellen Zustand vermerkt.
Startkonfiguration von Aswim
Eingabeband enthält Eingaben als Folgen von Zeichen
Zustandsspeicher enthält jeweils aktuellen Zustand
Programm, Kontrolle: Zustandsübergangsfunktion δ.
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)
Erweiterte Übergangsfunktion
Die Zustandsübergangsfunktion δ kann von Zeichen auf Wörter erweitert werden:
δ* : S x * → S definiert durch
δ*(s, ε) = s für alle s S
δ*(s, aw) = δ*(δ(s, a), w) für alle a , w *
Für einen endlichen Automaten A = (, S, δ, s0, F) wird die von A akzeptierte Sprache (die Menge aller von A akzeptierten Eingabefolgen) L(A) * definiert durch:
L(A) = {w; δ*(s0, w) F}
Beispiel
s0 s1 0 0 1 1
Konfiguration eines endlichen Automaten
Konfigurationsübergänge
Ein Konfigurationsübergang (s, v) ├ (t, w) kann stattfinden, wenn v = aw und δ(s, a) =t ist.
Die Abarbeitung eines Wortes x = x1x2 … xr durch einen DFA kann als Folge von Konfigurationsübergängen beschrieben werden:
(s0, x1x2 … xr ) ├ (s1, x2 … xr ) ├ … ├ (sr, ε )
Mit ├ * wird die transitiv-reflexive Hülle von ├ beschrieben.
Beispiel:
(start, 50 100 50) ├
Reguläre Sprachen
Für einen DFA A = (, S, δ, s0, F) ist
L(A) = {w * ; (s0, w) ├* (s, ε), s F}
die von A akzeptierte Sprache.
Eine Sprache L * heißt regulär, wenn es einen DFA A gibt mit L = L(A).
Zwei DFA A und A‘ heißen äquivalent, falls sie die gleiche Sprache akzeptieren, wenn also gilt: L(A) = L(A‘).
Theorie endlicher Automaten
Gibt Antworten auf folgende Fragen:
Wie entwirft man endliche Automaten für bestimmte Aufgaben (Synthese-Aufgabe)?
Wie analysiert man endliche Automaten? D.h. kann man die von endlichen Automaten akzeptierbaren Sprachen auch anders (automatenfrei) beschreiben?
Wie vereinfacht (reduziert, minimiert) man endliche Automaten? D.h. wie eliminiert man evtl. überflüssige Zustände?
Die Synthese endlicher Automaten ist ein kreativer Prozess!
Zur Analyse verwendet man: Reguläre Ausdrücke, Grammatiken, algebraische Hilfsmittel.
Die Reduzierung erfolgt durch Bildung von Äquivalenzklassen.
Beispiel einer Syntheseaufgabe
Finde einen DFA für
L3b = {w {a, b}* ; w = w1…wn, wi {a, b}, w3i ≠ a, 1 ≤ 3i ≤ n, n ≥ 0}
Dreiergruppe von Zeichen, deren letztes ein b ist, muss erkannt werden:
Beliebig viele Dreiergruppen derselben Art sind als Präfixe erlaubt:
Auch sämtliche Präfixe sollen erkannt werden:
Vollständige Automaten
Bisher musste die Funktion δ eines DFA nicht total sein.
Ein DFA A = (, S, δ, s0, F) heißt vollständig, wenn dom(δ) = S x
Jeder DFA A = (, S, δ, s0, F) kann durch Hinzunahme eines Zustands tot vervollständigt werden:
Wenn δ(s, a) nicht definiert ist, ergänze δ(s, a) = tot
Beispiel:
Text: t1 t2 t3 ti+1… ti+m
Muster: p1 ……pm Gegeben:
Text t1t2t3 … tn n
Muster p1p2 … pm m
Gesucht: Ein oder alle Vorkommen des Musters im Text, d.h. Verschiebungen i mit 0 ≤ i ≤ n-m und
p1 = ti+1
p2 = ti+2
……..
pm = ti+m
Comments