Teil III Reguläre Sprachen und endliche Automaten

Teil III
Reguläre Sprachen und endliche Automaten
Deterministische Endliche Automaten
DFA
Ein deterministischer endlicher Automat (DFA) A über einem Alphabet Σ
wird definiert durch:
1
eine nicht-leere, endliche Menge Q von Zuständen,
2
eine partielle Funktion δ : Q × Σ → Q (die Übergangsfunktion),
3
einen Zustand q0 ∈ Q (dem Startzustand),
4
eine Menge F ⊆ Q von akzeptierenden Zuständen.
Wir schreiben dies als A := (Σ, Q, δ, q0 , F ).
Reguläre Sprachen
DFAs
1/5
Deterministische Endliche Automaten
DFA
Ein deterministischer endlicher Automat (DFA) A über einem Alphabet Σ
wird definiert durch:
1
eine nicht-leere, endliche Menge Q von Zuständen,
2
eine partielle Funktion δ : Q × Σ → Q (die Übergangsfunktion),
3
einen Zustand q0 ∈ Q (dem Startzustand),
4
eine Menge F ⊆ Q von akzeptierenden Zuständen.
Wir schreiben dies als A := (Σ, Q, δ, q0 , F ).
Erweiterte Übergangsfunktion
Erweitere δ zu δ : Q × Σ∗ → Q
durch:
δ(q, ε) := q,
δ(q, aw) := δ (δ (q, a) , w) .
Reguläre Sprachen
DFAs
1/5
Deterministische Endliche Automaten
DFA
Ein deterministischer endlicher Automat (DFA) A über einem Alphabet Σ
wird definiert durch:
1
eine nicht-leere, endliche Menge Q von Zuständen,
2
eine partielle Funktion δ : Q × Σ → Q (die Übergangsfunktion),
3
einen Zustand q0 ∈ Q (dem Startzustand),
4
eine Menge F ⊆ Q von akzeptierenden Zuständen.
Wir schreiben dies als A := (Σ, Q, δ, q0 , F ).
Erweiterte Übergangsfunktion
von A akzeptierte Sprache:
Erweitere δ zu δ : Q × Σ∗ → Q
durch:
δ(q, ε) := q,
L(A) := {w ∈ Σ∗ | δ(q0 , w) ∈ F }
δ(q, aw) := δ (δ (q, a) , w) .
Reguläre Sprachen
Starte in q0 , arbeite w von links
nach rechts ab. Akzeptiere, wenn
am Ende in F .
DFAs
1/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
Reguläre Sprachen
DFAs
2/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
q ∈ Q erreichbar von p ∈ Q: Es ex. w ∈ Σ∗ mit δ(p, w) = q
Reguläre Sprachen
DFAs
2/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
q ∈ Q erreichbar von p ∈ Q: Es ex. w ∈ Σ∗ mit δ(p, w) = q
q ∈ Q ist Sackgasse: von q ist kein akzeptierender Zustand erreichbar
Reguläre Sprachen
DFAs
2/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
q ∈ Q erreichbar von p ∈ Q: Es ex. w ∈ Σ∗ mit δ(p, w) = q
q ∈ Q ist Sackgasse: von q ist kein akzeptierender Zustand erreichbar
q1
b
a
q0
q4
a
b
q3
Reguläre Sprachen
DFAs
2/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
q ∈ Q erreichbar von p ∈ Q: Es ex. w ∈ Σ∗ mit δ(p, w) = q
q ∈ Q ist Sackgasse: von q ist kein akzeptierender Zustand erreichbar
q1
dieser DFA ist nicht vollständig
b
a
q0
q4
a
b
q3
Reguläre Sprachen
DFAs
2/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
q ∈ Q erreichbar von p ∈ Q: Es ex. w ∈ Σ∗ mit δ(p, w) = q
q ∈ Q ist Sackgasse: von q ist kein akzeptierender Zustand erreichbar
q1
a
q0
a, b
b
a
q2
b
dieser DFA ist nicht vollständig
aber wir können ihn
vervollständigen
b
a, b
q4
a
q3
Reguläre Sprachen
DFAs
2/5
Handwerkszeug
Hilfreiche Definitionen
Sei (Σ, Q, δ, q0 , F ) ein DFA.
A ist vollständig, wenn δ total ist.
q ∈ Q erreichbar von p ∈ Q: Es ex. w ∈ Σ∗ mit δ(p, w) = q
q ∈ Q ist Sackgasse: von q ist kein akzeptierender Zustand erreichbar
q1
a
q0
a, b
b
a
q2
b
q3
Reguläre Sprachen
dieser DFA ist nicht vollständig
aber wir können ihn
vervollständigen
b
a, b
a
q4
Lemma
Zu jedem DFA A existiert ein
vollständiger DFA A0 mit
L(A) = L(A0 ).
DFAs
2/5
Reguläre Sprachen
Reguläre Sprache
Klasse aller regulären Sprachen
Sei Σ ein Alphabet. Eine Sprache
L ⊆ Σ∗ heißt regulär, wenn ein
DFA A existiert, der L akzeptiert.
(Also L(A) = L).
REGΣ := {L ⊆ Σ∗ | L ist regulär},
[
REG :=
REGΣ .
Reguläre Sprachen
Σ ist ein Alphabet
REG
3/5
Reguläre Sprachen
Reguläre Sprache
Klasse aller regulären Sprachen
Sei Σ ein Alphabet. Eine Sprache
L ⊆ Σ∗ heißt regulär, wenn ein
DFA A existiert, der L akzeptiert.
(Also L(A) = L).
REGΣ := {L ⊆ Σ∗ | L ist regulär},
[
REG :=
REGΣ .
Σ ist ein Alphabet
Satz
FIN ⊂ REG
Reguläre Sprachen
REG
3/5
Reguläre Sprachen
Reguläre Sprache
Klasse aller regulären Sprachen
Sei Σ ein Alphabet. Eine Sprache
L ⊆ Σ∗ heißt regulär, wenn ein
DFA A existiert, der L akzeptiert.
(Also L(A) = L).
REGΣ := {L ⊆ Σ∗ | L ist regulär},
[
REG :=
REGΣ .
Σ ist ein Alphabet
Satz
FIN ⊂ REG
FIN ⊆ REG: Übung
FIN 6= REG: Einfach.
Reguläre Sprachen
REG
3/5
Reguläre Sprachen
Reguläre Sprache
Klasse aller regulären Sprachen
Sei Σ ein Alphabet. Eine Sprache
L ⊆ Σ∗ heißt regulär, wenn ein
DFA A existiert, der L akzeptiert.
(Also L(A) = L).
REGΣ := {L ⊆ Σ∗ | L ist regulär},
[
REG :=
REGΣ .
Σ ist ein Alphabet
Satz
FIN ⊂ REG
FIN ⊆ REG: Übung
FIN 6= REG: Einfach.
Ist eigentlich jede Sprache regulär?
Reguläre Sprachen
REG
3/5
Nicht-reguläre Sprachen
Pumping-Lemma
Sei Σ ein Alphabet. Für jede reguläre Sprache L ⊆ Σ∗ existiert eine
Pumpkonstante nL ∈ N>0 , so dass für jedes Wort z ∈ L mit |z| ≥ nL
folgende Bedingung erfüllt ist: Es existieren Wörter u, v, w ∈ Σ∗ mit
1
uvw = z,
2
|v| ≥ 1,
3
|uv| ≤ nL ,
4
und für alle i ∈ N ist uv i w ∈ L.
Reguläre Sprachen
REG
4/5
Nicht-reguläre Sprachen
Pumping-Lemma
Sei Σ ein Alphabet. Für jede reguläre Sprache L ⊆ Σ∗ existiert eine
Pumpkonstante nL ∈ N>0 , so dass für jedes Wort z ∈ L mit |z| ≥ nL
folgende Bedingung erfüllt ist: Es existieren Wörter u, v, w ∈ Σ∗ mit
1
uvw = z,
2
|v| ≥ 1,
3
|uv| ≤ nL ,
4
und für alle i ∈ N ist uv i w ∈ L.
Beweisidee
1
zu jedem L ∈ REG existiert ein DFA A mit L(A) = L
2
ist w ∈ L länger als Zahl der Zustände, kommt beim Akzeptieren von
w mindestens ein Zustand qm doppelt vor
3
qm ist Teil einer Schleife, benutze Schleife zum Pumpen.
Reguläre Sprachen
REG
4/5
Anwendung des Pumping-Lemmas
Ansatz
Zu zeigen: L ∈
/ REG
Angenommen, L ∈ REG. Dann existiert Pumpkonstante nL .“
”
Konstruiere passendes z ∈ L, |z| ≥ nL
Zeige: Jede Zerlegung von z in u, v, w, die dem Pumping-Lemma
entspricht, führt bei geeigneter Wahl von i zu einem Widerspruch.
Reguläre Sprachen
REG
5/5
Anwendung des Pumping-Lemmas
Ansatz
Zu zeigen: L ∈
/ REG
Angenommen, L ∈ REG. Dann existiert Pumpkonstante nL .“
”
Konstruiere passendes z ∈ L, |z| ≥ nL
Zeige: Jede Zerlegung von z in u, v, w, die dem Pumping-Lemma
entspricht, führt bei geeigneter Wahl von i zu einem Widerspruch.
Bitte beachten!
Das Pumping-Lemma kann nur zum Beweis von Nicht-Regularität
verwendet werden, nicht für den Beweis von Regularität!
Reguläre Sprachen
REG
5/5
Anwendung des Pumping-Lemmas
Ansatz
Zu zeigen: L ∈
/ REG
Angenommen, L ∈ REG. Dann existiert Pumpkonstante nL .“
”
Konstruiere passendes z ∈ L, |z| ≥ nL
Zeige: Jede Zerlegung von z in u, v, w, die dem Pumping-Lemma
entspricht, führt bei geeigneter Wahl von i zu einem Widerspruch.
Bitte beachten!
Das Pumping-Lemma kann nur zum Beweis von Nicht-Regularität
verwendet werden, nicht für den Beweis von Regularität!
Außerdem:
Manchmal hat das Pumping-Lemma keine Chance:
2
L := {bi aj | i ∈ N>0 , j ∈ N} ∪ {ak | k ∈ N}
Reguläre Sprachen
REG
5/5

Download Report