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
25.10.2011
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.
Büchi-Automat:
Alle unendlichen Worte, mit denen man vom Anfangszustand aus
unendlich oft einen der Endzustände erreicht.
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
7
8
Operationen auf formalen Sprachen
Verkettung
Σ 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 ∈ Σ∗
{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}
Seien L, L ⊆ Σ∗ zwei Sprachen.
L ∪ L = { w | w ∈ L oder w ∈ L }
Vereinigung
{a, b} · {} = {} · {a, b} = {}
L · L = { w · w | w ∈ L, w ∈ L }
Verkettung
{ε} · {ε} = {ε}
{} · {} = {ε} · {} = {} · {ε} = {}
L0 = {ε}
= L · Ln
Ln+1
L+ =
L∗ =
n≥1
n≥0
(n ≥ 0)
Potenzen
Beobachtungen:
Sprachverkettung ist nicht kommutativ.
Sprachverkettung ist assoziativ.
Ln
Ln = L0 ∪ L+ = {ε} ∪ L+ Kleene-Stern
{ε} ist neutrales Element bzgl. Sprachverkettung.
∗
Das heißt, es gelten folgende Gleichungen.
= {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}
..
.
2Σ , ∪, {} . . . idemp.komm.Monoid
∗
(A ∪ B) ∪ C = A ∪ (B ∪ C )
{} ∪ A = A ∪ {} = A
A∪B =B∪A
A∪A=A
(A · B) · C = A · (B · C )
{ε} · A = A · {ε} = A
Verkettung distribuiert über Vereinigung.
Potenzen eines Alphabets Σ
{} ist Nullelement bzgl. Verkettung.
Σ1 = Σ
alle Σ-Wörter der Länge n (d.h., mit n Symbolen)
alle Σ-Wörter ohne Leerwort
alle Σ-Wörter mit Leerwort
A · (B ∪ C ) = (A · B) ∪ (A · C )
2Σ , ·, {ε} . . . Monoid
∗
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, . . . }
Σ0 = {ε}
Σn
Σ+ = n≥1 Σn
Σ∗ = n≥0 Σn
10
2Σ , ∪, ·, {}, {ε} bildet einen idempotenten Halbring
Potenzen von {a, 42}
L
L0
L1
L2
L3
{} ist Nullelement bzgl. Sprachverkettung.
9
(B ∪ C ) · A = (B · A) ∪ (C · A)
{} · A = A · {} = {}
Weitere Identitäten für + und ∗:
11
(A∗ )∗ = A∗
(A ∪ {ε})∗ = A∗
A∗ · A = A+
A+ ∪ {ε} = A∗
12
Was Sie heute erwartet
Reguläre Sprachen
Alle Sprachen, die aus einem Alphabet mit Hilfe von Vereinigung,
Verkettung und Stern gebildet werden können.
Anwendungen:
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
Betriebssytem-Shells: Dos („Wildcards“), Unix-Shells (wie sh, csh,
ash, bash, zsh), . . .
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
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.
6. Kontextfreie Grammatiken
Programmiersprachen: Perl, Tcl, Php, Python, Ruby, R, Java,
JavaScript, .Net-Sprachen, . . .
Websprachen: Xml Schema, XQuery, XPath, Dtds, . . .
Datenbanken: MySQL, Oracle, PostgreSQL, . . .
13
...
14
Was Sie heute erwartet
Regulären Sprachen über einem Alphabet
Die Menge der regulären Sprachen über Σ, Lreg (Σ), ist die kleinste
Menge, sodass gilt:
{}, {ε} und {s} sind reguläre Sprachen (für alle s ∈ Σ).
Wenn L und L reguläre Sprachen sind, dann auch L ∪ L , L · L und L∗ .
Reellen Numerale: reguläre Sprache über {0, . . . , 9, ., E, +, -}
real = digit · digit ∗ · {.} · digit ∗ · ({ε} ∪ scale)
scale = {E} · {+, -, ε} · digit · digit ∗
digit = {0, . . . , 9} = {0} ∪ · · · ∪ {9}
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
15
16
Reguläre Ausdrücke
Regulärer Ausdruck für die reellen Numerale
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.
R = DD ∗ .D ∗ (ε + S)
S = E(+ + - + ε)DD ∗
D = 0 + 1 + ··· + 9
(R, S und D sind Abkürzungen für die jeweiligen regulären Ausdrücke.)
Reguläre Ausdrücke (algebraische Notation)
Die regulären Ausdrücke über Σ sind die kleinste Menge, für die gilt:
∅, ε 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
Die zugehörigen Sprachen:
L(D) = L(0 + 1 + · · · + 9)
= L(0) ∪ L(1) ∪ · · · ∪ L(9)
= {0} ∪ {1} ∪ · · · ∪ {9}
= digits
r ∗.
Vereinfachte Klammerung: + bindet am schwächsten, ∗ am stärksten.
Keine Klammern bei gleichartigen Operatoren (wegen Assoziativität).
L(S) = L(E(+ + - + ε)DD ∗ )
= L(E) · L(+ + - + ε) · L(D) · L(D ∗ )
= {E} · (L(+) ∪ L(-) ∪ L(ε)) · digits · L(D)∗
= {E} · ({+} ∪ {-} ∪ {ε}) · digits · digits ∗
= scale
Die Sprache L(r ) zu einem regulären Ausdruck r ist definiert durch:
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 ))∗
17
L(R) = · · · = real
18
Reguläre Ausdrücke in Ebnf-Notation
Zwei reguläre Ausdrücke r und r heißen äquivalent, geschrieben r = r ,
wenn L(r ) = L(r ) gilt.
Ebnf . . . Erweiterte Backus-Naur-Form (Formalismus zur Beschreibung
der Syntax von Programmiersprachen, die reguläre Ausdrücke zulässt)
((a + b)∗ + ε)∗ = (a + b)∗
AB
A|B
[A]
{A}
(A)
"s"
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)∗ )
A·B
A∪B
{ε} ∪ A
A∗
(A)
{s}
Aufeinanderfolge
Alternativen
Option
Wiederholung
Gruppierung
Symbol
Reelle Numerale in Ebnf-Notation
real = digit { digit } "." { digit } [ scale ]
scale = "E" [ "+" | "-" ] digit { digit }
digit = "0" | "1" | "2" | · · · | "9"
19
20
Reguläre Ausdrücke als Syntaxdiagramme
Reelle Numerale als Syntaxdiagramm
Syntaxdiagramme . . . graphische Form der Ebnf
A
A
s
{s}
Symbol
X+
Wiederholung ≥ 1
X∗
Wiederholung ≥ 0
X
X
Aufeinanderfolge
X
Y
X ∪Y
Alternativen
X
{ε} ∪ X
Y
.
digit
real =
Abkürzung
X ·Y
X
digit
0
scale
2
+
scale =
3
digit
E
1
4
-
5
digit =
6
7
8
9
Option
21
Reguläre Ausdrücke im informatischen Alltag
22
Posix Extended Regular Expressions (Ere)
Unix := „30 definitions of regular expressions living under one roof“
(Donald E. Knuth)
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.
Verschiedene „Standards“:
Posix Basic Regular Expressions
Posix Extended Regular Expressions
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
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
Perl Regular Expressions
[0-9]
digit = {0, . . . , 9}
E[+-]?[0-9]+
scale = {E} · {+, -, ε} · digit · digit ∗
real = digit · digit ∗ · {.} · digit ∗ · ({ε} ∪ scale)
^[0-9]+\.[0-9]*(E[+-]?[0-9]+)?$
...
23
[0-9] . . . Kurzform von [0123456789]; analog [a-zA-Z] für Buchstaben24
Was Sie heute erwartet
Eigenschaften regulärer Sprachen
Reguläre Sprachen sind abgeschlossen gegenüber
Vereinigung, Verkettung und Stern (warum?)
Durchschnitt, Komplement, Differenz, Homomorphismen,
Quotientenbildung, . . .
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
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
Gegeben ein Programm mit einer Eingabe, wird es anhalten?
Folgende Probleme regulärer Sprachen sind entscheidbar:
6. Kontextfreie Grammatiken
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)
25
Ausdruckskraft regulärer Sprachen
Gegeben einen regulären Ausdruck r , ist L(r ) leer/endlich/unendlich?26
Was Sie heute erwartet
Die regulären Sprachen sind genau jene, die von endlichen Automaten
akeptiert werden, d.h.:
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.
Nicht regulär sind Sprachen, deren Analyse ein unbegrenztes Gedächtnis
erfordert:
Klammerausdrücke: {(), (()), ()(), ((())), (())(), ()()(), . . . }
{ an bn | n ≥ 0 } = {ε, ab, aabb, aaabbb, . . . }
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
{ 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)
27
28
Vom regulären Ausdruck zum Automaten
Automat für ∅:
i
Regulärer Ausdruck: 1(0 + 1)∗
Automat für r1 + r2 :
Automat für r1
f
Automat für r1 r2 :
ε
i1
ε
Automat für s ∈ Σ ∪ {ε}:
s
i
f
i
Automat für Binärnumerale ohne führende Null
i
i2
ε
Automat für r1∗ :
f1
ε
1
f
Automat für r2
Automat für r1
i1
ε
f1
f2
ε
ε
0
ε
ε
1
ε
Automat für r2
ε
i2
f2
ε
ε
ε
0,1
f
Minimaler deterministischer Automat:
1
Manuelle Konstruktion von Automaten:
ε
i1
ε
ε
1
Automat für r1
i
ε
f1
ε
f
ε
2
29
Was Sie heute erwartet
Konstruiere die Automaten zu einfachen Teilsprachen „durch
Hinschauen“.
Verwende die allgemeine Konstruktion mit ε-Übergängen für
undurchsichtige Situationen.
30
Vom Automaten zum regulären Ausdruck
R . . . Menge der regulären Ausdrücke über Σ
Verallgemeinerter endlicher Automat
. . . wird beschrieben durch ein 5-Tupel A = Q, Σ, δ, i, f , wobei
5. Reguläre Sprachen
5.1.
5.2.
5.3.
5.4.
5.5.
5.6.
Q . . . endliche Zustandsmenge
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
Σ . . . Eingabealphabet
δ : (Q − {f }) × (Q − {i}) → R . . . Übergangsfunktion
i ∈ Q . . . Anfangszustand
f ∈ Q, f = i . . . Endzustand
6. Kontextfreie Grammatiken
31
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.
32
Vom verallgemeinerten Automaten zum regulären Ausdruck
Umwandlung eines endlichen Automaten in einen verallgemeinerten
Übergänge in den Anfangszustand oder Anfangszustand ist
Endzustand:
=⇒
Gegeben: Verallgemeinerter Automat A = Q, Σ, δ, i, f
Für jeden Zustand q ∈ Q − {i, f } führe folgende Schritte durch:
ε
1
Mehrere Endzustände:
=⇒
ε
ε
Füge zwischen allen Nachbarn p, p von q neue Übergänge hinzu:
y
y
p
x
z
q
p
=⇒
p
x
ε
Übergänge weg vom Endzustand:
=⇒
Mehrere Übergänge zwischen zwei Zuständen:
s1
s1 + s2
=⇒
s2
p
xy ∗ z
(x , y und z bezeichnen reguläre Ausdrücke.)
ε
z
q
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).
33
34
Anmerkungen:
Falls p und p derselbe Knoten sind, erhält man:
y
xy ∗ z
y
x
x
p
q
p
q
=⇒
A
a
1
0,1
0
0
z
z
Falls die Schleife mit dem Ausdruck y nicht existiert, entfällt y ∗ .
b
1
c
1
Falls der Übergang p–p bereits existiert, wird xy ∗ z addiert.
0+1
i
ε
a
0
b
1
c
ε
f
ε
35
36
A
a
1
0,1
0
0
A
b
1
c
a
1
1
0,1
0
0
b
1
c
1
1
0
i
ε
a
0
00
b
00 + (1 + 01)(0 + 1)
0+1
0+1
1 + 01
0
c
ε
i
f
ε
b
1 + 01
c
ε
f
ε + 1 + 01
0 + 1(0 + 1)
1
36
A
a
36
1
0,1
0
0
A
b
1
c
a
1
0,1
0
0
b
1
c
00 + (1 + 01)(0 + 1)
i
b
0 + 1(0 + 1)
i
f
f
ε + 1 + 01
1 + (0 + 1(0 + 1))(00 + (1 + 01)(0 + 1))∗ (ε + 1 + 01)
1 + (0 + 1(0 + 1))(00 + (1 + 01)(0 + 1))∗ (ε + 1 + 01)
r = 1 + (0 + 10 + 11)(00 + 10 + 11 + 010 + 011)∗ (ε + 1 + 01)
36
Es gilt: L(r ) = L(A).
36
Was Sie heute erwartet
Kontextfreie Grammatiken
Menge von Ersetzungsregeln
2 Arten von Symbolen: Terminale, Nonterminale
Ausgehend vom Start-Nonterminal werden Nonterminale solange
ersetzt, bis nur noch Terminale bleiben.
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
Satz → HwP ZwP
HwP → Art Hw
ZwP → Hzw HwP Zw
6. Kontextfreie Grammatiken
Satz ⇒p
⇒p
⇒p
⇒p
Art
Hw
Hzw
Zw
→ der | den
→ Hund | Mond
→ wird
→ anbellen
HwP ZwP
Art Hw Hzw HwP Zw
der Hund wird Art Hw anbellen
der Hund wird den Mond anbellen
37
Von Grammatik G generierte Sprache
Kontextfreie Grammatik
. . . wird beschrieben durch ein 4-Tupel G = V , T , P, S , wobei
L(G) = { w ∈ T ∗ | S ⇒ w }
∗
V . . . Menge der Nonterminalsymbole (Variablen)
Grammatiken G1 und G2 heißen äquivalent, wenn L(G1 ) = L(G2 ) gilt.
T . . . Menge der Terminalsymbole (V ∩ T = {})
G = {S}, {a, b}, {S → ε | a S b}, S
P ⊆ V × (V ∪ T )∗ . . . Produktionen
S ∈ V . . . Startsymbol
S ⇒ aabb, weil
∗
Schreibweise: A → w
statt (A, w ) ∈ P
A → w1 | · · · | wn statt A → w1 , . . . , A → wn
Linksableitbarkeit: xAy ⇒L xwy falls A → w ∈ P und x ∈ T ∗
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 .
Rechtsableitbarkeit: xAy ⇒R xwy falls A → w ∈ P und y ∈ T ∗
Parallelableitbarkeit: x0 A1 x1 · · · An xn ⇒P x0 w1 x1 · · · wn xn
falls A1 → w1 , . . . , An → wn ∈ P und x0 , . . . , xn ∈ T ∗
v ist in mehreren Schritten aus u ableitbar, geschrieben u ⇒ v , falls
∗
u = v , oder
∗
S ⇒ a S b ⇒ aa S bb ⇒ aa ε bb ⇒ aabb
L(G) = { an bn | n ≥ 0 } = {ε, ab aabb aaabbb, . . . }
Ableitbarkeit
u ⇒ u und u ⇒ v für ein Wort u ∈ (V ∪ T )∗ .
38
L(G) = { w ∈ T ∗ | S ⇒ w } = { w ∈ T ∗ | S ⇒L w }
∗
∗
= { w ∈ T ∗ | S ⇒R w } = { w ∈ T ∗ | S ⇒P w }
∗
39
∗
40
Syntax aussagenlogischer Formeln
Syntax aussagenlogischer Formeln
G = {Fm, Op, Var }, T , P, Fm , wobei
G = {Fm, Op, Var }, T , P, Fm , wobei
T = { , ⊥, ¬, (, ), ∧, ↑, ∨, ↓, ≡, ≡, ⊃, ⊂} ∪ V
P = { Fm → Var | | ⊥ | ¬Fm | ( Fm Op Fm ) ,
Op → ∧ | ↑ | ∨ | ↓ | ≡ | ≡ | ⊃ | ⊂ ,
Var → A | B | C | · · · }
T = { , ⊥, ¬, (, ), ∧, ↑, ∨, ↓, ≡, ≡, ⊃, ⊂} ∪ V
P = { Fm → Var | | ⊥ | ¬Fm | ( Fm Op Fm ) ,
Op → ∧ | ↑ | ∨ | ↓ | ≡ | ≡ | ⊃ | ⊂ ,
Var → A | B | C | · · · }
((A ↑ B) ↑ (A ↑ B)) ist eine aussagenlogische Formel, weil:
((A ↑ B) ↑ (A ↑ B)) ist eine aussagenlogische Formel, weil:
Fm ⇒L
⇒L
⇒L
⇒L
⇒L
⇒L
⇒L
( 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))
Fm ⇒P
⇒P
⇒P
⇒P
41
( Fm Op Fm )
( ( Fm Op Fm ) ↑ ( Fm Op Fm ) )
( ( Var ↑ Var ) ↑ ( Var ↑ Var ) )
((A↑B)↑(A↑B))
42
Document
Kategorie
Gesundheitswesen
Seitenansichten
7
Dateigröße
427 KB
Tags
1/--Seiten
melden