Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Theoretische Informatikfür
Wirtschaftsinformatik und LehramtReguläre Sprachen
Priv.-Doz. Dr. Stefan [email protected]
Theoretische InformatikFriedrich-Alexander Universität Erlangen-Nürnberg
SS 2016
1 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Gliederung
1 Lernziele
2 Grammatiken
3 Reguläre Sprachen
4 Deterministische endliche Automaten
5 Nichtdeterministische endliche Automaten
6 Reguläre Ausdrücke
7 Zusammenfassung
2 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Worum geht es in diesem Abschnitt? (I)
Erste Formalismen zur endlichen algorithmischenBeschreibung von formalen Sprachen(= Lösung der entsprechenden Entscheidungsprobleme):
Automaten und Grammatiken
Praktische Anwendungen:Compilerbau: lexikalische Analyse, Parsing, TextprocessingAutomatische Systemanalyse: z.B. formale Verifikation vonnicht-trivialen Eigenschaften (Modelchecking)
Chomsky-Hierarchie: Hierarchie von Klassen von formalenSprachen und Grammatiken (und Maschinenmodellen)
(setzt die verschiedenen Sprachklassen in Beziehung zueinander)
3 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Noam ChomskyAmerikanischer Linguist, Philosoph, Logiker,Historiker und politischer Aktivist
Vater der modernen Linguistik
Analytische Philosophie
Über 100 Bücher
Bekannte Entdeckungen:
Chomsky-Hierarchie
Chomsky-Schützenberger Satz
Einfluss auf:
Noam Chomsky (1928– )Quelle: Wikipedia
künstliche Intelligenz, Kognitionswissenschaft, Mathematik, Logik,Informatik, Programmiersprachentheorie, Psychologie und
Politikwissenschaft.4 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Worum geht es in diesem Abschnitt? (II)
Jetzt als Erstes: Reguläre Sprachenbesonders einfachz.B. Suche nach regulären Ausdrücken in TextenMechanismen zur Erzeugung/Beschreibung regulärerSprachen:
reguläre Grammatikenreguläre Ausdrückedeterministische und nichtdeterministische endliche Automaten
5 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Lernziele
wissen, wie eine reguläre Sprache erzeugt und akzeptiertwerden kanndie Chomsky-Hierarchie kennen und Eigenschaften der ihrzugeordneten Grammatik-Typen benennen können
6 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Grammatiken
7 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zur Erinnerung: Formale Sprachen
DefinitionSei Σ ein Alphabet. (d.h. eine nicht leere, endliche Menge)Eine (formale) Sprache L über Σ ist eine beliebige Teilmenge vonΣ∗ (= Menge aller Wörter über Σ):
L ⊆ Σ∗.
Die leere Teilmenge ∅ heißt leere Sprache.
Zu jeder Sprache L über Σ gehört das Entscheidungsproblem:Eingabe: w ∈ Σ∗
Aufgabe: entscheide, ob w ∈ L gilt.
8 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Formale Sprachen
BeispielΣ = {(, ),+,−, ∗, /, a}
Sprache der korrekt geklammerten arithmetischen Ausdrücke:EXPR ⊆ Σ∗
(a − a) ∗ a + a/(a + a)− a ∈ EXPR(((a))) ∈ EXPR
((a+)− a( /∈ EXPR
(a Platzhalter für beliebige Konstanten oder Variablen)
9 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Grammatiken (I)
Sprachen enthalten im Allgemeinen unendlich viele Wörteralgorithmischer Umgang mit Sprachen erfordertendliche Beschreibungdazu dienen Grammatiken und Automaten
Beispiel für Grammatik〈Satz〉 → 〈Subjekt〉 〈Prädikat〉 〈Objekt〉〈Subjekt〉 → 〈Artikel〉 〈Attribut〉 〈Substantiv〉〈Artikel〉 → ε〈Artikel〉 → der〈Artikel〉 → die〈Artikel〉 → das〈Attribut〉 → ε〈Attribut〉 → 〈Adjektiv〉〈Attribut〉 → 〈Adjektiv〉 〈Attribut〉
10 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Grammatiken (II)
Beispiel für Grammatik (Fortsetzung)〈Adjektiv〉 → kleine〈Adjektiv〉 → bissige〈Adjektiv〉 → große〈Substantiv〉 → Hund〈Substantiv〉 → Katze〈Prädikat〉 → jagt〈Objekt〉 → 〈Artikel〉 〈Attribut〉 〈Substantiv〉
in spitzen Klammern 〈· · · 〉: Nicht-Terminale (oder Variable)ohne spitze Klammern: Terminale
Frage: Gehört der Satz„der kleine bissige Hund jagt die große Katze“
zu der Sprache, die von der Grammatik erzeugt wird?11 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Syntaxbaum
Elternknoten mit linker Seite einer Regel beschriftetKinder sind Objekte auf der rechten Seite der Regelnmit dieser Grammatik ist unendliche Sprache darstellbar, z.B.
„der Hund jagt die kleine kleine · · · kleine︸ ︷︷ ︸beliebige endliche Anzahl
Katze“12 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Grammatiken (III)
Grammatiken besitzen Regeln der Form
〈linke Seite〉 → 〈rechte Seite〉
Links und rechts zwei Typen von Symbolen:
Nicht-Terminale (oder Variablen) · · · · · · aus denen nochweitere Wortbestandteile abgeleitet werden sollenTerminale · · · · · · die eigentlichen Symbole
Vorheriges Beispiel:Auf der linken Seite befindet sich immer genau ein Nicht-Terminal(sog. kontextfreie Grammatik).
Es gibt aber allgemeinere Grammatiken.
13 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Definition einer Grammatik
DefinitionEine Grammatik ist ein 4-Tupel G = (V ,Σ,P,S) mit
V endliche Menge der Nicht-Terminale (oder Variablen)Σ Alphabet der TerminaleP endliche Menge der Regeln (oder Produktionen):
P ⊆ (V ∪ Σ)+ × (V ∪ Σ)∗
S ∈ V Startvariable.
14 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Schreibweisen
Variablen (Elemente aus V ) mit Großbuchstaben:
A,B,C , . . .
Terminalsymbole (Elemente aus Σ) oft mit Kleinbuchstaben:
a, b, c, . . .
Wörter (Elemente aus Σ∗) mit Kleinbuchstabenum „w herum“:
. . . , u, v ,w , . . .Regeln mit einem „Pfeil“:
u → v statt (u, v) ∈ P.
(d.h. → ⊆ (V ∪ Σ)+ × (V ∪ Σ)∗ Relation)15 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Beispiel einer Grammatik
BeispielG = (V ,Σ,P,S) mit
V = {S,B,C}, Σ = {a, b, c} und P besteht aus:
S → aSBCS → aBCCB → BC
aB → abbB → bbbC → bc
cC → cc
Frage:
Wie beschreiben Grammatiken Wörter formaler Sprachen?
16 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ableitungen (I)
DefinitionSeien u, v ∈ (V ∪ Σ)∗.Definiere die Relation u ⇒G v (⇒G ⊆ (V ∪ Σ)∗ × (V ∪ Σ∗))(„v aus u mit G direkt ableitbar“) falls
u = xyz und v = xy ′z mit x , y ∈ (V ∪ Σ)∗und y → y ′ Regel in P.
⇒∗G sei die reflexive, transitive Hülle von ⇒G , d.h.:u ⇒∗G v falls es w0,w1,w2, . . . ,wn (n ∈ N) gibt mit
u = w0 ⇒G w1 ⇒G w2 ⇒G · · · ⇒G wn = v
(„v aus u mit G ableitbar“) (in n = 0, 1, 2, . . . Schritten)Die Folge w0,w1, . . . ,wn heißt Ableitung (von v aus u).
Wir schreiben meist: ⇒ bzw. ⇒∗ statt ⇒G und ⇒∗G .17 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ableitungen (II)
BeispielFür G = (V ,Σ,P, S) mit V = {S,B,C}, Σ = {a, b, c} und P:
S → aSBCS → aBCCB → BC
aB → abbB → bbbC → bc
cC → cc
Es gilt: S ⇒∗ aaabbbccc, denn
S ⇒ aSBC ⇒ aaSBCBC ⇒ aaaBCBCBC⇒ aaaBBCCBC ⇒ aaaBBCBCC ⇒ aaaBBBCCC⇒ aaabBBCCC ⇒ aaabbBCCC ⇒ aaabbbCCC⇒ aaabbbcCC ⇒ aaabbbccC ⇒ aaabbbccc
Es gilt auch: aSBC ⇒∗ aaabbBCCC .18 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Erzeugte Sprache einer Grammatik (I)
DefinitionSei G = (V ,Σ,P, S) eine Grammatik.
G erzeugt ein Wort w ∈ Σ∗, falls S ⇒∗ w gilt.
Die von G erzeugte Sprache ist
L(G) = {w ∈ Σ∗ | S ⇒∗ w}.
(genau alle von G erzeugten Wörter über Σ)
19 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Erzeugte Sprache einer Grammatik (II)
BeispielG = (V ,Σ,P,S) mit V = {S,B,C}, Σ = {a, b, c} und P:
S → aSBCS → aBCCB → BC
aB → abbB → bbbC → bc
cC → cc
(Ohne Beweis) G erzeugt die Sprache:
L(G) = {anbncn | n ≥ 1}.
20 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ableiten und Nichtdeterminismus (I)
Bemerkung:Ableiten ist ein nichtdeterministischer Prozess.Für ein Wort u ∈ (V ∪ Σ)∗ kann es entweder
gar kein,ein odermehrere
v geben mit u ⇒ v .Mit anderen Worten:
⇒ ist keine Funktion.
Dieser Nichtdeterminismus kann durch zwei verschiedene Effekteverursacht werden . . .
21 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ableiten und Nichtdeterminismus (II)
Zwei verschiedene Regeln sind anwendbar:In der Beispiel-Ableitung:
Eine Regel ist an zwei verschiedenen Stellen anwendbar:In der Beispiel-Ableitung:
22 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Weitere Bemerkungen zum Ableiten
Es kann beliebig lange Pfade geben, die nie zu einem Wortaus Terminalsymbolen führen:
S ⇒ aSBC ⇒ aaSBCBC ⇒ aaaSBCBCBC ⇒ · · ·
Pfade können in einer „Sackgasse “enden,d.h. obwohl noch Variablen vorkommen, ist keine Regel mehranwendbar:
S ⇒ aSBC ⇒ aaBCBC ⇒ aabCBC ⇒ aabcBC 6⇒
23 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Die Chomsky-Hierarchie (I)
Allgemeine Grammatiken (und auch später Turing-Maschinen)erzeugen genau die sogenannten semi-entscheidbare Sprachen.Entscheidbare Sprachen nur dann, wenn die Erzeugungs-„Mächtigkeit“ der Grammatiken eingeschränkt wird.Im Folgenden: bestimmte eingeschränkte Typen vonGrammatiken:
24 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Die Chomsky-Hierarchie (II)
Definition (Typ 0-, Typ 1-, Typ 2-, Typ 3-Grammatiken)Typ 0: Jede Grammatik ist vom Typ 0.(keine Einschränkungen der Regelform)
Typ 1: Eine Grammatik ist vom Typ 1 oder kontextsensitiv, fallsalle Regeln in P von einer der folgenden Formen sind:
S → ε oder uAv → uwv
mit A ∈ V , u, v ∈ (Σ ∪ V )∗ und w ∈ (Σ ∪ V )+.
Typ 2: Eine Grammatik ist vom Typ 2 oder kontextfrei, falls alleRegeln in P in der folgenden Form sind:
A→ w mit A ∈ V ,w ∈ (Σ ∪ V )∗.
25 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Die Chomsky-Hierarchie (III)
Definition (Typ 0-, Typ 1-, Typ 2-, Typ 3-Grammatiken)Typ 3: Eine Grammatik ist vom Typ 3 oder regulär, falls alleRegeln in P in der folgenden Form sind:
A→ ε, A→ a oder A→ aB mit A,B ∈ V , a ∈ Σ.
(d.h. rechte Seiten entweder leer oder einzelne Terminalzeichen oder einTerminalzeichen gefolgt von einer einzelnen Variablen.)
Woher kommen die Namen „kontextfrei „und „kontextsensitiv“?Bei kontextfreien Grammatiken: Regeln der Form A→ w :In Ableitungen uAv ⇒ uwv wird A immer unabhängig vomKontext ersetzt.Bei kontextsensitiven Grammatiken ist uAv → uwv möglich:A kann nur in Kontexten mit u und v durch w ersetzt werden.
26 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Die Chomsky-Hierarchie (IV)
Schreibweise: Statt
A→ w1, A→ w2, . . . , A→ wn (d.h. gleiche linke Seite)
schreibe: A→ w1 |w2 | · · · |wn.
BeispieleTyp 2- bzw. kontextfreie Grammatik
S → aCb |CC → c |Cc
Typ 3- bzw. reguläre GrammatikS → aS | aUU → bB | b
27 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Die Chomsky-Hierarchie (V)
Definition (Typ 0-, Typ 1-, Typ 2-, Typ 3-Sprachen)Eine Sprache L ∈ Σ∗ heißt
vom Typ 0 (Typ 1, Typ 2, Typ 3),
falls es eine Typ 0- (Typ 1-, Typ 2-, Typ 3-) Grammatik G gibt mit
L(G) = L.
Typ-2-Sprachen heißen auch kontextfrei.
Typ-3-Sprachen heißen auch regulär.
28 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Die Chomsky-Hierarchie (VI)
Typ 1-Grammatiken sind vom Typ 0Typ 2-Grammatiken sind vom Typ 1(können leicht umgewandelt werden)Typ 3-Grammatiken sind vom Typ 2
=⇒ Sprachklassen ineinanderenthalten
Außerdem: die Inklusionen sind echt.(z.B. gibt es kontextfreie Sprachen,die nicht regulär sind)
29 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Sprachen
30 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Grammatiken (I)
Definition (Erinnerung)Eine Grammatik G = (V ,Σ,P, S) heißt regulär, wenn jede Regel in Pvon einer der folgenden Formen ist:
A→ ε, A→ a oder A→ aB (rechtslineare Regel)
mit A,B ∈ V und a ∈ Σ.
Beispiel einer regulären GrammatikGrammatik G3a mit V = {A,B,C},Σ = {a, b}, S = A und Regeln
A→ aB | bA | ε,B → aC | bB,C → aA | bC
31 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Grammatiken (II)
Beispiel einer AbleitungRegeln: A→ aB | bA | ε,
B → aC | bB,C → aA | bC
Ableitung: A ⇒ bA⇒ baB⇒ baaC⇒ baabC⇒ baabaA⇒ baaba
32 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Sprachen (I)
Sei nun
L3a = {w ∈ {a, b}∗ | |w |a ist durch 3 teilbar}.
Behauptung: L3a ist eine reguläre Sprache, denn es giltL3a = L(G3a).
Beweis: Für alle w ∈ {a, b}∗ gilt:
a) A⇒∗ w ⇐⇒ |w |a ist durch 3 teilbar.b) B ⇒∗ w ⇐⇒ |w |a + 1 ist durch 3 teilbar.c) C ⇒∗ w ⇐⇒ |w |a + 2 ist durch 3 teilbar.
Aus a) folgt dann L3a = L(G3a).
33 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Sprachen (II)
Beweis durch Induktion über den Aufbau von w :(wir schreiben: t3(x) für „x ist durch 3 teilbar“):1.) w = ε: es gilt t3(|w |a) und
A⇒∗ w , nicht B ⇒∗ w und nicht C ⇒∗ w .Daher gelten a), b) und c).
2) w 6= ε: dann ist w = aw ′ oder w = bw ′ (w ′ ∈ Σ∗).1. Fall: w = aw ′. Dann gilt(mit Anwendung der Induktionsvoraussetzung auf w ′):
(A⇒∗ w) ⇐⇒ (B ⇒∗ w ′) ⇐⇒ t3(|w ′|a + 1) ⇐⇒ t3(|w |a),(B ⇒∗ w) ⇐⇒ (C ⇒∗ w ′) ⇐⇒ t3(|w ′|a + 2) ⇐⇒ t3(|w |a + 1),(C ⇒∗ w) ⇐⇒ (A⇒∗ w ′) ⇐⇒ t3(|w ′|a) ⇐⇒ t3(|w |a + 2).
34 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Sprachen (III)
Beweis durch Induktion über den Aufbau von w (Fortsetzung):
2) w 6= ε (Fortsetzung):2. Fall: w = bw ′. Dann gilt(mit Anwendung der Induktionsvoraussetzung auf w ′):
(A⇒∗ w)⇐⇒ (A⇒∗ w ′)⇐⇒ t3(|w ′|a)⇐⇒ t3(|w |a),(B ⇒∗ w)⇐⇒ (B ⇒∗ w ′)⇐⇒ t3(|w ′|a +1)⇐⇒ t3(|w |a +1),(C ⇒∗ w)⇐⇒ (C ⇒∗ w ′)⇐⇒ t3(|w ′|a +2)⇐⇒ t3(|w |a +2).
In jedem Fall gelten also a), b) und c) für w . �
35 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Deterministische endlicheAutomaten (DFA)
36 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Deterministische endliche Automaten (I)
Bisher:Grammatiken erzeugen Wörter formaler Sprachen aus „nichts“.
Jetzt: Verarbeitung von Wörtern durch abstrakte Maschinen:endliche Automaten verarbeiten (akzeptieren) eingegebene Wörter
37 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Deterministische endliche Automaten (II)
Arbeitsweise eines endlichen Automaten M:
liest die Eingabe von links nach rechtsSymbole der Eingabe werden nicht verändertfür jedes gelesene Symbol ändert M seinen internen ZustandZustände zeigen an, ob (bis jetzt) gelesenes Wortakzeptiert/nicht akzeptiert wird
38 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Deterministische endliche Automaten (III)
Graphische Notation:
Beispiel: (Σ = {a, b})
39 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Deterministische endliche Automaten (IV)
DefinitionEin deterministischer endlicher Automat(deterministic finite automaton, DFA) ist ein 5-Tupel
M = (Z ,Σ, δ, z0,E ) gegeben durch
eine endliche Menge Z von Zuständen,ein Eingabealphabet Σ,eine totale Überführungsfunktion δ : Z × Σ→ Z ,einen Startzustand z0 ∈ Z ,eine Menge E ⊆ Z von Finalzuständen(auch Endzustände oder akzeptierende Zustände).
Warum deterministisch? Weil für jeden Zustand und jedesEingabesymbol genau ein Folgezustand existiert.
40 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ablauf eines DFA (I)
Beispiel
41 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ablauf eines DFA (II)
Beispiel (Fortsetzung)
42 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Mehr-Schritt-Übergänge eines DFA (I)
Arbeitsweise und akzeptierte Wörter/Sprache eines DFAsoll jetzt formalisiert werden.
Dazu:Erweiterung der Übergangsfunktion δ : Z × Σ→ Z auf Wörter:
δ̂ : Z × Σ∗ → Z ,
Definition (Mehr-Schritt-Übergänge)Zu einem gegebenen DFA M = (Z ,Σ, δ, z0,E ) definieren wir eineFunktion δ̂ : Z × Σ∗ → Z induktiv:
δ̂(z , ε) = z ,δ̂(z , aw) = δ̂(δ(z , a),w) (z ∈ Z , a ∈ Σ,w ∈ Σ∗).
43 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Mehr-Schritt-Übergänge eines DFA (II)
δ̂(z ,w) ist der Zustand, den der Automat erreicht,nachdem er w „abgearbeitet“ hat.
Für δ̂ gilt offenbar:a) a ∈ Σ⇒ δ̂(z , a) = δ(z , a)
b) a1, . . . , an ∈ Σ⇒ δ̂(z , a1 · · · an) = δ(· · · δ(δ(z , a1), a2), . . . , an)
c) u, v ∈ Σ∗ ⇒ δ̂(z , uv) = δ̂(δ̂(z , u), v)
44 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines DFA (I)
DefinitionSei M = (Z ,Σ, δ, z0,E ) ein DFA.
M akzeptiert ein Wort w ∈ Σ∗, falls δ̂(z0,w) ∈ E gilt.
Die von M akzeptierte Sprache ist
L(M) = {w ∈ Σ∗ | M akzeptiert w}.
Von M akzeptierte Sprache:
Menge aller Wörter, die M vom Startzustandin einen Endzustand überführen.
45 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines DFA (II)
Beispiel 1Sei Σ = {a, b, c}.
DFA, der die folgende Sprache L akzeptiert:
L = {w ∈ Σ∗ | w enthält abc}
46 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines DFA (III)
Beispiel 2M3a = ({z0, z1, z2}, {a, b}, δ, z0, {z0}) mit
δ(z0, a) = z1, δ(z1, a) = z2, δ(z2, a) = z0,δ(z0, b) = z0, δ(z1, b) = z1, δ(z2, b) = z2.
Zustandsübergangsgraph
47 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines DFA (IV)
Beispiel 2 (Fortsetzung)Dann gilt z.B.
δ̂(z0, ε) = z0 ∈ {z0}δ̂(z0, abaa) = δ̂(δ(z0, a), baa)
= δ̂(z1, baa)= δ̂(δ(z1, b), aa)= δ̂(z1, aa)= δ̂(δ(z1, a), a)= δ̂(z2, a)= δ̂(δ(z2, a), ε)= δ̂(z0, ε)= z0 ∈ {z0}
48 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines DFA (V)
Beispiel 2 (Fortsetzung)
δ̂(z0, bba) = δ̂(z0, ba)= δ̂(z0, a)= z1 6∈ {z0}
Also: ε ∈ L(M3a), abaa ∈ L(M3a), bba 6∈ L(M3a).
49 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines DFA (VI)
Beispiel 3DFA, der die folgende Sprache akzeptiert (mit Σ = {a, b}):
Lb = {w ∈ Σ∗ | w = bw ′ mit w ′ ∈ Σ∗}
Zustandsgraph:
Beachte: z2 („Fehler-“) Zustand,von dem aus kein akzeptierender Zustand mehr erreichbar ist.
50 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang DFA und reguläre Grammatik (I)
Konstruktion: DFA reguläre Grammatik
Sei M = (Z ,Σ, δ, z0,E ) ein DFA.
Konstruiere Grammatik GM = (Z ,Σ,P, z0) mit Regeln:
P : z → az ′ für alle z , z ′ ∈ Z , a ∈ Σ mit δ(z , a) = z ′,z → ε für alle z ∈ E .
GM ist offenbar regulär.
Anschaulich:Zustandsbezeichner zi von M Variablensymbole in GM
Zustandsübergänge Regeln
51 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang DFA und reguläre Grammatik (II)
Beispiel
Für den DFA M3a =({z0, z1, z2}, {a, b}, δ, z0, {z0})mit
δ(z0, a) = z1δ(z0, b) = z0δ(z1, a) = z2δ(z1, b) = z1δ(z2, a) = z0δ(z2, b) = z2
ist GM3a =({z0, z1, z2}, {a, b},P, z0) mit
z0 → az1z0 → bz0z1 → az2z1 → bz1z2 → az0z2 → bz2z0 → ε
Beobachtung: GM3a ist die ursprüngliche Grammatik G3a für L3a(bis auf Bezeichnung der Variablen (hier: „zi“)).
Es gilt also: L(GM3a ) = L3a = L(M3a).52 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang DFA und reguläre Grammatik (III)
Allgemein gilt:
Satz 2.1Für jeden DFA M ist L(GM) = L(M).
Direkt aus diesem Satz folgt insbesondere:
Satz 2.2Jede von einem DFA akzeptierte Sprache ist regulär.
53 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Nichtdeterministische endlicheAutomaten (NFA)
54 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Idee nichtdeterministischer endlicher Automaten (I)
Nichtdeterminismus: erlaube, dass ein Zustand für einEingabesymbol mehrere oder keine Folgezustände hat.
Ziel: Vereinfachung/Unterspezifizierung.Führt zu kleineren oder besser verständlichen Automaten.
55 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Idee nichtdeterministischer endlicher Automaten (II)
Nichtdeterministische Automaten: Zu jedem Paar
(z , a) mit z Zustand, a Eingabesymbol
gibt es entweder keinen, einen oder mehrere Nachfolgezustände.
Nichtdeterministischer Automatwählt aus den möglichen Nachfolgerzuständen immer(nichtdeterministisch) einen aus.akzeptiert ein Wort, falls es bei „richtiger“ Auswahl vomStartzustand in einen Endzustand führt.
56 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Nichtdeterministische endliche Automaten
DefinitionEin nichtdeterministischer endlicher Automat(nondeterministic finite automaton, NFA) ist ein 5-Tupel
M = (Z ,Σ, δ, z0,E ) gegeben durch:
Z ,Σ, z0,E wie bei DFA,eine totale Überführungsfunktion δ : Z × Σ→ ℘(Z ).
℘(Z ) ist die Potenzmenge der Menge der Zustände:δ bildet jedes Paar (z , a) ∈ Z × Σ auf eine Teilmenge von Z ab.(die möglichen Folgezustände von z bei Eingabe von a)
Alternativ: (und equivalent) δ ⊆ (Z × Σ)× Z Relation
57 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ablauf eines NFA (I)
Beispiel
58 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Ablauf eines NFA (II)
Beispiel (Fortsetzung)
59 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Mehr-Schritt-Übergänge eines NFA (I)
Erweiterung von δ auf ganze Wörter w ∈ Σ∗:
Informell: für Zustandsmenge Z ′ ⊆ Z ist δ̂(Z ′,w) die Menge allerZustände, die von Z ′ aus durch Abarbeitung von w erreicht werdenkönnen.
Definition (Mehr-Schritt-Übergänge)Zu einem gegebenen NFA M = (Z ,Σ, δ, z0,E ) definieren wir eineFunktion δ̂ : ℘(Z )× Σ∗ → ℘(Z ) induktiv wie folgt:
δ̂(Z ′, ε) = Z ′ für Z ′ ∈ ℘(Z ),δ̂(Z ′, aw) =
⋃z∈Z ′
δ̂(δ(z , a),w) für Z ′ ∈ ℘(Z ), a ∈ Σ,w ∈ Σ∗.
mit Z ′ ⊆ Z ,w ∈ Σ∗ und a ∈ Σ.
60 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines NFA (I)
DefinitionSei M = (Z ,Σ, δ, z0,E ) ein NFA.M akzeptiert ein Wort w ∈ Σ∗, falls δ̂({z0},w) ∩ E 6= ∅ gilt.Die von M akzeptierte Sprache ist:
L(M) = {w ∈ Σ∗ | M akzeptiert w}.
Von M akzeptierte Sprache:Menge aller Wörter, die M vom Startzustand in einen Endzustandüberführen. (Es kann für ein Wort mehrere Überführungspfade geben.)
Bemerkung: Jeder DFA ist ein (spezieller) NFA.Die graphische Darstellung von NFA ist analog zu der von DFA.
61 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines NFA (II)
BeispielDer NFA Maba sei gegeben durch
Es ist z. B. baabab ∈ L(Maba), denn:
δ̂({z0}, baabab) = δ̂({z0}, aabab)= δ̂({z0, z1}, abab)= δ̂({z0, z1}, bab)= δ̂({z0, z2}, ab)= δ̂({z0, z1, z3}, b)
62 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Akzeptierte Sprache eines NFA (III)
Beispiel (Fortsetzung)
δ̂({z0}, baabab) = · · ·= δ̂({z0, z2, z3}, ε)= {z0, z2, z3}
und {z0, z2, z3} ∩ E 6= ∅.
Allgemeiner gilt (ohne Beweis):
L(Maba) = {w ∈ {a, b}∗ | aba ist Teilwort von w}.
63 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und reguläre Grammatik (I)
Zuvor: Konstruktion DFA reguläre GrammatikJetzt: „Umkehrung“ der Konstruktion liefert:
reguläre Grammatik NFA
64 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und reguläre Grammatik (II)
Konstruktion: Sei G = (V ,Σ,P,S) eine reguläre Grammatik.Der NFA MG ist gegeben durch MG = (V ′,Σ, δ,S,E ) mit
– Zustände von MG :
V ′ =
V ∪ {X} mit X 6∈ V , falls P eine Regel der Form
A→ a enthältV sonst,
– Zustandsübergänge von MG :B ∈ δ(A, a) für Regel A→ aB in P (für B ∈ V ),
X ∈ δ(A, a) für Regel A→ a in P,
– Endzustände von MG :
E ={{A ∈ V | P enthält A→ ε} ∪ {X}, falls X ∈ V ′
{A ∈ V | P enthält A→ ε} sonst.
65 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und reguläre Grammatik (III)
BeispielSei G = ({A,B, S}, {a, b},P,S) mit den Regeln
S → aA | aB | ε,A→ bS | b,B → aS | a.
MG ist dann der NFA
66 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und reguläre Grammatik (IV)
Allgemein gilt:
Satz 2.3Für jede reguläre Grammatik G ist L(MG) = L(G).
Daraus folgt insbesondere:
Satz 2.4Zu jeder regulären Sprache L gibt es einen NFA M mit L(M) = L.
Wir haben nun folgende Konstruktionen beschrieben:
DFA reguläre Grammatik NFA
67 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und DFA (I)
Jetzt: Konstruktion NFA N DFA MN
Idee des Verfahrens:(potenzielle) Zustände von MN :jede Teilmenge der Zustandsmenge des NFA Nkonstruiere die Übergängeeliminiere alle nicht erforderlichen Zustände des DFA MN :nicht erreichbare Teilmengen / Zustände von MN
Beachte:Falls N n Zustände hat, hat MN im schlimmsten Fall 2n Zustände.
68 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und DFA (II)
Potenzmenge-Konstruktion:
Es sei N = (Z ,Σ, δ, z0,E ) NFA.
Dann ist MN = (℘(Z ),Σ, δ′, {z0},E ′) mit
δ′(Z ′, a) =⋃
z∈Z ′δ(z , a) für alle Z ′ ∈ ℘(Z ),
betrachte alle in Z ′ enthaltenen Zustände z ,untersuche welche Zustände N auf Eingabe a von z auserreichtnimm die Vereinigung aller dieser Zustände.
E ′ = {Z ′ ∈ ℘(Z ) | Z ′ ∩ E 6= ∅}Menge der Endzustände von MN :alle Teilmengen von Z , die mindestens einen Endzustand aus Eenthalten.
69 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und DFA (III)
Beispiel
� // q
1��
0 // r
0,1
��
s0//
1??
t 0,1hh
δ′ q r s t{q0} {q0, q1} {q1} ∅
0 {q0, q1} {q0, q1} ∅ ∅1 {q1} {q0, q1} {q0, q1} ∅
final? nein ja ja nein70 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang NFA und DFA (IV)
Es gelten:
Satz 2.5Für jeden NFA N ist L(MN) = L(N).
Satz 2.6Zu jedem NFA M gibt es einen DFA M ′ mit L(M ′) = L(M).
71 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Grammatiken, DFA und NFA (I)
Bisher: drei Formalismen für reguläre Sprachen:reguläre Grammatiken, DFA und NFA.
Vor- und Nachteile der Formalismen:Reguläre Grammatiken
schaffen Verbindung zur Chomsky-Hierarchiewerden zur Erzeugung von Sprachen eingesetztnichtdeterministisch schwieriger zu entscheiden, ob einbestimmtes Wort erzeugt wird
NFAerlauben oft kleine, kompakte Darstellungen von Sprachenhaben intuitive, graphische Notationnichtdeterministisch schwieriger zu entscheiden, ob einbestimmtes Wort akzeptiert wird
72 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Grammatiken, DFA und NFA (II)
DFAkönnen gegenüber äquivalenten NFA exponentiell größerwerdenerlauben eine effiziente Lösung des Wortproblems(einfach Übergänge des Automaten durchführen undüberprüfen, ob ein Endzustand erreicht wird)
Alle Modelle:relativ viel Schreibaufwand und Platz für die Notation.
Gesucht: kompaktere syntaktische Repräsentation reguläre Ausdrücke.
73 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Ausdrücke
74 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Syntax regulärer Ausdrücke
Definition (induktiv)Menge RegΣ der regulären Ausdrücke über Σ(für ein gegebenes Alphabet Σ):
1 ∅ ∈ RegΣ, ε ∈ RegΣ und a ∈ RegΣ für alle a ∈ Σ.2 Falls r , s ∈ RegΣ, dann (r · s), (r + s), r∗ ∈ RegΣ.
Bemerkungen:Schreibe: (r |s) statt (r + s) und (rs) statt (r · s)Anschaulich: (r |s) bzw. (r + s) bedeutet Alternative,
(r · s) bzw. (rs) bedeutet Verkettung und(· · · )∗ bedeutet „beliebig oft“.
Beispiele
(ab|ba)(ab|ba)∗
(ab|ba)c∗(a|b|c)∗abc(a|b|c)∗
75 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Durch regulärer Ausdrücke beschriebene Sprache (I)
Nach Syntax jetzt Semantik regulärer Ausdrücke.(d.h. Bedeutung: welche Sprache beschreibt ein regulärer Ausdruck?)
DefinitionFür r ∈ RegΣ ist die durch r beschriebene Sprache L(r) rekursivdefiniert wie folgt:
1 L(∅) = ∅, L(ε) = {ε}, L(a) = {a} für a ∈ Σ.2 L(r · s) = L(r) ◦ L(s),
L(r + s) = L(r) ∪ L(s),L(r∗) = L(r)∗.
76 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Durch regulärer Ausdrücke beschriebene Sprache (II)
Beispiele für reguläre Ausdrücke über dem Alphabet Σ = {a, b}Beispiel 1: Sprache aller Wörter, die mit a beginnen und mitbb enden.
α = a(a|b)∗bbBeispiel 2: Sprache aller Wörter, die das Teilwort abaenthalten.
α = (a|b)∗aba(a|b)∗
Beispiel 3: Sprache aller Wörter, die eine gerade Anzahl desZeichens a enthalten.
α = (b∗ab∗a)∗b∗
77 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Durch regulärer Ausdrücke beschriebene Sprache (III)
Konventionen: (zur Klammereinsparung)Bindungsregel: „· vor +“.
r · s · t statt (r · s) · t oder r · (s · t) (da „·“) assoziativ)
analog für + bzw. |.
BeispieleSei Σ = {a, b}. Dann gilt:
L(a|b) = ΣL((a|b)∗) = Σ∗
L((ab)∗a) = {(ab)na ∈ Σ∗ | n ∈ N}L(a(a|b)∗b|b) = {w ∈ Σ∗ | w = aw ′b mit w ′ ∈ Σ∗
oder w = b}
78 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Reguläre Sprache und regulärer Ausdruck
Satz 2.7 (Satz von Kleene)Sei Σ ein Alphabet. Eine Sprache L über Σ ist genau dann regulär,wenn es einen regulären Ausdruck r ∈ RegΣ gibt mit L(r) = L.
Bemerkung: der Beweis liefert zwei Konstruktionen:
DFA regulärer Ausdruck DFA
79 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Stephen Cole KleeneAmerikanischer Mathematiker
einer der Begründer der Rekursionstheorie
wichtige Beiträge zur TheoretischenInformatik
Theorie der berechenbaren Funktionen
Bekannte Entdeckungen:
Erfinder der regulären Ausdrücke
Kleene’scher Fixpunktsatz
Kleene’scher Rekursionssatz
Stephen Cole Kleene (1909–1994)Quelle: www.library.wisc.edu
Außerdem nach Kleene benannt:Kleene Stern, Kleene Algebra, Kleene Hierarchie
80 / 82
Lernziele Grammatiken Reguläre Sprachen DFA NFA Reguläre Ausdrücke Zusammenfassung
Zusammenhang reguläre Grammatik, DFA, NFA,regulärer Ausdruck
Satz 2.8Sei L eine Sprache. Die folgenden Aussagen sind äquivalent:a) L wird von einer regulären Grammatik erzeugt
(d.h. L ist regulär).b) L wird von einem DFA akzeptiert.c) L wird von einem NFA akzeptiert.d) L wird durch einen regulären Ausdruck beschrieben.
81 / 82