Zusammenfassung KE2 PDF

Preview

Summary

KE 2 Reguläre Sprachen2 Der Deterministische Endliche Automat Berechnungs- bzw. Beschreibungsmodell für einfache Sprachen liest ein Anfragewort zeichenweise ein o akzeptiert das Eingabewort wenn er in einem akzeptierenden Zustand endet o verwirft das Eingabewort wenn er in einem nicht-akzeptierenden...

Description

KE 2 Reguläre Sprachen 2.1 Der Deterministische Endliche Automat • •

•

• •

• • • •

•

•

• •

Berechnungs- bzw. Beschreibungsmodell für einfache Sprachen liest ein Anfragewort zeichenweise ein o akzeptiert das Eingabewort wenn er in einem akzeptierenden Zustand endet o verwirft das Eingabewort wenn er in einem nicht-akzeptierenden Zustand endet Definition 2.1 — Deterministischer Endlicher Automat. Ein deterministischer endlicher Automat (DEA) M wird durch ein Tupel (Q, Σ, δ, q0, F) dargestellt. Hierbei ist o Q eine endliche nicht-leere Menge, genannt Zustandsmenge, o Σ ein (endliches) Alphabet, o δ eine Funktion δ : Q × Σ → Q, genannt Übergangsfunktion, o q0 ein Element aus Q, genannt Startzustand, o F eine Teilmenge von Q, genannt Menge der akzeptierenden Zustände. Zustandsdiagramm: graphische Notation eines DEA w-Lauf eines DEAs M für ein Wort w ∈ Σ*: o Folge von Zustandsübergängen (qi1, qi2,…qim) mit ▪ q0 = qi1 ▪ w = x1x2x3…xm-1, mit xi ∈ Σ* ▪ δ(qi1,xk) = qik+1 für alle 1 ≤ k < m ein DEA M akzeptiert ein Wort w ∈ Σ* genau dann, wenn der w -Lauf in einem akzeptierenden Zustand endet (akzeptierender Lauf) erreichbare Zustände: alle Zustände, die man im Zustandsdiagramm vom Startzustand erreichen kann nicht-erreichbare Zustand spielen für die Akzeptanz eines Wortes keine Rolle und können immer entfernt werden Definition 2.2 — Iterierte Übergangsfunktion eines DEAs. Sei δ die Übergangsfunktion eines DEAs, dann definieren wir für alle q ∈ Q δ0 (q, ε) = q, und für alle i > 0 und alle Wörter w = ua ∈ Σi mit u ∈ Σi−1 und a ∈ Σ δi (q, w) = δ((δi−1(q, u), a). Schließlich definieren wir die iterierte Übergangsfunktion δ*: Q × Σ* → Q als δ* (q, w) := δ|w|(q, w). Sprache des Automaten: die Menge aller Wörter, die der Automat M akzeptiert, L(M) Definition 2.3 — Sprache eines DEAs. Sei M = (Q, Σ, δ, q0, F) ein DEA, dann ist die von M akzeptierte Sprache definiert als L(M) := {w ∈ Σ* | δ*(q0, w) ∈ F}. Definition 2.4 — Reguläre Sprache. Wenn L eine Sprache ist, für die es einen DEA gibt, der L akzeptiert, nennen wir L eine reguläre Sprache. Wir nutzen die Bezeichnung REG := {L | L ist regulär}. eine Sprache L mit |L| < ∞ heißt endlich Satz 2.1 Jede endliche Sprache ist regulär.

2.2 Nichtdeterministische Endliche Automaten •

•

Erweiterung von Berechnungsmodellen o Berechnungsvorschrift wird mit Freiheiten ausgestattet ▪ Nichtdeterminismus Übergang mir dem gleichen Zeichen in verschiedene Folgezustände möglich ▪ ε-Übergänge Übergang in einen Folgezustand ohne das Lesen eines Zeichens möglich Definition 2.5 — Nichtdeterministischer Endlicher Automat. Ein nichtdeterministischer endlicher Automat (NEA) M wird durch ein Tupel (Q, Σ, δ, q0, F) dargestellt. Hierbei ist

•

• •

•

•

• •

•

•

•

o Q eine endliche nicht-leere Menge, genannt Zustandsmenge, o Σ ein (endliches) Alphabet, o δ eine Funktion δ : Q × (Σ ∪ {ε}) → P(Q), genannt Übergangsfunktion, o q0 ein Element aus Q, genannt Startzustand, o F eine Teilmenge von Q, genannt Menge der akzeptierenden Zustände w-Lauf eines NEAs M für ein Wort w ∈ Σ*: o Folge von Zustandsübergängen (qi1,x1, qi2,x2,…qim) mit ▪ w = x1x2x3…xm-1, mit xi ∈ Σε ▪ δ(qi1,xk) ∋ qik+1 für alle 1 ≤ k < m o ein Wort kann verschiedene Läufe haben! ein NEA M akzeptiert ein Wort w ∈ Σ* genau dann, wenn ein akzeptierender Lauf existiert E(p): die Zustandsmenge der Zustände, die von p aus erreicht werden können, ohne ein Zeichen zu lesen. E(p) := {q | q ist von p durch eine Sequenz von ≥ 0 ε-Übergängen erreichbar} für Mengen P ⊆ Q: E(P) := ⋃ 𝑝∈𝑃 𝐸(𝑝) Definition 2.6 — Iterierte Übergangsfunktion eines NEAs. (gibt an, in welchem Zustand man nach lesen eines Wortes sein könnte) Sei δ die Übergangsfunktion eines NEAs, dann definieren wir für alle P ⊆ Q δ0 (P, ε) = E(P), und für alle i > 0 und alle Wörter w = ua ∈ Σi mit u ∈ Σi−1 und a ∈ Σ δi (P, w) = E( ∪r∈δi−1(P,u) δ(r, a)). Schließlich definieren wir die iterierte Übergangsfunktion δ* : P(Q) × Σ ∗ → P(Q) als δ* (P, w) := δ|w| (P, w). Definition 2.7 — Sprache eines NEAs. Sei N = (Q, Σ, δ, q0, F) ein NEA, dann ist die von N akzeptierte Sprache definiert als L(N) := {w ∈ Σ* | δ* ({q0}, w) ∩ F ≠ ∅}. jede Sprache, die ein NEA akzeptiert, wird auch von einem DEA akzeptiert → Potenzautomat Definition 2.8 — Potenzautomat. Sei N = (Q, Σ, δ, q0, F) ein NEA, dann ist der Potenzautomat zu N ein DEA M = (QP, Σ, δP, qP, FP) mit o QP := P(Q), o δP gegeben durch δP(P, x) := E( ∪p∈P δ(p, x)), o qP := E(q0) und o FP = {P ⊆ Q | ∃p ∈ P: p ∈ F}. Lemma 2.1 Sei N = (Q, Σ, δ, q0, F) ein NEA mit Potenzautomat MP = (QP, Σ, δP, qP, FP). Dann gilt, dass für alle P ⊆ Q und alle w ∈ Σ* δ*P(E(P), w) = δ*(P, w). Satz 2.2 Sei N ein NEA und MP dessen Potenzautomat, dann gilt L(N) = L(MP). Korollar 2.1 Die Sprachen, die von einem NEA akzeptiert werden, sind genau die regulären Sprachen.

2.3 Minimierung von DEAs • • •

•

Vorbemerkung: zwei DEAs M1 und M2 heißen äquivalent, gdw. L(M1) = L(M2) gesucht ist der kleinste (d.h. minimale Anzahl von Zuständen) DEA für eine Sprache L Definition 2.9 — Äquivalenz von Zuständen. Sei M = (Q, Σ, δ, q0, F) ein DEA. Wir nennen zwei Zustände p, q ∈ Q äquivalent, falls für alle w ∈ Σ* gilt, dass δ* (p, w) ∈ F ⇔ δ* (q, w) ∈ F. Wir schreiben in diesem Fall p ≈ q Zwei nicht äquivalente Zustände nennen wir auch trennbar

es muss also ein Wort w ∈ Σ* geben, für das entweder δ*(p, w) ∈ F und δ* (q, w) ∉ F, oder aber δ*(p, w) ∉ F und δ*(q, w) ∈ F. Wir nennen ein solches Wort w Trennwort für das Zustandspaar p, q Die Relation ≈ ist eine Äquivalenzrelation (symmetrisch, reflexiv, transitiv) Für zwei Zustände p, q aus einer Klasse (p≈q) gilt o p∈Fp⇔q∈F o für alle w ∈ Σ* , dass δ* (p, w) ≈ δ* (q, w) Definition 2.10 — Kollabierter Automat. Für einen DEA M = (Q, Σ, δ, q0, F) definieren wir als seinen kollabierten Automaten einen DEA Mˆ = (Qˆ, Σ, δ,ˆ qˆ0, Fˆ) wie folgt: o Qˆ = {[q] | q ∈ Q} o ∀[q] ∈ Qˆ ∀a ∈ Σ: δˆ([q], a) := [δ(q, a)] o qˆ0 = [q0] o Fˆ := {[ f ] | f ∈ F} o

• •

•

Hierbei bezeichnet [q] die Äquivalenzklasse von q bezüglich der ≈ Relation von M.

•

•

•

•

•

•

Lemma 2.2 Sei Mˆ der kollabierte Automat zum DEA M mit Zustandsmenge Q. Dann gilt für alle p, q ∈ Q [p] ≈Mˆ [q] ⇒ [p] = [q]. Hierbei bezieht sich ≈ Mˆ auf die ≈-Relation bezüglich M Myhill–Nerode Relation o hängt nur von der Sprache, nicht vom Modell ab o L muss nicht unbedingt regulär sein Definition 2.11 — Myhill–Nerode Relation. Sei L eine Sprache über dem Alphabet Σ, nicht notwendigerweise regulär. Wir definieren für zwei Wörter u, v ∈ Σ* u ≡L v : ⇔ ∀ w ∈ Σ* : (uw ∈ L ⇔ vw ∈ L) . Die Relation ≡L nennen wir Myhill–Nerode Relation (kurz MN-Relation). Eigenschaften: o 1. ≡L ist symmetrisch Rechtskongruenz o 2. ≡L ist reflexiv o 3. ≡L ist transitiv o 4. für alle a ∈ Σ : u ≡L v ⇒ ua ≡L va o 4‘. für alle w ∈ Σ* : u ≡L v ⇒ uw ≡L vw o 5. u ≡L v ⇒ u ∈ L ⇔ v ∈ L Beispiel: L ist die Sprache von (a+b)*ab(a+b)* (alle Wörter über a,b, die das Teilwort ab enthalten) die Klassen der MN-Relation sind o 1. Klasse [ab] = {w ∈ {a,b}* | w enthält ab} o 2. Klasse [a] = {w ∈ {a,b}* | w endet auf a und enthält nicht ab} o 1. Klasse [ε] = {w ∈ {a,b}* | w endet auf b und enthält nicht ab} ∪ {ε} o [a]∪[ε]∪[ab] = Σ*, d.h. es gibt keine weiteren Klassen Index: Anzahl der Äquivalenzklassen

•

•

•

• •

Definition 2.12 — Myhill–Nerode Automat. Sei L ⊆ Σ* eine Sprache, deren MN-Relation endlichen Index hat. Dann definieren wir den MyhillNerode Automaten ML = (QL, Σ, δL, q0L , FL) zu L wie folgt: o QL := {[w] | w ∈ Σ*} o ∀[w] ∈ QL ∀a ∈ Σ: δL([w], a) := [wa] o q0L := [ε] o FL := {[w] | w ∈ L} Hierbei bezeichnet [w] die Äquivalenzklasse von w bezüglich der MN-Relation von L. Satz 2.4 Sei ML der Myhill–Nerode Automat für die Sprache L, dann gilt o 1. L(ML) = L und o 2. ML ist ein Minimalautomat zu L Satz 2.5 Der kollabierte Automat, in dem alle nicht-erreichbaren Zustände gestrichen wurden, ist ein Minimalautomat. Satz 2.6 — Satz von Myhill–Nerode. Eine Sprache L ist genau dann regulär, wenn ihre MN-Relation einen endlichen Index hat. Table-Filling-Algorithmus o Algorithmus zum effizienten Finden aller äquivalenten Zustände o Datenstruktur: Tabelle T mit |Q| Zeilen und Spalten Q = {1, 2, 3…, n} ▪ wg Symmetrie werden nicht alle Felder bearbeitet o Invariante: Enthält T[p,q] die Markierung 1 dann sind p und q trennbar (p≈q) o T wird nach und nach mit 1en gefüllt bis eine Abbruchbedingung eintritt o am Ende notieren alle nicht markierten Einträge T[p,q] äquivalente Zustandspaare p, q ( Satz 2.7) o Ablauf: ▪ Initialisierung: Setze alle Einträge T[p,q]=1 für die p ∈ F und q ∉ F oder umgekehrt ▪ Suchphase: sehe alle nicht markierten Zustandspaare (p,q) durch wenn a ∈ Σ existiert mit T[δ(p, a), δ(q, a)]=1 dann setze T[p,q]=1 ▪ Abbruchbedingung: wiederhole bis in der Suchphase keine 1 mehr gesetzt wird

2.4 Abschlusseigenschaften Regulärer Sprachen • • •

•

eine Sprachklasse L ist abgeschlossen unter der Operation ⊕, falls für alle L1, L2 ∈ L gilt, dass auch L1 ⊕ L2 aus L ist Satz 2.8: Die regulären Sprachen sind abgeschlossen unter binärer Vereinigung (L 1, L2 ∈ REG ⇒ L1 ∪ L2) Beweis 1: o wenn L1, L2 ∈ REG, dann existieren DEAs M1 und M2 mit L(M1) = L1 und L(M2) = L2 o konstruiere DEA M3, der M1 und M2 simultan und genau dann akzeptiert, wenn einer der beiden anderen DEAs akzeptiert Simulation von L1 und L2 o sei M1 = (Q1, Σ, δ1, q01 , F1), M2 = (Q2, Σ, δ2, q02 , F2) o konstruiere M3 = (Q3, Σ, δ3, q03 , F3) o Idee: Zustände von M3 sind Paare von Zuständen Q1 x Q2 → M3 ist im Zustand (qa,qb) gdw M1 im Zustand qa und M2 im Zustand qb sind (Invariante) o Formal: ▪ Q3 .= Q1 x Q2 ▪ δ3((q1,q2),a) := (q1‘,q2‘), gdw δ1(q1,a) = q1’ und δ2(q2,a) = q2’ ▪ q03 .= (q01,q02) o akzeptierende Zustände: akzeptiere wenn M1 oder M2 akzeptieren ▪ F3 := {(q1,q2) | q1 ∈ F1 oder q2 ∈ F2} ▪

o o

•

•

Einen DEA, dessen Zustandsraum man als Paare von Zuständen anderer Automaten definiert, nennt man Produktautomat

o alternativer Beweis: o M1, M2 wie bisher, konstruiere nun NEA ▪ einfügen eines neuen Startzustands mit ε-Übergängen zu q01 und q02

▪ Satz 2.9 Die regulären Sprachen REG sind unter Konkatenation und Kleene Stern abgeschlossen. o Beweis Konkatenation: M1, M2 wie bisher, konstruiere nun NEA ▪ ε-Übergänge von akzeptierenden Zuständen in M1 zum Startzustand vom M2, „deaktivieren“ der akzeptierenden Zustände von M1

o

o

▪ Beweis Kleene Stern: ▪ M1 wie bisher, konstruiere nun NEA N3 für L1* • neuer Startzugang mit ε-Übergang zu q01 (weil ε ∈ L1* aber nicht ∈ M1) • von akzeptierenden Zuständen im M1 ε-Übergänge zu neuem Startzustand

• L ∈ REG ist auch unter Spiegelung und Komplement abgeschlossen

2.5 Reguläre Ausdrücke • •

•

Formalismus zum Beschreiben von formalen Sprachen Definition 2.13 — Regulärer Ausdruck (RA). Für ein Alphabet Σ bezeichnen wir Wörter über Σ∪ {(, ), ∗, +, ·, ∅, ε}, die nach folgenden Regeln gebildet wurden, als reguläre Ausdrücke: o ∅, ε sind reguläre Ausdrücke o für jedes a ∈ Σ ist a ein regulärer Ausdruck o wenn S und T reguläre Ausdrücke sind, dann auch (S + T), (S · T) und (S) ∗ o wenn Klammern fehlen gilt * vor · vor + Definition 2.14 — Sprache eines Regulären Ausdrucks. Sei R ein regulärer Ausdruck, dann bezeichnen wir dessen Sprache mit L(R). Die Sprache L(R) definiert sich induktiv wie folgt (S und T sind andere RAs). o Falls R = ∅, dann ist L(R) = ∅. o Falls R = a mit a ∈ Σ ∪ {ε}, dann ist L(R) = {a}. o Falls R = (S + T), dann ist L(R) = L(S) ∪ L(T). o Falls R = (S · T), dann ist L(R) = L(S) ◦ L(T). o Falls R = (S) ∗ , dann ist L(R) = L(S) ∗ .

• • •

Satz 2.10 Sei R ein regulärer Ausdruck, dann ist L(R) regulär Satz 2.11 Sei L eine reguläre Sprache, dann existiert ein regulärer Ausdruck R mit L(R) = L vom DEA zum RA: o Ansatz: wenn L ∈ REG, dann existiert ein DEA M der L erkennt ▪ M = (Q, Σ, δ, q0, F) mit Q = {1, 2, …, n} ▪ Ziel: konstruiere RA R mit L(R) = L o Rkij = RA für alle Wörter die vom Zustand i nach j führen ohne einen Zustand > k zu benutzen (Anfangs-/Endzustand dürfen größer k sein)

o o

Konstruktion der Rkij Terme: ▪ Rekursive Konstruktion Man kann vom Zustand i zum Zustand j kommen, ohne über den Zustand k zu laufen. Diese Möglichkeiten werden durch den Ausdruck R (k−1)ij erfasst. Die zweite Möglichkeit ist, vom Zustand i zum Zustand j zu laufen, und dabei (möglicherweise mehrfach) den Zustand k zu durchlaufen. Einen solchen Lauf kann man wie folgt aufspalten: • der erste Teil läuft vom Zustand i zum Zustand k, ohne (dazwischen) einen Zustand größer gleich k zu besuchen (durch R(k−1)ik erfasst) • ein oder mehrere Teile vom Zustand k zum Zustand k, ohne (dazwischen) einen Zustand größer gleich k zu besuchen (durch R (k−1)kk erfasst) • der letzte Teil läuft vom Zustand k zum Zustand j, ohne (dazwischen) einen Zustand größer gleich k zu besuchen (durch R(k−1) kj erfasst) ▪ Basisfall (R0ij): nur direkte Übergänge

▪

R022 = c + ε R013 = ∅ R012 = a Rekursion (Rkij): alle Rk-1ij sind bereits bekannt Beispiel für einen „Lauf“ R6ij:

▪

Rkij = R(k−1)ij + R(k−1)ik (R(k−1)kk )*R(k−1)kj

o

Da wir zur Bestimmung von Rkij nur Ausdrücke mit kleinerem oberen Index benötigen, können wir so alle benötigten Ausdrücke bestimmen. Berechnung mit ansteigendem k (k=0,…,n) aller Rkij Terme:

(2.1)

R = R(n)1f1 + R(n)1f2 + · · · + R(n)1fm F = { f1, f2, . . ., fm} •

Korollar 2.2 — Satz von Kleene. Die Menge der regulären Sprachen und die Menge der Sprachen, die durch einen regulären Ausdruck beschrieben werden können, sind identisch.

2.6 Nachweis von Nichtregularität •

Möglichkeit mit Myhill-Nerode Relation o Sprache mit unendlich vielen Klassen in ihrer Myhill –Nerode Relation nicht regulär sein kann o Pumping-Lemma ▪ strukturelles Lemma über eine Eigenschaft von regulären Sprachen ▪ hat eine Sprache diese Eigenschaft nicht, kann sie nicht regulär sein ▪ Definition 2.15 Eine Sprache L heißt pumpbar, wenn es ein () k ∈ ℕ gibt (Pumplänge), sodass für alle (∀) Wörter w ∈ L mit Mindestlänge k gilt: Es gibt eine Zerteilung () w = xyz, welche die folgenden Eigenschaften erfüllt: • 1. |xy| ≤ k

▪

▪

• 2. |y| > 0 • 3. ∀i ≥ 0: xyiz ∈ L Satz 2.12 — Reguläres Pumpinglemma. Wenn eine Sprache regulär ist, dann ist sie auch pumpbar. (gilt anders herum nicht unbedingt) Beweis Pumping-Lemma: • sei L regulär und M = = (Q, Σ, δ, q0, F) ein DEA, der L erk ennt • wir setzen k = |Q| • jeder w-Lauf (|w| ≥ k) besucht mindestens k+1 = |Q| +1 Zustände, d.h mindestens 1 Zustand wird doppelt besucht • sei p der erste Zustand, der doppelt besucht wird

• •

Überprüfen der Eigenschaften aus dem Pumping-Lemma Beispiel:

|Q| = 5,

k=5

Lauf für w = bbabaa

p = q1 Lauf für xz = baa Lauf für xyyz = bbabbabaa

o

Anwendung des Pumping-Lemmas ▪ PL: L∈ REG ⇒ L ist pumpbar ▪ Umkehrung PL: L nicht pumpbar ⇒ L ∉ REG ▪ nicht pumpbar heißt: • ∀k∈ℕ •  w ∈ L : (|w| ≥ k) • ∀ xyz = w mit |xy| ≤ k, |y| > 0 gilt: •  i > 0 : xyiz ∉ L ▪ Den Nachweis, dass eine Sprache nicht pumpbar ist, kann man auch als 2-

Personen-Spiel formulieren. Das Spiel läuft nach folgenden Regeln ab • 1. Ihr Gegenspieler wählt eine Zahl k ∈ ℕ. • 2. Sie wählen ein Wort w ∈ L, das Mindestlänge k hat. • 3. Ihr Gegenspieler wählt eine Zerteilung w = xyz, mit |xy| ≤ k und y ≠ ε. • 4. Finden Sie ein i ≥ 0, für das xyiz < L — dann haben Sie gewonnen, ansonsten ihr Gegenspieler...