TheoretischeInformatik für WirtschaftsinformatikundLehramtthinfwil:milius-ti-rs_ho.pdf · LernzieleGrammatikenReguläreSprachenDFANFAReguläreAusdrückeZusammenfassung DieChomsky-Hierarchie(III)

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


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


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


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


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

wissen, wie eine reguläre Sprache erzeugt und akzeptiertwerden kanndie Chomsky-Hierarchie kennen und Eigenschaften der ihrzugeordneten Grammatik-Typen benennen können

6 / 82


Grammatiken

7 / 82


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


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


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


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


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


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


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


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


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


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


Ableitungen (II)

BeispielFür G = (V ,Σ,P, S) mit V = {S,B,C}, Σ = {a, b, c} und P:



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


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


Erzeugte Sprache einer Grammatik (II)

BeispielG = (V ,Σ,P,S) mit V = {S,B,C}, Σ = {a, b, c} und P:



cC → cc

(Ohne Beweis) G erzeugt die Sprache:

L(G) = {anbncn | n ≥ 1}.

20 / 82


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


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


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


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


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


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


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


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


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


Reguläre Sprachen

30 / 82


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


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


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


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


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


Deterministische endlicheAutomaten (DFA)

36 / 82


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


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


Deterministische endliche Automaten (III)

Graphische Notation:

Beispiel: (Σ = {a, b})

39 / 82


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


Ablauf eines DFA (I)

Beispiel

41 / 82


Ablauf eines DFA (II)

Beispiel (Fortsetzung)

42 / 82


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


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


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


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


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


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


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


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


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


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


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


Nichtdeterministische endlicheAutomaten (NFA)

54 / 82


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


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


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


Ablauf eines NFA (I)

Beispiel

58 / 82


Ablauf eines NFA (II)


59 / 82


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


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


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


Akzeptierte Sprache eines NFA (III)


δ̂({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


Zusammenhang NFA und reguläre Grammatik (I)

Zuvor: Konstruktion DFA reguläre GrammatikJetzt: „Umkehrung“ der Konstruktion liefert:

reguläre Grammatik NFA

64 / 82


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


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


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


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


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


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


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


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


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


Reguläre Ausdrücke

74 / 82


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


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


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


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


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


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


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


Zusammenfassung

1 Lernziele

2 Grammatiken

3 Reguläre Sprachen

4 Deterministische endliche Automaten

5 Nichtdeterministische endliche Automaten

6 Reguläre Ausdrücke

7 Zusammenfassung

82 / 82

Documents

TheoretischeInformatik für WirtschaftsinformatikundLehramtthinfwil:milius-ti-rs_ho.pdf · LernzieleGrammatikenReguläreSprachenDFANFAReguläreAusdrückeZusammenfassung DieChomsky-Hierarchie(III)