Vorlesung Informatik 3 Einführung in die Theoretische Informatik (02 – Endliche Automaten)Prof. Dr. Th. Ottmann
Naives Verfahren
Text: t1 t2 t3 ti+1 … ti+j ….ti+m ……
Muster: p1 …. pj ……pm Für jede mögliche Verschiebung i mit 0 ≤ i ≤ n-m prüfe maximal m Zeichenpaare. Bei Mismatch beginne mit neuer Verschiebung!
Aufwandsabschätzung: Was ist die Laufzeit im worst case?
Grundidee des KMP-Verfahrens
Beobachtung: Das Lesen und
Verarbeiten eines Zeichens
Verursacht nur konstanten
Aufwand! Konstruiere zum Muster P = p1p2 … pm einen DFA AP, der den Text T = t1t2t3 … tn einmal v.l.n.r. liest und in einem Endzustand ist, immer dann, wenn er das Ende eines Vorkommens von P in T erkannt hat.
Beispiel für die Konstruktion eines Pattern Matching Automaten
s0 sa sab sabba sabb Sei P = abba, ein DFA, der jedes Vorkommen von P in einem beliebigen Text aus * = {a, b}* entdeckt, kann so konstruiert werden:
Operationen für Formale Sprachen
Sei ein fest gewähltes, endliches Alphabet. Für Sprachen A, B * definiert man:
Vereinigung: A B = {w; w A oder w B}
Durchschnitt: A ∩ B = {w; w A und w B}
Verkettung: A B = {xy; x A und y B}
Iteration A* = {x1…xk; k ≥ 0 und xi A für alle i mit 1 ≤ i ≤ k}
Reguläre Sprachen
Die Klasse der von endlichen Automaten akzeptierbaren Sprachen heißt auch Klasse der regulären Sprachen, m.a.W:
Eine Sprache L * heißt regulär, wenn es einen endlichen Automaten (einen DFA) A gibt mit L = L(A).
Satz: Die Klasse der regulären Sprachen ist abgeschlossen gegenüber Vereinigung, Durchschnitt und Komplement.
Comments