close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

3.0 VU Formale Modellierung Was Sie letzte Woche hörten Formale

EinbettenHerunterladen
Was Sie letzte Woche hörten
3.0 VU Formale Modellierung
4. Endliche Automaten
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
Gernot Salzer
27.3.2012
Einleitung
Anwendungsbeispiele
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
Büchi-Automaten
1
Formale Sprachen
2
Was Sie letzte Woche hörten
Σ
Alphabet, d.h., endliche, nicht-leere Menge atomarer Symbole
w
Wort über Σ, (endliche) Folge von Zeichen aus dem Alphabet Σ
ε
Leerwort
+
Σ
Menge aller nicht-leeren endlichen Wörter über Σ
Σ∗ Menge aller endlichen Wörter über Σ (inklusive Leerwort)
Σω Menge aller unendlichen Wörter über Σ
w1 · w2 = w1 w2 Verkettung der Wörter w1 , w2 ∈ Σ∗
L ⊆ Σ∗ formale Sprache über Σ
∗
2Σ Menge aller Sprachen über Σ
4. Endliche Automaten
4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
4.7.
Σ∗ , ·, ε bildet ein Monoid.
Einleitung
Anwendungsbeispiele
Grundlagen formaler Sprachen
Deterministische endliche Automaten
Nichtdeterministische endliche Automaten
Transducer
Büchi-Automaten
Σ = {0, 1}
Σ∗ = {ε, 0, 1, 00, 01, 10, 11, 000, 001, . . . }
10 · ε · 11101 · 000 = 1011101000 (Klammerung irrelevant, Assoziativität!)
ε·ε·ε=ε
3
4
Endliche Automaten
Übergangsfunktionen und -relationen
Bezeichnungen
δ: Q × Σ → Q
det. endlicher Automat (DEA)
det. Büchi-Automat
δ ⊆Q×Σ×Q
(δ : Q × Σ → 2Q )
nichtdet. endl. Aut. (NEA) ohne ε-Ü.
nichtdet. Büchi-Automat
Q
q0
I
F
endliche Menge von Zuständen
Anfangszustand
Menge von Anfangszuständen
Menge von Endzuständen
Σ
Γ
Eingabealphabet
Ausgabealphabet
δ
δ∗
γ
γ∗
Übergangsfunktion/-relation
erweiterte Übergangsfunktion/-relation
Ausgabefunktion
erweiterte Ausgabefunktion
A
L(A)
[A]
Automat
die von A akzeptierte Sprache
die von A berechnete Übersetzungsfunktion/-relation
δ ⊆ Q × (Σ ∪ {ε}) × Q
(δ : Q × (Σ ∪ {ε}) → 2Q )
nichtdet. endl. Aut. (NEA) mit ε-Ü.
δ: Q × Σ → Q γ: Q × Σ → Γ
(δ : Q × Σ → Γ × Q)
Mealy-Automat
δ ⊆ Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) × Q
(δ : Q × (Σ ∪ {ε}) → 2(Γ∪{ε})×Q )
Transducer (indet. mit ε-Ü.)
δ: Q × Σ → Q
Moore-Automat
γ: Q → Γ
ε-Übergänge, Relation oder Potenzmenge =⇒ nichtdeterm. Automat
5
6
Was Sie heute erwartet
Akzeptierte Worte bzw. Wortpaare
(Nicht-)Deterministischer Automat:
Alle Worte, mit denen man vom Anfangszustand aus einen der
Endzustände erreicht.
4. Endliche Automaten
Büchi-Automat:
Alle unendlichen Worte, mit denen man vom Anfangszustand aus
unendlich oft einen der Endzustände erreicht.
4.8. Beispiel: Flussüberquerung
5. Reguläre Sprachen
Transducer:
Alle Paare (u, v ) von Ein-/Ausgabewörtern, bei denen man mit u vom
Anfangszustand (von einem der Anfangszustände) aus in einen
Endzustand gelangt und dabei v ausgibt.
Mealy: Pro Übergang wird genau ein Symbol gelesen und eines
geschrieben. Die Ausgabe ist an den Übergang gebunden.
Moore: Pro Übergang wird genau ein Symbol gelesen und eines
geschrieben. Die Ausgabe ist an den Zustand gebunden.
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
6. Kontextfreie Grammatiken
6.1. Definition
6.2. Beispiele
7
8
Beispiel: Flussüberquerung
Zustandsübergänge:
b, k, w , z . . . Bauer fährt alleine/mit Kraut/Wolf/Ziege über den Fluss
¯ k,
¯ w
b,
¯ , z¯ . . . Bauer fährt alleine/mit Kraut/Wolf/Ziege retour
¯ k,
¯ w
Σ = {b, k, w , z, b,
¯ , z¯} . . . Eingabealphabet
Ein Bauer kommt mit einem Wolf, einer Ziege und einem Krautkopf an
einen Fluss. Für die Überquerung ist ein kleines Boot vorhanden, mit dem
der Bauer jeweils nur eines der Tiere oder das Gemüse transportieren
kann. Allerdings darf er weder den Wolf mit der Ziege noch die Ziege mit
dem Kraut alleine an einem Flussufer zurücklassen, da sonst der Wolf die
Ziege bzw. die Ziege das Kraut frisst.
z¯
Automat A:
k
bwz
(ohne Fehlerzustände)
Wie gelangen alle wohlbehalten an das andere Ufer?
z
wk
bz
bwzk
Relevante Systemkomponenten: Bauer (b), Wolf (w ), Ziege (z),
Krautkopf (k), Boot, 2 Flussseiten
(Boot ist immer dort, wo der Bauer ist.)
¯
b
. . . Anfangszustand,
bk bw kz wz
, , ,
wz kz bw bk
bwzk
z¯
b
z¯
w
z
¯
b
z
bwk
k
k¯
k
k¯
bz
wk
w
¯
b
bwzk
z¯
bwz
k
z
9
Was Sie heute erwartet
¯ z¯k bz,
¯ . . . , z¯
¯ bw
¯ z¯k bz,
¯ . . . , z bw
¯ z¯k w
¯ z¯k bz,
¯ ...}
L(A) = {z bw
z z bb
¯ z kw
10
Operationen auf formalen Sprachen
Σ Alphabet, d.h., endliche, nicht-leere Menge atomarer Symbole
w Wort über Σ, (endliche) Folge von Zeichen aus dem Alphabet Σ
ε
Leerwort
∗
Σ Menge aller endlichen Wörter über Σ (inklusive Leerwort)
w · w = ww Verkettung der Wörter w , w ∈ Σ∗
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
z
w
bzk
. . . Endzustand
. . . verbotene Zustände
w
¯
bwk
z
Lebewesen hüben
Beschreibung des momentanen Systemzustandes: Lebewesen
drüben
Wer befindet sich gerade auf welcher Seite des Flusses?
bwzk
w
bzk
w
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
Seien L, L ⊆ Σ∗ zwei Sprachen.
L ∪ L = { w | w ∈ L oder w ∈ L }
Vereinigung
L · L = { w · w | w ∈ L, w ∈ L }
Verkettung
L0 = {ε}
Ln+1 = L · Ln
6. Kontextfreie Grammatiken
6.1. Definition
6.2. Beispiele
L+ =
L∗ =
11
n≥1
n≥0
(n ≥ 0)
Potenzen
Ln
Ln = L0 ∪ L+ = {ε} ∪ L+ Kleene-Stern
12
Verkettung
Potenzen von {a, 42}
L
L0
L1
L2
L3
{a, b} · {b, c, d} = {ab, ac, ad, bb, bc, bd}
{b, c, d} · {a, b} = {ba, bb, ca, cb, da, db}
({a, b} · {1, 2}) · {#, $} = {a1#, a1$, a2#, a2$, b1#, b1$, b2#, b2$}
= {a, b} · ({1, 2} · {#, $})
{a, b} · {ε} = {a · ε, b · ε} = {a, b} = {ε · a, ε · b} = {ε} · {a, b}
= {a, 42}
= {ε}
= L · L0 = L · {ε} = L = {a, 42}
= L · L1 = L · L = {aa, a42, 42a, 4242}
= L · L2 = {aaa, aa42, a42a, a4242, 42aa, 42a42, 4242a, 424242}
..
.
L+ = n≥1 Ln = L1 ∪ L2 ∪ L3 ∪ · · ·
= {a, 42, aa, a42, 42a, 4242, aaa, aa42, a42a, a4242, 42aa, . . . }
∗
L = n≥0 Ln = L0 ∪ L1 ∪ L2 ∪ L3 ∪ · · ·
= {ε, a, 42, aa, a42, 42a, 4242, aaa, aa42, a42a, a4242, 42aa, . . . }
{a, b} · {} = {} · {a, b} = {}
{ε} · {ε} = {ε}
{} · {} = {ε} · {} = {} · {ε} = {}
Beobachtungen:
Potenzen eines Alphabets Σ
Sprachverkettung ist nicht kommutativ.
Sprachverkettung ist assoziativ.
{ε} ist neutrales Element bzgl. Sprachverkettung.
{} ist Nullelement bzgl. Sprachverkettung.
13
2Σ , ∪, ·, {}, {ε} bildet einen idempotenten Halbring
Σ0 = {ε}
Σn
Σ+ = n≥1 Σn
Σ∗ = n≥0 Σn
Σ1 = Σ
alle Σ-Wörter der Länge n (d.h., mit n Symbolen)
alle Σ-Wörter ohne Leerwort
alle Σ-Wörter mit Leerwort
14
Was Sie heute erwartet
∗
Das heißt, es gelten folgende Gleichungen.
2Σ , ∪, {} . . . idemp.komm.Monoid
∗
(A ∪ B) ∪ C = A ∪ (B ∪ C )
{} ∪ A = A ∪ {} = A
A∪B =B∪A
A∪A=A
2Σ , ·, {ε} . . . Monoid
∗
4. Endliche Automaten
(A · B) · C = A · (B · C )
{ε} · A = A · {ε} = A
4.8. Beispiel: Flussüberquerung
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
Verkettung distribuiert über Vereinigung.
A · (B ∪ C ) = (A · B) ∪ (A · C )
(B ∪ C ) · A = (B · A) ∪ (C · A)
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
6. Kontextfreie Grammatiken
{} ist Nullelement bzgl. Verkettung.
6.1. Definition
6.2. Beispiele
{} · A = A · {} = {}
Weitere Identitäten für + und ∗:
(A∗ )∗ = A∗
(A ∪ {ε})∗ = A∗
A∗ · A = A+
A+ ∪ {ε} = A∗
15
16
Reguläre Sprachen
Regulären Sprachen über einem Alphabet
Die Menge der regulären Sprachen über Σ, Lreg (Σ), ist die kleinste
Menge, sodass gilt:
Alle Sprachen, die aus einem Alphabet mit Hilfe von Vereinigung,
Verkettung und Stern gebildet werden können.
{}, {ε} und {s} sind reguläre Sprachen (für alle s ∈ Σ).
Anwendungen:
Wenn L und L reguläre Sprachen sind, dann auch L ∪ L , L · L und L∗ .
Betriebssytem-Shells: Dos („Wildcards“), Unix-Shells (wie sh, csh,
ash, bash, zsh), . . .
Reellen Numerale: reguläre Sprache über Σ = {0, . . . , 9, ., E, +, -}
Unix Kommandozeilenprogramme: grep, awk, ed, sed, . . .
Editoren: vi, emacs, . . .
Compilerbau: Tokens bilden reguläre Sprache, die durch sog. Scanner
(Lexer) wie lex oder flex verarbeitet werden.
Programmiersprachen: Perl, Tcl, Php, Python, Ruby, R, Java,
JavaScript, .Net-Sprachen, . . .
Websprachen: Xml Schema, XQuery, XPath, Dtds, . . .
Datenbanken: MySQL, Oracle, PostgreSQL, . . .
...
Wichtig: Unterscheide Symbole des Alphabets von Meta-Symbolen!
0, . . . , 9, ., E, +, - . . . Symbole des Alphabets
ε, real, scale, digit . . . Meta-Symbole
18
17
Was Sie heute erwartet
Reguläre Ausdrücke
Ausdrücke wie digit · digit ∗ und digit + sind ununterscheidbar: Beides sind
semantische Beschreibungen der Menge aller Ziffernfolgen. Um Aussagen
über ihre Form treffen zu können, benötigen wir eine formale Sprache.
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
Reguläre Ausdrücke (algebraische Notation)
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
real = digit · digit ∗ · {.} · digit ∗ · ({ε} ∪ scale)
scale = {E} · {+, -, ε} · digit · digit ∗
digit = {0, . . . , 9} = {0} ∪ · · · ∪ {9}
Die regulären Ausdrücke über Σ sind die kleinste Menge, für die gilt:
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
∅, ε und s sind reguläre Ausdrücke (für alle Symbole s ∈ Σ).
Sind r und r reguläre Ausdrücke, dann auch (r + r ), (rr ) und r ∗ .
Vereinfachte Klammerung: + bindet am schwächsten, ∗ am stärksten.
Keine Klammern bei gleichartigen Operatoren (wegen Assoziativität).
6. Kontextfreie Grammatiken
Die Sprache L(r ) zu einem regulären Ausdruck r ist definiert durch:
6.1. Definition
6.2. Beispiele
19
L(∅) = {}
L(ε) = {ε}
L(s) = {s} für s ∈ Σ
L((r + r )) = L(r ) ∪ L(r )
L((rr )) = L(r ) · L(r )
L(r ∗ ) = (L(r ))∗
20
Regulärer Ausdruck für die reellen Numerale
Zwei reguläre Ausdrücke r und r heißen äquivalent, geschrieben r = r ,
wenn L(r ) = L(r ) gilt.
DD ∗ .D ∗ (ε
R=
+ S)
S = E(+ + - + ε)DD ∗
D = 0 + 1 + ··· + 9
((a + b)∗ + ε)∗ = (a + b)∗
(R, S und D sind Abkürzungen für die jeweiligen regulären Ausdrücke.)
L(((a + b)∗ + ε)∗ ) = · · ·
= ({a, b}∗ ∪ {ε})∗
= ({a, b}∗ )∗
da ε ∈ L∗ für alle L
= ({a, b}∗ )0 ∪ ({a, b}∗ )1 ∪ ({a, b}∗ )2 ∪ · · ·
= {a, b}∗ ∪ ({a, b}∗ )0 ∪ ({a, b}∗ )2 ∪ · · ·
= {a, b}∗
da L∗ alle Wörter über L enthält
= ···
= L((a + b)∗ )
Die zugehörigen Sprachen:
L(D) = L(0 + 1 + · · · + 9)
= L(0) ∪ L(1) ∪ · · · ∪ L(9)
= {0} ∪ {1} ∪ · · · ∪ {9}
= digits
L(S) = L(E(+ + - + ε)DD ∗ )
= L(E) · L(+ + - + ε) · L(D) · L(D ∗ )
= {E} · (L(+) ∪ L(-) ∪ L(ε)) · digits · L(D)∗
= {E} · ({+} ∪ {-} ∪ {ε}) · digits · digits ∗
= scale
L(R) = · · · = real
22
21
Reguläre Ausdrücke in Ebnf-Notation
Reguläre Ausdrücke als Syntaxdiagramme
Ebnf . . . Erweiterte Backus-Naur-Form (Formalismus zur Beschreibung
der Syntax von Programmiersprachen, die reguläre Ausdrücke zulässt)
Syntaxdiagramme . . . graphische Form der Ebnf
AB
A|B
[A]
{A}
(A)
"s"
A·B
A∪B
{ε} ∪ A
A∗
(A)
{s}
Aufeinanderfolge
Alternativen
Option
Wiederholung
Gruppierung
Symbol
A
A
s
{s}
Symbol
X
X+
Wiederholung ≥ 1
X∗
Wiederholung ≥ 0
X
Aufeinanderfolge
X
Y
X ·Y
X ∪Y
Alternativen
X
{ε} ∪ X
X
Reelle Numerale in Ebnf-Notation
real = digit { digit } "." { digit } [ scale ]
scale = "E" [ "+" | "-" ] digit { digit }
digit = "0" | "1" | "2" | · · · | "9"
23
Abkürzung
Y
Option
24
Reguläre Ausdrücke im informatischen Alltag
Reelle Numerale als Syntaxdiagramm
digit
.
digit
real =
scale
grep -E -e "regexp" file
liefert alle Zeilen der Datei file, die eine Zeichenkette enthalten, die dem
regulären Ausdruck regexp (in Posix ERE Syntax) entspricht.
3
digit
E
(Donald E. Knuth)
1
2
+
scale =
Unix := „30 definitions of regular expressions living under one roof“
0
4
-
Verschiedene „Standards“:
5
digit =
Posix Basic Regular Expressions
6
Posix Extended Regular Expressions
7
Perl Regular Expressions
8
...
9
25
Was Sie heute erwartet
Posix Extended Regular Expressions (Ere)
regexp
\s
s
.
ˆ
$
[s1 · · · sn ]
[ˆs1 · · · sn ]
(r )
trifft zu auf
Zeichen s
s, falls kein Sonderzeichen
alle Zeichen
Zeilenanfang
Zeilenende
ein Zeichen aus {s1 , . . . , sn }
alle Zeichen außer s1 , . . . , sn
r
26
regexp
rr
r |r
r*
r+
r?
r {i}
r {i,}
r {i,j}
trifft zu auf
r gefolgt von r
r oder r
≥ 0 Mal r
≥ 1 Mal r
≤ 1 Mal r
i Mal r
≥ i Mal r
i bis j Mal r
Reelle Numerale als Ere
[0-9]
digit = {0, . . . , 9}
E[+-]?[0-9]+
scale = {E} · {+, -, ε} · digit · digit ∗
real = digit · digit ∗ · {.} · digit ∗ · ({ε} ∪ scale)
^[0-9]+\.[0-9]*(E[+-]?[0-9]+)?$
[0-9] . . . Kurzform von [0123456789]; analog [a-zA-Z] für Buchstaben27
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
6. Kontextfreie Grammatiken
6.1. Definition
6.2. Beispiele
28
Eigenschaften regulärer Sprachen
Ausdruckskraft regulärer Sprachen
Reguläre Sprachen sind abgeschlossen gegenüber
Die regulären Sprachen sind genau jene, die von endlichen Automaten
akeptiert werden, d.h.:
Vereinigung, Verkettung und Stern (warum?)
Durchschnitt, Komplement, Differenz, Homomorphismen,
Quotientenbildung, . . .
Zu jedem regulären Ausdruck r gibt es einen endlichen Automaten A,
sodass L(A) = L(r ) gilt.
Zu jedem endlichen Autmaten A gibt es einen regulären Ausdruck r ,
sodass L(r ) = L(A) gilt.
Entscheidbarkeit eines Problems: Es gibt ein Verfahren (einen
Algorithmus), der für jede Eingabe die richtige Antwort ja/nein liefert.
Nicht entscheidbar: Halteproblem Ihrer Lieblingsprogrammiersprache
Nicht regulär sind Sprachen, deren Analyse ein unbegrenztes Gedächtnis
erfordert:
Gegeben ein Programm mit einer Eingabe, wird es anhalten?
Klammerausdrücke: {(), (()), ()(), ((())), (())(), ()()(), . . . }
Folgende Probleme regulärer Sprachen sind entscheidbar:
Gegeben ein Wort w und einen regulären Ausdruck r , gilt w ∈ L(r )?
(Wortproblem)
Gegeben zwei reguläre Ausdrücke r und r , gilt r = r ?
(Äquivalenzproblem)
Gegeben einen regulären Ausdruck r , ist L(r ) leer/endlich/unendlich?29
Was Sie heute erwartet
{ an bn | n ≥ 0 } = {ε, ab, aabb, aaabbb, . . . }
{ an bn cn | n ≥ 0 } = {ε, abc, aabbcc, aaabbbccc, . . . }
Palindrome: Worte, die identisch mit ihrem Spiegelbild sind.
{otto, anna, reliefpfeiler, o genie der herr ehre dein ego, . . . }
Doppelworte: { ww | w ∈ Σ∗ } (falls |Σ| > 1)
Vom regulären Ausdruck zum Automaten
Automat für ∅:
i
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
Automat für r1 + r2 :
Automat für r1
f
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
Automat für r1 r2 :
i
6. Kontextfreie Grammatiken
ε
i
i1
i2
ε
f1
f1
ε
f
Automat für r2
Automat für r1
Automat für r1∗ :
6.1. Definition
6.2. Beispiele
i1
ε
Automat für s ∈ Σ ∪ {ε}:
s
i
f
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
30
f2
ε
Automat für r2
ε
i2
ε
f
f2
ε
f
ε
Automat für r1
i
31
ε
i1
f1
ε
32
Was Sie heute erwartet
Automat für Binärnumerale ohne führende Null
Regulärer Ausdruck: 1(0 + 1)∗
ε
1
ε
ε
ε
0
ε
ε
1
ε
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
ε
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
ε
0,1
Minimaler deterministischer Automat:
1
6. Kontextfreie Grammatiken
Manuelle Konstruktion von Automaten:
1
2
6.1. Definition
6.2. Beispiele
Konstruiere die Automaten zu einfachen Teilsprachen „durch
Hinschauen“.
Verwende die allgemeine Konstruktion mit ε-Übergängen für
undurchsichtige Situationen.
33
Vom Automaten zum regulären Ausdruck
34
Umwandlung eines endlichen Automaten in einen verallgemeinerten
Übergänge in den Anfangszustand oder Anfangszustand ist
Endzustand:
R . . . Menge der regulären Ausdrücke über Σ
Verallgemeinerter endlicher Automat
=⇒
. . . wird beschrieben durch ein 5-Tupel A = Q, Σ, δ, i, f , wobei
Q . . . endliche Zustandsmenge
ε
Mehrere Endzustände:
Σ . . . Eingabealphabet
δ : (Q − {f }) × (Q − {i}) → R . . . Übergangsfunktion
=⇒
i ∈ Q . . . Anfangszustand
ε
ε
ε
Übergänge weg vom Endzustand:
f ∈ Q, f = i . . . Endzustand
Unterschiede zu „normalen“ Automaten:
keine Übergänge in den Anfangszustand;
nur ein Endzustand, der nicht Anfangszustand ist;
keine Übergänge weg vom Endzustand;
nur ein Übergang zwischen je zwei Zuständen;
Übergänge beschriftet mit regulären Ausdrücken.
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
=⇒
35
ε
Mehrere Übergänge zwischen zwei Zuständen:
s1
s1 + s2
=⇒
s2
36
Vom verallgemeinerten Automaten zum regulären Ausdruck
Gegeben: Verallgemeinerter Automat A = Q, Σ, δ, i, f
Für jeden Zustand q ∈ Q − {i, f } führe folgende Schritte durch:
1
Füge zwischen allen Nachbarn p, p von q neue Übergänge hinzu:
y
y
p
x
z
q
p
=⇒
p
x
z
q
Anmerkungen:
Falls p und p derselbe Knoten sind, erhält man:
y
xy ∗ z
y
x
x
p
q
p
q
=⇒
z
z
Falls die Schleife mit dem Ausdruck y nicht existiert, entfällt y ∗ .
p
Falls der Übergang p–p bereits existiert, wird xy ∗ z addiert.
xy ∗ z
(x , y und z bezeichnen reguläre Ausdrücke.)
Entferne q und alle Kanten von und nach q aus dem Automaten.
r
i
f
Restautomat:
2
Ergebnis: r ist ein regulärer Ausdruck mit L(r ) = L(A).
37
A
a
38
1
0,1
0
0
A
b
1
c
a
1
0,1
0
0
b
1
c
1
1
1
0+1
i
ε
a
0
b
1
0
c
ε
i
f
ε
a
0
ε
39
0
00
b
0+1
1 + 01
c
ε
f
ε
39
A
a
1
0,1
0
0
A
b
1
c
a
1
0,1
0
0
b
1
c
1
00 + (1 + 01)(0 + 1)
0+1
i
b
1 + 01
00 + (1 + 01)(0 + 1)
c
ε
i
f
ε + 1 + 01
0 + 1(0 + 1)
b
0 + 1(0 + 1)
1
a
39
Was Sie heute erwartet
1
0,1
0
0
ε + 1 + 01
1 + (0 + 1(0 + 1))(00 + (1 + 01)(0 + 1))∗ (ε + 1 + 01)
39
A
f
b
1
c
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
5. Reguläre Sprachen
i
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
f
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
6. Kontextfreie Grammatiken
6.1. Definition
6.2. Beispiele
1 + (0 + 1(0 + 1))(00 + (1 + 01)(0 + 1))∗ (ε + 1 + 01)
r = 1 + (0 + 10 + 11)(00 + 10 + 11 + 010 + 011)∗ (ε + 1 + 01)
Es gilt: L(r ) = L(A).
39
40
Kontextfreie Grammatiken
Kontextfreie Grammatik
. . . wird beschrieben durch ein 4-Tupel G = V , T , P, S , wobei
Menge von Ersetzungsregeln
V . . . Menge der Nonterminalsymbole (Variablen)
2 Arten von Symbolen: Terminale, Nonterminale
T . . . Menge der Terminalsymbole (V ∩ T = {})
Ausgehend vom Start-Nonterminal werden Nonterminale solange
ersetzt, bis nur noch Terminale bleiben.
Satz → HwP ZwP
HwP → Art Hw
ZwP → Hzw HwP Zw
Satz ⇒p
⇒p
⇒p
⇒p
Art
Hw
Hzw
Zw
P ⊆ V × (V ∪ T )∗ . . . Produktionen
S ∈ V . . . Startsymbol
→ der | den
→ Hund | Mond
→ wird
→ anbellen
Schreibweise: A → w
statt (A, w ) ∈ P
A → w1 | · · · | wn statt A → w1 , . . . , A → wn
Ableitbarkeit
v ist in einem Schritt aus u ableitbar, geschrieben u ⇒ v , falls es Worte
x , y ∈ (V ∪ T )∗ und eine Produktion A → w ∈ P gibt, sodass u = xAy
und v = xwy .
HwP ZwP
Art Hw Hzw HwP Zw
der Hund wird Art Hw anbellen
der Hund wird den Mond anbellen
v ist in mehreren Schritten aus u ableitbar, geschrieben u ⇒ v , falls
∗
u = v , oder
41
L(G) = { w ∈ T ∗ | S ⇒ w }
∗
42
Linksableitbarkeit: xAy ⇒L xwy falls A → w ∈ P und x ∈ T ∗
(In jedem Schritt wird die linkeste Variable ersetzt.)
Grammatiken G1 und G2 heißen äquivalent, wenn L(G1 ) = L(G2 ) gilt.
Rechtsableitbarkeit: xAy ⇒R xwy falls A → w ∈ P und y ∈ T ∗
(In jedem Schritt wird die rechteste Variable ersetzt.)
G = {S}, {a, b}, {S → ε | a S b}, S
∗
∗
Verschiedene Ableitbarkeitsbegriffe
Von Grammatik G generierte Sprache
S ⇒ aabb, weil
u ⇒ u und u ⇒ v für ein Wort u ∈ (V ∪ T )∗ .
Parallelableitbarkeit: x0 A1 x1 · · · An xn ⇒P x0 w1 x1 · · · wn xn
falls A1 → w1 , . . . , An → wn ∈ P und x0 , . . . , xn ∈ T ∗
(In jedem Schritt werden alle Variablen ersetzt.)
S ⇒ a S b ⇒ aa S bb ⇒ aa ε bb ⇒ aabb
L(G) = { an bn | n ≥ 0 } = {ε, ab aabb aaabbb, . . . }
⇒L , ⇒R und ⇒P sind eingeschränkte Ableitungsrelationen:
∗
∗
Manche Wörter w ∈ (V ∪ T )∗ sind mit ⇒ herleitbar (S ⇒ w ),
aber nicht mit diesen Relationen.
∗
Kontextfreie Sprachen
Eine Sprache heißt kontextfrei, wenn es eine kontextfreie Grammatik gibt,
die sie generiert.
∗
∗
Sie können aber jedes Wort der Sprache ableiten. Für alle w ∈ T ∗ gilt:
∗
∗
∗
∗
S ⇒ w gdw. S ⇒L w gdw. S ⇒R w gdw. S ⇒P w
L(G) = { w ∈ T ∗ | S ⇒ w } = { w ∈ T ∗ | S ⇒L w }
∗
∗
= { w ∈ T ∗ | S ⇒R w } = { w ∈ T ∗ | S ⇒P w }
∗
43
∗
44
Was Sie heute erwartet
Syntax aussagenlogischer Formeln
G = {Fm, Op, Var }, T , P, Fm , wobei
T = { , ⊥, ¬, (, ), ∧, ↑, ∨, ↓, ≡, ≡, ⊃, ⊂} ∪ V
P = { Fm → Var | | ⊥ | ¬Fm | ( Fm Op Fm ) ,
Op → ∧ | ↑ | ∨ | ↓ | ≡ | ≡ | ⊃ | ⊂ ,
Var → A | B | C | · · · }
4. Endliche Automaten
4.8. Beispiel: Flussüberquerung
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
Operationen auf formalen Sprachen
Definition regulärer Sprachen
Reguläre Ausdrücke
Eigenschaften regulärer Sprachen
Vom regulären Ausdruck zum Automaten
Vom Automaten zum regulären Ausdruck
((A ↑ B) ↑ (A ↑ B)) ist eine aussagenlogische Formel, weil:
Fm ⇒L
⇒L
⇒L
⇒L
⇒L
⇒L
⇒L
6. Kontextfreie Grammatiken
6.1. Definition
6.2. Beispiele
( Fm Op Fm )
⇒L
( ( Var Op Fm ) Op Fm )
⇒L
( ( A ↑ Fm ) Op Fm )
⇒L
( ( A ↑ B ) Op Fm )
⇒L
( ( A ↑ B ) ↑ ( Fm Op Fm ) ) ⇒L
( ( A ↑ B ) ↑ ( A Op Fm ) ) ⇒L
( ( A ↑ B ) ↑ ( A ↑ Var ) ) ⇒L
( ( Fm Op Fm ) Op Fm )
( ( A Op Fm ) Op Fm )
( ( A ↑ Var ) Op Fm )
( ( A ↑ B ) ↑ Fm )
( ( A ↑ B ) ↑ ( Var Op Fm ) )
( ( A ↑ B ) ↑ ( A ↑ Fm ) )
((A ↑ B) ↑ (A ↑ B))
46
45
Syntax aussagenlogischer Formeln
Reelle Numerale
G = {Fm, Op, Var }, T , P, Fm , wobei
G = V , T , P, Real , wobei
T = { , ⊥, ¬, (, ), ∧, ↑, ∨, ↓, ≡, ≡, ⊃, ⊂} ∪ V
P = { Fm → Var | | ⊥ | ¬Fm | ( Fm Op Fm ) ,
Op → ∧ | ↑ | ∨ | ↓ | ≡ | ≡ | ⊃ | ⊂ ,
Var → A | B | C | · · · }
und P folgende Produktionen sind:
V = {Real, Scale, Sign, Digits, Digit}
T = {0, . . . , 9, ., E, +, -}
Real → Digit Digits . Digits Scale
Scale → ε | E Sign Digit Digits
Sign → ε | + | Digits → ε | Digit Digits
Digit → 0 | · · · | 9
((A ↑ B) ↑ (A ↑ B)) ist eine aussagenlogische Formel, weil:
Fm ⇒P
⇒P
⇒P
⇒P
( Fm Op Fm )
( ( Fm Op Fm ) ↑ ( Fm Op Fm ) )
( ( Var ↑ Var ) ↑ ( Var ↑ Var ) )
((A↑B)↑(A↑B))
Optionalität:
A → ε | B (A steht für optionales B)
47
Wiederholung:
A → ε | B A (A steht für wiederholtes B, auch 0 Mal)
A → B | B A (A steht für wiederholtes B, mind. 1 Mal)
48
Wohlgeformte Klammerausdrücke
Induktive Definition vs. kontextfreie Grammatik
WKA ist die kleinste Menge, sodass
Induktive Definition für M
kontextfreie Grammatik für M
Mengen M, M0 , A1 , B1 , . . .
Var. M , M0 , A1 , B1 , . . .
M ist die kleinste Menge,
sodass:
M = L({. . . , P, M }), wobei
P folgende Produktionen sind:
ε ∈ WKA
(w ) ∈ WKA, wenn w ∈ WKA
w1 w2 ∈ WKA, wenn w1 , w2 ∈ WKA
G = {W },
{(, )},
{W → ε | ( W ) | W W },
Beispiel einer Ableitung: W ⇒P
⇒P
⇒P
⇒P
⇒P
W
M0 ⊆ M
M → M0
g(x1 , . . . , xn ) ∈ M,
falls x1 ∈ B1 , . . . , xn ∈ Bn
M → g( B1 , . . . , Bn )
f (x1 , . . . , xm ) ∈ M,
falls x1 ∈ A1 , . . . , xm ∈ Am
WW
(W )(W )
()(W W )
()((W )(W ))
()(()())
· · · ∈ M, falls . . .
L(G) = {ε, (), (()), ()(), ((())), (())(), ()(()), ()()(), . . . }
= WKA
49
h(x1 , x2 ) ∈ M, falls x1 , x2 ∈ M
h(x , x ) ∈ M, falls x ∈ M
M → f ( A1 , . . . , Am )
M → ...
M → h( M , M )
keine Entsprechung, nicht kontextfrei
50
Document
Kategorie
Seele and Geist
Seitenansichten
8
Dateigröße
450 KB
Tags
1/--Seiten
melden