close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Formelsammlung Version 13

EinbettenHerunterladen
F ORMALE S YSTEME
— Wintersemester 2014/15 —
Formelsammlung
Version 17
Kirstin Peters
18. Dezember 2014
In diesem Dokument sammeln wir Definitionen und Sätze, die in der Veranstaltung verwendet werden. Es ist als Nachschlagewerk während der Vorlesungszeit gedacht (z.b. als Hilfe zum Lösen der
Aufgaben). Wir übernehmen keine Garantien; weder für die Vollständigkeit noch für die Richtigkeit der enthaltenen Daten. Sollten Sie einen Fehler entdecken oder etwas vermissen, melden Sie
sich bitte unter kirstin_barbara.peters@tu-dresden.de. Vielen Dank!
Viele der folgenden Definitionen, Zitate und Sätze sind [HUM02], [Sch08], [Hof11] oder dem
Skript zur Veranstaltung Formale Systeme aus dem Wintersemester 2011/12 von Prof. Dr. Baier
entnommen. Diesen Quellen können auch weiterführende Erklärungen und zusätzliche Aufgaben
entnommen werden.
i
INHALTSVERZEICHNIS
Formale Systeme
Inhaltsverzeichnis
1
2
3
Mathematische Grundlagen
1.1 Mengen . . . . . . . . . . . .
1.2 Relationen . . . . . . . . . . .
1.3 Ordnungen und Äquivalenzen
1.4 Abbildungen und Kardinalität
.
.
.
.
1
1
3
5
7
.
.
.
.
.
.
10
10
12
19
25
26
26
Aussagenlogik
3.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
27
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Formale Sprachen
2.1 Wörter und Sprachen . . . . . . . . . . . . . . .
2.2 Reguläre Sprachen (Typ 3) . . . . . . . . . . . .
2.3 Kontextfreie Sprachen (Typ 2) . . . . . . . . . .
2.3.1 Deterministisch Kontextfreie Sprachen .
2.4 Kontextsensitive Sprachen (Typ 1) . . . . . . . .
2.5 Akzeptierbare oder Allgemeine Sprachen (Typ 0)
Literatur
Version 17, 18. Dezember 2014
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
29
ii
Formale Systeme
1
Mathematische Grundlagen
Wir beginnen mit der Einführung einiger mathematischer Grundlagen, welche in den späteren Abschnitten verwendet werden.
1.1
Mengen
„Unter einer Menge verstehen wir jede Zusammensetzung M von
bestimmten wohl unterschiedenen Objekten unserer Anschauung
oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen.“
(Georg Cantor, 1895)
Georg Cantor
(1845 – 1918)
Üblicherweise bezeichnen wir Mengen mit A, B, C, A1 , Ai , A , . . . und die Elemente von Mengen mit a, b, c, a1 , ai , a , . . ..
Notation 1.1.1 (Aufzählende Schreibweise). Eine Menge A kann durch
A = { a1 , a2 , a3 , . . . }
def
als die explizite Aufzählung unterscheidbarer Elemente ai definiert werden.
Die Aussage „a ∈ A“ bezeichnet den Sachverhalt, dass a ein Element der Menge A ist.
Die leere Menge enthält keine Elemente. Sie wird mit ∅ oder {} bezeichnet.
Definition 1.1.2 (Zahlenmengen). Mit N = { 0, 1, 2, 3, . . . } (bzw. N+ = { 1, 2, 3, . . . }) bezeichnen wir
die Menge der natürlichen Zahlen (bzw. positiven natürlichen Zahlen). Entsprechend bezeichnen
Z, Q und R die gebräuchlichen Mengen von ganzen Zahlen, rationalen Zahlen und reellen Zahlen.
def
def
Definition 1.1.3 (Größe von Mengen). Sei A eine beliebige Menge.
#(A) bezeichnet die Anzahl der Elemente in A.
Es gilt #(A) ∈ N oder #(A) = ∞.
Notation 1.1.4 (Deskriptive Beschreibung). Eine Menge A kann mit
A = { x ∈ B | P(x) }
def
bzw.
A = { x | P(x) }
def
durch die Angabe eines definierenden Prädikats P zur Variablen x (in Bezug auf eine andere Menge
B) definiert werden. Sowohl { x ∈ B | P(x) } als auch { x | P(x) } definieren nur dann Mengen, wenn
für alle betroffenen x die Wahrheit von P(x) überprüfbar ist.
Version 17, 18. Dezember 2014
1
1.1
Mengen
Formale Systeme
Bemerkung 1.1.5 (Russell’sches Paradox). { x | x ∈
/ x } ist keine Menge.
Wir führen logische Konnektive zunächst als symbolische Abkürzungen natürlichsprachlicher
Begriffe ein. Im Abschnitt 3 beschäftigen wir uns näher mit der Aussagenlogik.
Notation 1.1.6 (Junktor-Symbole).
• Verum steht für „wahr“
• Falsum ⊥ steht für „falsch“
• Negation ¬ steht für „nicht“
• Konjunktion ∧ steht für „und“
• Disjunktion ∨ steht für „oder“
• Implikation → steht für „impliziert“ (d.h. lässt schließen auf)
• Äquivalenz ↔ steht für „genau dann, wenn“ („g.d.w.“)
• Universelle Quantifikation ∀ steht für „für alle“
• Existentielle Quantifikation ∃ steht für „es gibt“
Definition 1.1.7 (Teilmengen, Gleichheit von Mengen).
Seien A und B zwei beliebige Mengen.
A heißt Teilmenge von B, geschrieben A ⊆ B, wenn für alle x gilt:
(x ∈ A) → (x ∈ B)
A und B heißen gleich, geschrieben A = B, wenn gilt:
A ⊆ B∧B ⊆ A
A heißt echte Teilmenge von B, geschrieben A ⊂ B, wenn gilt:
A ⊆ B∧A = B
Wenn A (echte) Teilmenge von B ist, dann heißt B (echte) Obermenge von A.
Satz 1.1.8. Für alle Mengen A gilt: ∅ ⊆ A.
Satz 1.1.9. Die leere Menge ist eindeutig.
Definition 1.1.10 (Vereinigung, Durchschnitt, Komplement, Produkt).
Seien A und B zwei beliebige Mengen. Wir definieren,
die Vereinigung von A und B, lies A vereinigt mit B, als
A∪B = {x | x ∈ A∨x ∈ B}
def
Version 17, 18. Dezember 2014
2
1.2
Relationen
Formale Systeme
den Schnitt von A und B, lies A geschnitten B, als
A∩B = {x | x ∈ A∧x ∈ B}
def
das Komplement von A in Bezug auf B, lies B ohne A, als
B\A = {x | x ∈ B∧x ∈
/ A}
def
und das kartesiche Produkt von A und B als
A × B = { (a, b) | a ∈ A ∧ b ∈ B }
def
Definition 1.1.11 (Potenzmenge). Sei A eine beliebige Menge. Dann heißt
2A = { B | B ⊆ A }
def
Potenzmenge von A.
Satz 1.1.12. Sei A eine beliebige Menge. Dann gilt:
# 2A =
1.2
, falls #(A) = ∞
, falls #(A) = ∞
2#(A)
∞
Relationen
Definition 1.2.1 (Kartesisches Produkt).
Sei n ∈ N+ . Seien A1 , . . . , An Mengen. Dann heißt
Πi∈{ 1,...,n } Ai = { (a1 , . . . , an ) | ∀i ∈ { 1, . . . , n } . ai ∈ Ai }
def
das kartesische Produkt der Ai . Die Elemente eines kartesischen Produkts heißen Tupel.
Das leere Tupel wird mit () bezeichnet.
Bemerkung 1.2.2. Seien A1 , A2 Mengen.
Dann heißt A1 × A2 = Πi∈{ 1,2 } Ai binäres kartesisches Produkt.
Definition 1.2.3 (Spezialfälle).
Sei A eine beliebige Menge.
def
• An = Πi∈{ 1,...,n } A für n ∈ N+ .
def
• A0 = { () }
Version 17, 18. Dezember 2014
3
1.2
Relationen
Formale Systeme
Definition 1.2.4 (Relation). Seien A1 , . . . , An nicht-leere Mengen.
Eine Teilmenge R ⊆ Πi∈{ 1,...,n } Ai heißt n-stellige Relation.
Die Schreibweise „Relation R mit Typ Πi∈{ 1,...,n } Ai “
R : Πi∈{ 1,...,n } Ai
erlaubt es, Relationen aufgrund ihres Typs zu klassifizieren.
R heißt homogen, falls Ai = Aj für alle 1 i n und 1 j n.
Zwei Relationen RA : Πi∈{ 1,...,n } Ai und RB : Πi∈{ 1,...,m } Bi sind gleich, falls (1.) n = m, (2.) für
alle 1 i n ist Ai = Bi und (3.) RA = RB .
Notation 1.2.5 (Binäre Relationen).
Der Spezialfall der zweistelligen Relation R : A × B heißt auch binäre Relation. Hier benutzen wir
oft die Infixschreibweise aRb anstelle von (a, b) ∈ R.
Definition 1.2.6 (Spezielle Relationen). Seien A und B beliebige Mengen.
def
• ∇A,B : A × B mit ∇A,B = A × B
bezeichnet die universelle Relation bzw. Allrelation (mit Typ A × B).
def
• ∅A,B : A × B mit ∅A,B = ∅
bezeichnet die leere Relation (mit Typ A × B).
def
def
• ∆A : A × A mit ∆A = IdA = { (a, a) | a ∈ A }
bezeichnet die Diagonalrelation bzw. Identität (mit Typ A × A).
Wenn der Typ implizit klar ist, kann der Index weggelassen werden.
Definition 1.2.7 (Eigenschaften binärer Relationen).
Sei R : A × B eine beliebige binäre Relation. Dann heißt R:
linkstotal,
falls
∀a ∈ A . ∃b ∈ B . aRb
rechtstotal,
falls
∀b ∈ B . ∃a ∈ A . aRb
linkseindeutig,
falls ∀a1 , a2 ∈ A . ∀b ∈ B . (a1 Rb ∧ a2 Rb) → a1 = a2
rechtseindeutig, falls ∀a ∈ A . ∀b1 , b2 ∈ B . (aRb1 ∧ aRb2 ) → b1 = b2
Definition 1.2.8 (Komposition). Seien A, B, C drei beliebige Mengen. Seien P : A×B und Q : B×C
zwei beliebige Relationen. Dann ist die Komposition P;Q : A × C definiert als:
P;Q = { (a, c) ∈ A × C | ∃b ∈ B . aPb ∧ bQc }
def
Aus Gründen der Konsistenz mit dem Kompositionsbegriff für Funktionen verwenden wir auch die
def
Notation: Q ◦ P = P;Q.
Satz 1.2.9 (Assoziativität der Komposition). Seien A, B, C, D beliebige Mengen. Seinen P : A × B,
Q : B × C und R : C × D drei beliebige Relationen. Dann gilt:
P;(Q;R) = (P;Q);R
Version 17, 18. Dezember 2014
4
1.3
Ordnungen und Äquivalenzen
Formale Systeme
Definition 1.2.10 (Umkehrrelation). Seien A und B zwei beliebige Mengen. Sei R : A × B. Die
Umkehrrelation von R, geschrieben R−1 : B × A, ist definiert durch:
R−1 = { (b, a) | (a, b) ∈ R }
def
Proposition 1.2.11 (Eigenschaften der Umkehrrelation). Seien A, B, C drei beliebige Mengen. Seien R : A × B und Q : B × C zwei beliebige Relationen. Dann gilt:
−1
=R
1. R−1
−1
2. (R;Q) = Q−1 ;R−1
3. (Q ◦ R)−1 = R−1 ◦ Q−1
Definition 1.2.12 (Eigenschaften homogener Relationen).
Sei R : A × A eine beliebige binäre homogene Relation. Dann heißt R:
reflexiv,
falls
∀a ∈ A . aRa
bzw.
∆A ⊆ R
irreflexiv,
falls
∀a ∈ A . ¬(aRa)
bzw.
∆A ∩ R = ∅
symmetrisch,
falls
∀a, b ∈ A . aRb → bRa
bzw.
R−1 = R
antisymmetrisch, falls ∀a, b ∈ A . (aRb ∧ bRa) → a = b bzw. R−1 ∩ R ⊆ ∆A
transitiv,
falls ∀a, b, c ∈ A . (aRb ∧ bRc) → aRc bzw.
R◦R ⊆ R
linear,
falls
∀a, b ∈ A . aRb ∨ bRa
bzw. R−1 ∪ R = ∇A,A
1.3
Ordnungen und Äquivalenzen
Definition 1.3.1 (Ordnungen). Sei R : A × A eine beliebige homogene Relation.
Die Tabelle benennt die Mindestkriterien, so dass für R der jeweilge Ordnungsbegriff gilt.
Ordnungsbegriff
reflexiv transitiv antisymmetrisch linear
Quasiordnung
•
•
partielle Ordnung
•
•
•
totale Ordnung
•
•
•
•
Notation 1.3.2 (Ordnungsbegriffe).
• Quasiordnungen heißen auch Präordnungen.
• Partielle Ordnungen heißen auch Halbordnungen.
• Totale Ordnungen heißen auch lineare Ordnungen.
• Irreflexive Ordnungen heißen auch streng oder strikt.
Definition 1.3.3 (Äquivalenzrelation). Sei R : A × A eine beliebige homogene Relation.
Dann heißt R Äquivalenzrelation bzw. Äquivalenz, wenn R sowohl (1.) reflexiv, (2.) symmetrisch,
als auch (3.) transitiv ist.
Version 17, 18. Dezember 2014
5
1.3
Ordnungen und Äquivalenzen
Formale Systeme
Definition 1.3.4 (Äquivalenzklassen). Sei R : A × A eine Äquivalenz. Sei a ∈ A.
[a]R = { x ∈ A | (a, x) ∈ R }
def
heißt Äquivalenzklasse von a bzgl. R.
Notation 1.3.5. Wir schreiben [a] für [a]R , wenn R aus dem Kontext eindeutig hervorgeht.
Proposition 1.3.6. Sei R : A × A eine Äquivalenz. Sei a ∈ A. Dann gilt:
1. a ∈ [a]
2. (a1 , a2 ) ∈ R ↔ [a1 ] = [a2 ]
3. (a1 , a2 ) ∈
/ R ↔ [a1 ] ∩ [a2 ] = ∅
Definition 1.3.7 (Quotient). Sei R : A × A eine Äquivalenz.
Dann heißt die Menge aller Äquivalenzklassen, gegeben durch
A/R
Quotient von A bzgl. R. Die Zahl #(A/R) der Äquivalenzklassen von R heißt Index von R.
Satz 1.3.8. Sei A eine beliebige Menge. Dann sind eindeutig bestimmt:
• ∇A,A als ⊆-größte Äquivalenz in A × A und
• ∆A als ⊆-kleinste Äquivalenz in A × A.
Definition 1.3.9. Sei M eine Menge von Mengen. Dann gilt:
M = { x | ∃M ∈ M . x ∈ M }
def
M = { x | ∀M ∈ M . x ∈ M }
def
Als Spezialfälle werden häufig indizierte Vereinigungen verwendet.
Mi = { x | ∃i ∈ I . x ∈ Mi }
def
i∈I
Mi = { x | ∀i ∈ I . x ∈ Mi }
def
i∈I
Definition 1.3.10. Sei R : A × A eine beliebige homogene Relation. Dann heißt Rn für n ∈ N die
n-fache Komposition von R, definiert durch:
R0 = ∆A
def
Rn+1 = R;Rn
def
Version 17, 18. Dezember 2014
6
1.4
Abbildungen und Kardinalität
Formale Systeme
Bemerkung 1.3.11. Die n-fache Komposition einer homogenen Relation kann gleichwertig linksbzw. rechts-induktiv definiert werden, d.h. die zweite Zeile in der Definition 1.3.10 kann gleichdef
wertig durch Rn+1 = Rn ;R ersetzt werden.
Definition 1.3.12 (Abschluss). Sei R : A × A eine beliebige homogene Relation.
• Der reflexive Abschluss von R ist definiert durch:
def
r(R) = R ∪ ∆A
• Der symmetrische Abschluss von R ist definiert durch:
s(R) = R ∪ R−1
def
• Der transitive Abschluss von R ist definiert durch:
Rn
def
t(R) =
n∈N+
Der Typ der Abschlussrelationen entspricht dem Typ der Basisrelation, d.h. der Typ von r(R), s(R)
und t(R) ist gleich dem Typ von R.
Proposition 1.3.13 (Erzeugte Äquivalenz). Sei R : A × A eine beliebige homogene Relation. Unter
allen Relationen, die Obermenge von R sind, ist:
• r(R) die ⊆-kleinste reflexive Relation,
• s(R) die ⊆-kleinste symmetrische Relation,
• t(R) die ⊆-kleinste transitive Relation und
• t(s(r(R))) die ⊆-kleinste Äquivalenz.
1.4
Abbildungen und Kardinalität
Definition 1.4.1 (Partielle Abbildung). Sei f : A × B eine rechtseindeutige Relation. Dann heißt f
partielle Abbildung f vom Typ A B, geschrieben f : A B.
1. Wir schreiben f(a) = b, falls (a, b) ∈ f.
2. f(a) ist der Funktionswert von f an der Stelle a.
3. A heißt Argumentbereich bzw. Domain von f, geschrieben dom(f).
B heißt Zielbereich bzw. Codomain von f, geschrieben cod(f).
4. Seien A0 ⊆ A und B0 ⊆ B. Dann heißen die Mengen
f(A0 ) = { b ∈ B | ∃a ∈ A0 . f(a) = b }
def
f−1 (B0 ) = { a ∈ A | ∃b ∈ B0 . f(a) = b }
def
Bild von A0 bzgl. f, sowie Urbild von B0 bzgl. f.
Version 17, 18. Dezember 2014
7
1.4
Abbildungen und Kardinalität
Formale Systeme
5. Die Mengen
def
Bild(f) = f(A)
Def(f) = f−1 (B)
def
heißen Bildbereich Bild(f) ⊆ B und Definitionsbereich Def(f) ⊆ A.
6. f heißt (totale) Abbildung bzw. Funktion, geschrieben f : A → B, falls f linkstotal ist.
Notation 1.4.2. Anstelle von (a, b) ∈ f verwendet man im Kontext von Abbildungen häufig auch
die Schreibweise a → b.
Satz 1.4.3 (Komposition von Abbildungen).
1. Seien f : A
B und g : B
C partielle Abbildungen. Dann ist auch (g ◦ f) : A
C eine
partielle Abbildung mit (g ◦ f)(x) = g(f(x)) für alle x ∈ A.
2. Seien f : A → B und g : B → C Abbildungen. Dann ist auch (g ◦ f) : A → C eine Abbildung
mit (g ◦ f)(x) = g(f(x)) für alle x ∈ A.
Definition 1.4.4 (Eigenschaften partieller Abbildungen).
LT LE RE RT
Begriff
partielle Abbildung
•
Abbildung
•
•
injektive partielle Abbildung
•
•
surjektive partielle Abbildung
•
•
•
•
•
bijektive partielle Abbildung
Bijektion
•
•
•
•
Satz 1.4.5 (Umkehrabbildung).
Sei f : A B eine partielle Abbildung bzw. g : A → B eine Abbildung.
1. Ist f bzw. g nicht injektiv, dann ist die Umkehrrelation f−1 : B × A bzw. g−1 : B × A keine
(partielle) Abbildung.
2. Ist f bzw. g injektiv, dann ist auch f−1 : B × A eine injektive partielle Abbildung bzw. dann
ist g−1 : B × A eine partielle, injektive und surjektive Abbildung.
3. Ist f bzw. g bijektiv, dann ist f−1 : B × A eine totale injektive Abbildung bzw. dann ist auch
g−1 : B × A eine Bijektion mit g(x) = y ↔ g−1 (y) = x.
Satz 1.4.6 (Bijektion). Eine Relation f : A × B ist genau dann eine Bijektion, wenn es eine Relation
g : B × A mit f ◦ g = ∆B und g ◦ f = ∆A gibt. In diesem Fall ist g = f−1 .
Definition 1.4.7 (Größe von Mengen II). Eine Menge A heißt endlich, falls es eine Bijektion vom
def
Typ A → { 1, . . . , n } für n ∈ N gibt; dann bezeichnet #(A) = n die entsprechende Anzahl der Elemente in A. Falls ein solches n nicht existiert, heißt A unendlich und wir notieren #(A) = ∞.
Es gilt: ∀n ∈ N . (∞ + n = ∞) ∧ (∞ − n = ∞) ∧ (∞ · n = ∞) ∧ (n < ∞).
Version 17, 18. Dezember 2014
8
1.4
Abbildungen und Kardinalität
Formale Systeme
Definition 1.4.8 (Kardinalität). Seien A und B zwei Mengen.
1. A und B haben die gleiche Kardinalität, card(A) = card(B), falls es eine Bijektion vom Type
A → B gibt. A und B heißen dann auch äquipotent oder isomorph.
2. A hat höchstens die Kardinalität von B, card(A) card(B), falls es eine injektive Abbildung
vom Typ A → B gibt.
3. A hat eine echt kleinere Kardinalität als B, card(A) < card(B), falls card(A) card(B) und
card(A) = card(B).
Definition 1.4.9 (Abzählbarkeit). Sei A eine Menge.
1. A heißt abzählbar, falls A endlich oder äquipotent zu N ist.
2. A heißt abzählbar unendlich, falls A äquipotent zu N ist.
3. A heißt überabzählbar, falls card(N) < card(A).
Proposition 1.4.10 (Größe von Zahlenmengen).
Es gilt #(N) = #(Z) = #(Q) = #(R) = ∞; aber card(N) = card(Z) = card(Q) < card(R).
Satz 1.4.11 (Cantor). Sei A eine Menge. Dann ist
card(A) < card 2A .
Version 17, 18. Dezember 2014
9
Formale Systeme
2
Formale Sprachen
2.1
Wörter und Sprachen
Intuitiv ist ein Wort eine endliche Folge von Symbolen und eine Sprache eine Menge von Wörtern.
Die Menge aller Symbole, die in irgendeinem Wort einer Sprache vorkommen, nennt man üblicherweise Alphabet. Der Einfachheit halber beschränken wir uns auf nicht-leere endliche Alphabete.
Alphabete werden oft mit Σ, Γ oder A bezeichnet.
Definition 2.1.1 (Alphabet). Ein Alphabet Σ ist eine endliche, nicht-leere Menge von Symbolen.
Die Elemente si ∈ Σ werden auch Symbol, Zeichen oder Buchstabe genannt.
Definition 2.1.2 (Wort). Sei Σ ein Alphabet. Ein Wort w über Σ ist eine endliche Folge (a1 , . . . , an ),
wobei n ∈ N und ai ∈ Σ für alle 1 i n.
• Für n = 0 ergibt sich das leere Wort ε = ().
• Mit |w| wird die Länge des Wortes w bezeichnet. Für w = (a1 , . . . , an ) ist |w| = n.
• (w)i bezeichnet die Projektion des Wortes w auf das i-te Symbol. Die Projektion ist lediglich
für 1 i |w| definiert.
• Wir bezeichnen mit |w|a die Anzahl aller Vorkommen von a ∈ Σ in w ∈ Σ∗ ,
d.h. |w|a = #({ i ∈ N | 1 i |w| ∧ (w)i = a }).
Häufig vereinfachen wir (a1 , . . . , an ) zu a1 · · · an .
Definition 2.1.3 (Kleeneabschluss). Σ∗ bezeichnet die Menge aller Wörter über Σ und Σ+ = Σ∗ \
{ ε } die Menge aller nicht-leeren Wörter über Σ.
Definition 2.1.4 (Operationen auf Wörtern).
Seien v = (a1 , . . . , am ) und w = (b1 , . . . , bn ) zwei Wörter aus Σ∗ .
1. Die Konkatenation von v und w ist definiert durch:
def
v · w = (a1 , . . . , am , b1 , . . . , bn )
2. v heißt Präfix von w, falls es ein u ∈ Σ∗ gibt, so dass v · u = w.
3. v heißt Suffix von w, falls es ein u ∈ Σ∗ gibt, so dass u · v = w.
4. v heißt Teilwort von w, falls es u1 , u2 ∈ Σ∗ gibt, so dass u1 · v · u2 = w.
Notation 2.1.5. Seien u, v ∈ Σ∗ und a ∈ Σ. Anstelle von (a) · v schreiben wir oft av. Anstelle von
v · (a) schreiben wir oft va. Anstelle von u · v schreiben wir oft uv.
Lemma 2.1.6 (Dekomposition).
Sei w ein Wort über dem Alphabet Σ. Dann gilt genau einer der beiden folgenden Fälle:
1. w = ε (also |w| = 0), oder
Version 17, 18. Dezember 2014
10
2.1
Wörter und Sprachen
Formale Systeme
2. es gibt ein a ∈ Σ und ein v ∈ Σ∗ und mit |v| = |w| − 1, so dass w = av.
Definition 2.1.7 (Sprache).
Sei Σ ein Alphabet. Dann heißt jede Teilmenge L ⊆ Σ∗ Sprache über Σ.
Satz 2.1.8 (Abzählbarkeit). Sei Σ ein Alphabet. Σ∗ und alle Sprachen L über Σ∗ sind abzählbar.
def
Notation 2.1.9 (Komplement). Sei L eine Sprache über dem Alphabet Σ. Dann bezeichnet L = Σ\L
das Komplement von L bezüglich Σ.
Definition 2.1.10 (Konkatenation von Sprachen). Seien LA und LB Sprachen über dem Alphabet
Σ. Die Konkatenation LA · LB (oder kurz: LA LB ) ist definiert durch:
LA · LB = { w ∈ Σ∗ | ∃w1 ∈ LA . ∃w2 ∈ LB . w = w1 · w2 }
def
Sei L eine Sprache. Die n-fache Konkatenation ist definiert durch:
L0 = { ε }
def
Ln+1 = L · Ln
L∗ =
def
L+ =
def
def
n
n 0L
n
n 1L
Definition 2.1.11 (Grammatik). Eine Grammatik ist ein 4-Tupel G = (V, Σ, P, S), wobei
• V ein nicht-leeres Alphabet von Nichtterminalsymbolen ist,
• Σ ein nicht-leeres Alphabet von Terminalsymbolen ist, so dass V ∩ Σ = ∅,
• P ⊆ (V ∪ Σ)+ × (V ∪ Σ)∗ eine endliche Menge von Produktionen ist und
• S ∈ V als Startsymbol bezeichnet wird.
Wir benutzen α, β, . . . für Elemente von (V ∪ Σ)∗ .
Produktionen (α, β) ∈ P schreiben wir auch als α →G β (oder kurz α → β).
Mehrere Regeln α →G β1 , . . . , α →G βn kürzen wir oft mit α →G β1 | . . . | βn ab.
def
Üblicherweise nutzen wir Kleinbuchstaben für die Terminalsymbole und Großbuchstaben für
die Nichtterminalsymbole.
Definition 2.1.12 (Ableitung, Sprache). Sei G = (V, Σ, P, S) eine Grammatik.
1. Die direkte Ableitung in G zwischen α, β ∈ (V ∪ Σ)∗ ist definiert durch:
(α ⇒G β)
↔
∃α , β , γ, γ ∈ (V ∪ Σ)∗ . α →G β ∧ α = γα γ ∧ β = γβ γ
β heißt dann direkt ableitbar aus α in G. Wir schreiben auch kurz α ⇒ β.
def
2. Die Relation ⇒∗G = t(r(⇒G )) ist der reflexiv-transitive Abschluss von ⇒G .
Eine Ableitung in G ist eine endliche Sequenz α0 ⇒∗G αn , d.h. α0 ⇒G α1 ⇒G . . . ⇒G αn .
def
3. Die Sprache von G, bzw. die von G erzeugte Sprache, ist L(G) = { w ∈ Σ∗ | S ⇒∗G w }.
4. Zwei Grammatiken G1 = (V1 , Σ, P1 , S1 ) und G2 = (V2 , Σ, P2 , S2 ) mit dem selben Terminalalphabet Σ heißen äquivalent, falls L(G1 ) = L(G2 ).
Version 17, 18. Dezember 2014
11
2.2
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Reguläre Sprachen (Typ 3)
Definition 2.2.1 (Reguläre Grammatik). Eine Grammatik G = (V, Σ, P, S) ist regulär, falls für jede
Produktion (α → β) ∈ P gilt:
1. entweder A → wB (also α = A und β = wB)
2. oder A → w (also α = A und β = w)
mit A, B ∈ V und w ∈ Σ∗ .
In dieser Form heißt G auch rechtslinear. Ersetzt man wB durch Bw, dann heißt G linkslinear. Beide
Varianten sind gleichwertig.
Definition 2.2.2 (Normalform von regulären Grammatiken).
Sei G = (V, Σ, P, S) eine reguläre Grammatik.
G ist in Normalform, falls jede Produktion aus P eine der folgenden Formen hat:
X → aZ
X→a
S→ε
mit X, Z ∈ V und a ∈ Σ.
Algorithmus 2.2.3 (Reguläre Grammatik Normalform).
Sei G = (V, Σ, P, S) eine reguläre Grammatik. Wir erzeugen eine zugehörige reguläre Grammatik in
Normalform G = (V , Σ, P , S) schrittweise wie folgt:
1. Initialisiere V = V und P = P.
2. Für jede Regel der Form A → wB mit B ∈ V und |w| > 1 wähle A1 , . . . , An mit n = |w| − 1
und A1 , . . . , An ∈
/ (V ∪ Σ). Füge A1 , . . . , An zu V hinzu. Ersetze A → wB in P durch die
Regeln A → (w)1 A1 , . . . , An−1 → (w)n An , An → (w)n+1 B.
3. Solange es Regeln der Form A → B mit B ∈ V in P gibt, ersetze eine dieser Regel in P
durch die Regeln A → β1 | . . . | βn , wobei { β1 , . . . , βn } = { β | (B, β) ∈ P ∧ β ∈
/ { A, B } }.
4. Berechne Vε = { A ∈ V | (A, ε) ∈ P ∧ A = S }. Entferne aus P alle Regeln der Form A → ε
mit A = S. Für jede Regel der Form A → aB mit B ∈ Vε in P füge A → a zu P hinzu.
Satz 2.2.4. Sei G eine reguläre Grammatik und G die nach obigem Algorithmus erzeugte zugehörige reguläre Grammatik in Normalform. Es gilt L(G) = L(G ).
Definition 2.2.5 (DFA).
Ein deterministischer endlicher Automat (DFA) ist ein 5-Tupel M = (Q, Σ, δ, q0 , F), wobei
• Q eine endliche Menge von Zuständen ist,
• Σ eine endliche Symbolmenge ist, das Eingabealphabet,
• δ : Q × Σ Q eine partielle Abbildung ist, die Übergangsfunktion (bzw. Transitionsfunktion),
• q0 ∈ Q der Startzustand ist und
• F ⊆ Q die Menge der (akzeptierenden) Endzustände ist.
Version 17, 18. Dezember 2014
12
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Definition 2.2.6 (Berechnungen). Sei M = (Q, Σ, δ, q0 , F) ein DFA.
Wir erweitern die Übergangsfunktion δ auf δ : Q × Σ∗ Q durch
def
def
δ(q, ε) = q
δ(q, wa) = δ δ(q, w) , a
mit q ∈ Q, w ∈ Σ∗ und a ∈ Σ.
Definition 2.2.7 (Sprache eines DFA). Sei M = (Q, Σ, δ, q0 , F) ein DFA.
1. M akzeptiert das Wort w ∈ Σ∗ g.d.w. δ(q0 , w) ∈ F.
Wenn δ(q0 , w) ∈
/ F, dann verwirft M das Wort w.
2. Die von M akzeptierte Sprache ist definiert durch:
L(M) =
def
w ∈ Σ∗ | δ(q0 , w) ∈ F
Definition 2.2.8 (Totaler DFA). Ein totaler DFA ist ein DFA mit totaler Überführungsfunktion.
Algorithmus 2.2.9 (Totaler DFA). Sei M = (Q, Σ, δ, q0 , F) ein DFA mit nicht-totaler Übergangsfunktion. Wir erzeugen einen zugehörigen totalen DFA Mtot durch Hinzunahme einer sogenannten
Senke s ∈
/ Q wie folgt:
Mtot = (Q ∪ { s } , Σtot , q0 , F) , wobei δtot =
def
def
δ(q, a)
s
, falls q ∈ Q und a ∈ Σ und (q, a) ∈ δ
, sonst
Satz 2.2.10. Sei M ein nicht-totaler DFA und Mtot der nach obigem Algorithmus erzeugte zugehörige totale DFA. Es gilt L(M) = L(Mtot ).
Algorithmus 2.2.11 (DFA reguläre Grammatik). Sei ein DFA M = (Q, Σ, δ, q0 , F) mit Q ∩ Σ = ∅.
Wir erzeugen eine zugehörige reguläre Grammatik G = (V, Σ, P, S) wie folgt:
def
def
1. Setze V = Q und S = q0 . Initialisiere P = ∅
2. Für jeden Übergang δ(q, a) = q füge q → aq und für alle q ∈ F füge q → ε zu P hinzu.
Satz 2.2.12. Sei M ein DFA und G die nach obigem Algorithmus erzeugte zugehörige reguläre
Grammatik. Es gilt L(M) = L(G).
Definition 2.2.13 (ε-NFA). Ein nichtdeterministischer endlicher Automat mit ε-Übergängen (εNFA) ist ein 5-Tupel M = (Q, Σ, δ, S, F) wobei
• Q eine endliche Menge von Zuständen ist,
• Σ eine endliche Symbolmenge ist, das Eingabealphabet,
• δ : Q × (Σ ∪ { ε }) → 2Q eine (totale) Abbildung ist, die Übergangsfunktion,
• S ⊆ Q die Menge der Startzustände ist und
• F ⊆ Q die Menge der (akzeptierenden) Endzustände ist.
Version 17, 18. Dezember 2014
13
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Definition 2.2.14 (NFA). Ein nichtdeterministischer endlicher Automat (NFA) ist ein ε-NFA ohne
ε-Übergänge, dass heißt mit δ : Q × Σ → 2Q statt δ : Q × (Σ ∪ { ε }) → 2Q .
Definition 2.2.15 (Berechnungen). Sei M = (Q, Σ, δ, S, F) ein ε-NFA.
Wir erweitern δ auf δ : 2Q × Σ∗ → 2Q durch
def
δ(X, ε) = X ∪
def
q∈X δ(q, ε)
δ(X, wa) =
q∈δ(X,w)
δ(q, a)
mit X ⊆ Q, w ∈ Σ∗ und a ∈ Σ. Für einen NFA ergibt sich δ analog mit δ(X, ε) = X.
def
Definition 2.2.16 (Sprache eines ε-NFA/NFA). Sei M = (Q, Σ, δ, S, F) ein ε-NFA/NFA.
1. M akzeptiert das Wort w ∈ Σ∗ g.d.w. δ(S, w) ∩ F = ∅.
Wenn δ(S, w) ∩ F = ∅, dann verwirft M das Wort w.
2. Die von M akzeptierte Sprache ist definiert durch:
L(M) =
def
w ∈ Σ∗ | δ(S, w) ∩ F = ∅
Satz 2.2.17 (NFA
ε-NFA). Sei M = (Q, Σ, δ, S, F) ein NFA.
def
Dann ist M = (Q, Σ, δ ∪ { (q, ε, ∅) | q ∈ Q } , S, F) ein ε-NFA mit L(M) = L(M ).
Satz 2.2.18 (ε-NFA NFA). Sei M = (Q, Σ, δ, S, F) ein ε-NFA. Dann ist
def
M = Q, Σ, (q, a, X) | q ∈ Q ∧ a ∈ Σ ∧ δ({ q } , a) = X , q | q ∈ δ(S, ε) , F ein NFA
mit L(M) = L(M ).
Algorithmus 2.2.19 (Reguläre Grammatik in Normalform NFA).
Sei G = (V, Σ, P, S) eine reguläre Grammatik in Normalform.
Wir erzeugen einen NFA M = (Q, Σ, δ, S, F) schrittweise wie folgt:
1. Gibt es mindestens eine Regel A → a für ein A ∈ V und ein a ∈ Σ:
{ S, E } ,
def
def
def
Ja: Wähle E ∈
/ (V ∪ Σ). Setze Q = V ∪ { E }, S = { S } und F =
{E},
falls ε ∈ L(G)
.
sonst
{ S } , falls ε ∈ L(G)
.
∅,
sonst
2. Initialisiere δ mit δ(q, a) = ∅ für alle q ∈ Q und alle a ∈ Σ.
3. Für jede Regel A → aB füge B zu δ(A, a) hinzu.
Für jede Regel A → a füge E zu δ(A, a) hinzu.
Nein: Setze Q = V, S = { S } und F =
def
def
def
Satz 2.2.20. Sei G eine reguläre Grammatik in Normalform und M der nach obigem Algorithmus
erzeugte zugehörige NFA. Es gilt L(G) = L(M).
Version 17, 18. Dezember 2014
14
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Algorithmus 2.2.21 (Potenzmengenkonstruktion).
Die Determinisierungsfunktion D : NFA → DFA mit (Q, Σ, δ, S, F) → (QD , Σ, δD , qD , FD ) zur Umwandlung eines beliebigen NFA in einen gleichwertigen DFA ist definiert als:
def
def
QD = 2Q
def
δD (X, a) =
q∈X δ(q, a)
qD = S
def
FD = { X ⊆ Q | X ∩ F = ∅ }
Satz 2.2.22. Sei M ein NFA. Dann gilt: L(M) = L(D(M)).
Algorithmus 2.2.23 (Optimierte Potenzmengenkonstruktion).
Sei M = (Q, Σ, δ, S, F) ein NFA. Die optimierte Determinisierungsfunktion oD : NFA → DFA erdef
zeugt einen zugehörigen DFA oD(M) = (QoD , Σ, δoD , qoD , FoD ) schrittweise wie folgt:
def
1. Setze qoD = S und initialisiere QoD = δoD = ∅ und Qneu = { qoD }.
2. Solange Qneu = ∅, wähle ein X ∈ Qneu und streiche X aus Qneu . Für alle a ∈ Σ berechne
Xa = q∈X δ(q, a). Falls Xa ∈
/ (QoD ∪ Qneu ∪ { X }), füge Xa zu Qneu hinzu.
Dann, falls Xa = ∅, füge Xa zu QoD und δoD (X, a) = X zu δoD hinzu.
def
3. Setze FoD = { X ⊆ QoD | X ∩ F = ∅ }.
Satz 2.2.24. Sei M ein NFA. Dann gilt: L(M) = L(oD(M)).
Satz 2.2.25 (Minimierung).
Sei M = (Q, Σ, δ, q0 , F) ein DFA und sei R : Q × Q eine Äquivalenz, so dass
∀q1 ∈ F . ∀q2 ∈ (Q \ F) . [q1 ]R = [q2 ]R
∀q1 , q2 ∈ Q . [q1 ]R = [q2 ]R → (∀a ∈ Σ . [δ(q1 , a)]R = [δ(q2 , a)]R )
und
Dann ist auch M = (Q/R, Σ, δ , [q0 ]R , F ) mit
def
δ ([q]R , a) = [δ(q, a)]R
für alle q ∈ Q und a ∈ Σ
F = { [qF ]R | qF ∈ F }
def
ein DFA und es gilt L(M) = L(M ).
Definition 2.2.26 (Reguläre Ausdrücke).
Sei Σ ein Alphabet mit Σ ∩ { ∅, ε } = ∅. Die Menge E der regulären Ausdrücke über Σ ist als kleinste
Menge definiert, die die folgenden Regeln erfüllt:
1. ∅ ∈ E, ε ∈ E, a ∈ E für alle a ∈ Σ.
2. Falls e ∈ E, dann auch e∗ ∈ E und e+ ∈ E.
3. Falls e1 ∈ E und e2 ∈ E, dann auch e1 · e2 ∈ E und e1 + e2 ∈ E.
Der Ausdruck e1 · e2 wird oft durch e1 e2 abgekürzt. Es gilt: ∗ hat Vorrang vor · hat Vorrang vor +.
Version 17, 18. Dezember 2014
15
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Definition 2.2.27 (Sprache regulärer Ausdrücke). Sei Σ ein Alphabet mit Σ ∩ { ∅, ε } = ∅. Die Ab∗
bildung L : E → 2Σ definiert die Sprache eines regulären Ausdrucks durch:
∅ → ∅
e∗ → L(e)∗
e1 · e2 → L(e1 ) · L(e2 )
ε → {ε}
a → {a}
für alle a ∈ Σ
+
+
e → L(e)
e1 + e2 → L(e1 ) ∪ L(e2 )
Notation 2.2.28. Die Schreibweisen an und a∗ werden häufig verwechselt. an bezeichnet ein
einzelnes Wort. a∗ bezeichnet eine ganze Sprache, nämlich L(a∗ ) = { an | ∃n ∈ N }.
Definition 2.2.29 (Äquivalenz regulärer Ausdrück). Zwei reguläre Ausdrücke e1 und e2 sind äquivalent, geschrieben e1 ≡ e2 , wenn L(e1 ) = L(e2 ).
Algorithmus 2.2.30 (Regulärer Ausdruck
ε-NFA). Sei e ein regulärer Ausdruck ohne ∅ über
dem Alphabet Σ. Wir erzeugen einen ε-NFA M = (Q, Σ, δ, S, F) schrittweise wie folgt:
def
def
1. Setze S = { qs } und F = { qe }. Initialisiere Q = { qs , qe } und den Graph mit:
e
q
q
s
e
2. Wende solange wie möglich eine der folgenden Regeln an:
• Wähle ein p ∈
/ Q, füge p zu Q hinzu und ersetze einen Übergang
e1
e2
q
p
q
e + e2
e ,e
q 1
q 1 2 q
q
• Ersetze einen Übergang
durch:
• Wähle ein p ∈
/ Q, füge p zu Q hinzu und ersetze einen Übergang
e
q
ε
p
ε
e
p
ε
q
3. Setze δ entsprechend des erzeugten Graphen.
Version 17, 18. Dezember 2014
e1 e2
q
e∗
q
e+
q
q
durch:
durch:
q
• Wähle ein p ∈
/ Q, füge p zu Q hinzu und ersetze einen Übergang
e
q
q
16
q
durch:
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Satz 2.2.31. Sei e eine regulärer Ausdruck ohne ∅ und M der nach obigem Algorithmus erzeugte
zugehörige ε-NFA. Es gilt L(e) = L(M).
Satz 2.2.32.
∅∗ ≡ ε ∅+ ≡ ∅
∅·e ≡ ∅ ≡ e·∅
∅+e ≡ e ≡ e+∅
e1 (e2 + e3 ) ≡ e1 e2 + e1 e3
∗
+
ε ≡ε≡ε
ε·e ≡ e ≡ e·ε
e 1 + e2 ≡ e2 + e1
(e1 + e2 )e3 ≡ e1 e3 + e2 e3
e+e ≡ e
(e1 + e2 ) + e3 ≡ e1 + (e2 + e3 )
(e1 e2 )e3 ≡ e1 (e2 e3 )
Algorithmus 2.2.33 (NFA Regulärer Ausdruck). Sei M = (Q, Σ, δ, S, F) ein NFA.
Wir erzeugen einen zugehörigen regulären Ausdruck e schrittweise wie folgt:
1. Entferne aus dem NFA M alle Zustände (zusammen mit allen ein- oder ausgehende Kanten), die entweder nicht von einem Startzustand aus erreichbar sind oder von denen aus kein
Endzustand erreichbar ist.
2. Nummeriere die übrigen Zustände Q = { q1 , . . . , qn }. Erzeuge ein Gleichungssystem mit je
einer Gleichung pro Zustand wie folgt:
• Für alle qi ∈
/ F erzeuge die Gleichung ei ≡ Σa∈Σ Σr∈δ(qi ,a) aer .
• Für alle qi ∈ F erzeuge die Gleichung ei ≡ Σa∈Σ Σr∈δ(qi ,a) aer + ε.
In beiden Fällen ist Σr∈δ(qi ,a) aer = ∅ falls δ(qi , a) = ∅.
3. Löse das Gleichungssystem mit Hilfe der Ersetzungsregeln:
• Aus ei ≡ ej ei + ek folgt ei ≡ e∗j ek .
• Aus ei ≡ ej ei folgt ei ≡ ∅.
4. e = Σqi ∈S ei .
Satz 2.2.34. Sei M ein NFA und e der nach obigem Algorithmus erzeugte zugehörige reguläre
Ausdruck. Es gilt L(M) = L(e).
Satz 2.2.35. Sei L ⊆ Σ∗ eine Sprache über Σ. Die folgenden Aussagen sind äquivalent:
1. Die Sprache L ist regulär (Typ 3).
2. Es existiert eine reguläre Grammatik G = (V, Σ, P, S) mit L(G) = L.
3. Es existiert ein DFA M = (Q, Σ, δ, q0 , F) mit L(M) = L.
4. Es existiert ein NFA M = (Q , Σ, δ, S, F ) mit L(M ) = L.
5. Es existiert ein regulärer Ausdruck e mit L(e) = L.
Satz 2.2.36. Alle endlichen Sprachen sind regulär.
Satz 2.2.37 (Abschlusseigenschaften).
Seien LA , LB reguläre Sprachen über Σ. Dann gilt:
1. LA ∩ LB ist regulär.
4. (LA )∗ ist regulär.
2. LA ∪ LB ist regulär.
5. Σ∗ \ LA = LA ist regulär.
3. LA LB ist regulär.
6. LA \ LB ist regulär.
Version 17, 18. Dezember 2014
17
2.2
Reguläre Sprachen (Typ 3)
Formale Systeme
Satz 2.2.38 (Pumping Lemma).
Sei Σ ein Alphabet und L ⊆ Σ∗ . Sei die Formel PUMP(L) definiert durch:
def
PUMP(L) = ∃n ∈ N . ∀z ∈ L .
→ ∃u, v, w ∈ Σ∗ . ♣ ∧ ♥ ∧ ♠ ∧ ♦
mit:
def
= |z|
def
n
♣ = z = uvw
def
♥ = |v| 1
def
♠ = |uv| n
def
♦ = ∀k ∈ N . uvk w ∈ L
Die Umkehrung ¬ PUMP(L) ist damit:
¬ PUMP(L) ↔ ∀n ∈ N . ∃z ∈ L .
∧ ∀u, v, w ∈ Σ∗ . (♣ ∧ ♥ ∧ ♠) → ¬♦
¬♦ ↔ ∃k ∈ N . uvk w ∈
/L
Das Pumping Lemma besagt:
1. Wenn L regulär ist, dann gilt die Formel PUMP(L).
2. Wenn die Formel ¬ PUMP(L) gilt, dann ist L nicht regulär.
Bemerkung 2.2.39.
Die Umkehrung des Pumping Lemma gilt im Allgemeinen nicht,
d.h. es gibt nicht-reguläre Sprachen, die dem Pumping Lemma genügen.
Definition 2.2.40 (Nerode-Äquivalenz, Nerode-Index). Sei L ⊆ Σ∗ eine Sprache. Die NerodeÄquivalenz für L bezeichnet diejenige Äquivalenzrelation ∼L auf Σ∗ , für die für alle Wörter x, y ∈
Σ∗ gilt:
x ∼L y genau dann wenn ∀z ∈ Σ∗ . xz ∈ L ↔ yz ∈ L
Wir schreiben [x]L für die Äquivalenzklasse von x bzgl. ∼L und Σ∗ /L für den Quotient Σ∗ / ∼L .
Der Nerode-Index von L bezeichnet die Anzahl an Elementen in Σ∗ /L.
Satz 2.2.41 (Satz von Myhill & Nerode). Sei L eine Sprache. L ist genau dann regulär, wenn der
Nerode-Index von L endlich ist.
Version 17, 18. Dezember 2014
18
2.3
2.3
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Kontextfreie Sprachen (Typ 2)
Definition 2.3.1 (Kontextfreie Grammatik (CFG)).
Eine Grammatik G = (V, Σ, P, S) ist kontextfrei (kurz CFG), falls für jede Produktion (α → β) ∈ P
gilt:
α∈V
Die Größe einer CFG bezeichnen wir mit #(G) = #(V) + Σ(α,β)∈P (|α| + |β|).
def
Definition 2.3.2 (ε-Freiheit). Sei G = (V, Σ, P, S) eine CFG. G heißt ε-frei, wenn:
1. Aus X → ε folgt X = S.
2. Falls S → ε ∈ P, dann gibt es keine Regel X → β, so dass S in β vorkommt.
Algorithmus 2.3.3 (CFG ε-freie CFG). Sei G = (V, Σ, P, S) eine CFG. Wir erzeugen eine zugehörige ε-freie CFG G = (V , Σ, P , S ) schrittweise wie folgt:
1. Berechne Vε = { X ∈ V | X ⇒∗ ε }. Initialisiere P = P \ { X → ε ∈ P | X ∈ V }.
2. Solange es eine Regel X → xYy mit Y ∈ Vε , |xy| 1 und X → xy gibt, wähle eine solche
Regel und füge X → xy zu P hinzu.
def
3. Falls S ∈ Vε , wähle ein S ∈
/ V setze V = V ∪ { S } und füge S → ε | S zu P hinzu.
def
def
Ansonsten setze V = V und S = S.
Algorithmus 2.3.4 (Nutzlose Variablen). Sei G = (V, Σ, P, S) eine CFG. Eine Variable X ∈ V \ { S }
ist nutzlos, wenn es kein Wort w ∈ Σ∗ gibt so, dass X ⇒∗ w.
Wir ermitteln die nutzlosen Variablen von G schrittweise wie folgt:
1. Markiere alle Variablen X mit X → w in P für ein w ∈ Σ∗ .
2. Solange es Regeln der Form X → β gibt so, dass X nicht markiert ist und alle Variablen in β
markiert sind, wähle eine solche Regel und markiere X.
3. Alle nicht markierten Variablen sind in G nutzlos.
Satz 2.3.5. Sei G = (V, Σ, P, S) eine CFG und V ⊂ V nutzlose Variablen in G. Dann ist G =
V \ V , Σ, X → β ∈ P | X ∈ V \ V ∧ β ∈ ((V \ V ) ∪ Σ)∗ , S eine CFG mit L(G) = L(G ).
Algorithmus 2.3.6 (Erzeugbare Variablen). Sei G = (V, Σ, P, S) eine CFG. Eine Variable X ∈ V ist
erzeugbar in G, wenn es ein Wort w ∈ (Σ ∪ V)∗ gibt so, dass X in w enthalten ist und S ⇒∗ w.
Wir ermitteln die erzeugbaren Variablen von G durch Umkehrung des Markierungsalgorithmus:
1. Markiere S.
2. Solange es Regeln der Form X → β gibt so, dass X markiert ist aber nicht alle Variablen in
β markiert sind, wähle eine solche Regel und markiere alle Variablen in β.
3. Alle markierten Variablen sind in G erzeugbar.
Version 17, 18. Dezember 2014
19
2.3
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Satz 2.3.7. Sei G = (V, Σ, P, S) eine CFG und V ⊆ V alle erzeugbare Variablen in G. Dann ist
G = V , Σ, X → β ∈ P | X ∈ V ∧ β ∈ (V ∪ Σ)∗ , S eine CFG mit L(G) = L(G ).
Definition 2.3.8 (Bereinigte CFG). Eine CFG G nennen wir bereinigt, wenn G keine nutzlosen oder
nicht-erzeugbaren Variablen enthält.
Algorithmus 2.3.9 (CFG CFG ohne Kettenregeln). Sei G = (V, Σ, P, S) eine CFG.
Wir erzeugen eine zugehörige CFG G = (V , Σ, P , S) ohne Kettenregeln schrittweise wie folgt:
1. Initialisiere V = V und P = { X → β ∈ P | X = β }.
2. Solange es in P einen Zyklus der Form X0 → X1 , . . . , Xn → X0 gibt, wähle einen solchen
Zyklus. Wenn S ∈ { X0 , . . . , Xn }, dann wähle Y = S. Ansonsten wähle ein Y ∈ { X0 , . . . , Xn }.
(a) Ersetze in P alle Vorkommen von X ∈ ({ X0 , . . . , Xn } \ { Y }) durch Y.
(b) Entferne aus P alle Regeln der Form Z → Z.
(c) Entferne aus V alle Variablen aus { X0 , . . . , Xn } \ { Y }.
3. Nummeriere die übrigen Variablen V = { X1 , . . . , Xk } so, dass für jede verbliebene Kettenregel
Xi → Xj gilt i < j.
4. Entferne die übrigen Kettenregeln entsprechend des folgenden Algorithmus in Pseudocode:
FOR i = k − 1, . . . , 1 DO
FOR j = i + 1, . . . , k DO
IF Xi → Xj THEN
Streiche Xi → Xj aus P .
FOR ALL Xj → x DO
Füge Xi → x zu P hinzu.
OD
FI
OD
OD
Definition 2.3.10 (Normalform von kontextfreien Grammatiken).
Sei G = (V, Σ, P, S) eine kontextfreie Grammatik.
1. G ist in Chomsky-Normalform,
falls jede Produktion aus P eine der folgenden Formen hat:
X → YZ
X → a
S → ε
mit X, Y, Z ∈ V und a ∈ Σ.
2. G ist in Greibach-Normalform,
falls jede Produktion aus P eine der folgenden Formen hat:
X → aY1 · · · Yk
mit k ∈ N, X, Y1 , . . . , Yk ∈ V und a ∈ Σ.
Version 17, 18. Dezember 2014
20
S → ε
2.3
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Satz 2.3.11. Zu jeder CFG G gibt es eine CFG G in Chomsky-Normalform und eine CFG G in
Greibach-Normalform mit L(G) = L(G ) = L(G ).
Algorithmus 2.3.12 (CFG
CFG in Chomsky-Normalform). Sei G = (V, Σ, P, S) eine CFG.
Wir erzeugen eine zugehörige CFG G4 in Chomsky-Normalform wie folgt:
1. Erzeuge die zu G gehörige ε-freie CFG G1 .
2. Erzeuge die zu G1 gehörige CFG G2 ohne Kettenregeln.
3. Erzeuge G3 = (V3 , Σ, P3 , S) aus G2 = (V2 , Σ, P2 , S) schrittweise wie folgt:
(a) Initialisiere V3 = V2 und P3 = P2 .
(b) Wähle für jedes a ∈ Σ ein Xa ∈
/ V3 so, dass für alle a, b ∈ Σ mit a = b gilt Xa = Xb .
(c) Solange es eine Regel der Form X → w mit |w| 2 und w ∈
/ V∗3 in P3 gibt, wähle eine
solche Regel. Ersetze alle Terminale a ∈ Σ in w durch die entsprechende Variable Xa
und füge (falls noch nicht vorhanden) Xa zu V3 und Xa → a zu P3 hinzu.
4. Erzeuge G4 = (V4 , Σ, P4 , S) aus G3 = (V3 , Σ, P3 , S) schrittweise wie folgt:
(a) Initialisiere V4 = V3 und P4 = P3 .
(b) Solange es eine Regel X → Y1 . . . Yn mit n 3 in P4 gibt, wähle eine solche Regel.
Wähle paarweise verschiedene Variablen Z1 , . . . , Zn−2 ∈
/ V4 . Füge Z1 , . . . , Zn−2 zu V4
hinzu. Ersetze X → Y1 . . . Yn in P4 durch X → Y1 Z1 , Z1 → Y2 Z2 , . . . , Zn−2 → Yn−1 Yn .
Algorithmus 2.3.13 (Cocke-Younger-Kasami (CYK)). Sei G = (V, Σ, P, S) eine CFG in ChomskyNormalform, w = a1 . . . an ∈ Σ∗ und wi,j = ai . . . ai+j−1 für alle 1 i n und 1 j n + 1 − i.
W = ε ist in L(G) falls S → ε ∈ P. Für w = ε prüfen wir w ∈ L(G) schrittweise wie folgt:
def
1. Für alle 1 i n bestimme V[i, 1] = { X ∈ V | X → ai }.
2. Erzeuge nacheinander beginnend mit j = 2 und i = 1 alle
j−1
{ X ∈ V | ∃Y, Z ∈ V . X → YZ ∈ P ∧ Y ∈ V[i, l] ∧ Z ∈ V[i + l, j − l] }
def
V[i, j] =
l=1
für 2 j n und 1 i n + 1 − j, wobei zunächst i hochgezählt und, für jeden neuen Wert
von j, i wieder auf 1 initialisiert wird.
3. w ∈ L(G) falls S ∈ V[1, n].
Satz 2.3.14. Das Wortproblem lässt sich für eine CFG in Chomsky-Normalform und Wörter w ∈ Σ∗
der Länge |w| = n mit dem CYK-Algorithmus in Zeit O n3 und Platz O n2 lösen.
Version 17, 18. Dezember 2014
21
2.3
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Definition 2.3.15 (Nichtdeterministischer Kellerautomat (NKA)).
Ein nichtdeterministischer Kellerautomat (NKA) ist ein 7-Tupel K = (Q, Σ, Γ , δ, q0 , #, F) wobei
• Q eine endliche Menge von Zuständen ist,
• Σ eine endliche Symbolmenge, das Eingabealphabet, ist,
• Γ eine endliche Symbolmenge, das Kelleralphabet, ist,
∗
• δ : (Q × (Σ ∪ { ε }) × Γ ) → 2Q×Γ die totale Überführungsfunktion ist,
• q0 ∈ Q der Startzustand ist,
• # ∈ Γ das unterste Kellerzeichen ist und
• F ⊆ Q eine Menge von Endzuständen ist.
Definition 2.3.16 (Berechnungen). Sei K = (Q, Σ, Γ , δ, q0 , #, F) ein NKA.
1. Eine Konfiguration von K ist ein Tripel (q, w, γ) ∈ (Q × Σ∗ × Γ ∗ ).
2. Die binäre Relation K auf Konfigurationen von K ist definiert durch:
(q, aw, Xβ)
(q, w, Xβ)
falls (q , α) ∈ δ(q, a, X)
falls (q , α) ∈ δ(q, ε, X)
(q , w, αβ)
K (q , w, αβ)
K
(c, c ) mit c K c bezeichnet einen Berechnungsschritt von K.
3. Eine Berechnung von K für das Eingabewort w ist eine Sequenz von Konfigurationen von
K,
(q0 , w, #)
K
(q1 , w1 , γ1 )
K
...
K
(qi , wi , γi )
K
...
wobei (q0 , w, #) Initial- oder Anfangskonfiguration der Berechnung heißt.
Wir schreiben oft anstelle von K . ∗ ist der reflexive und transitive Abschluss von .
Lemma 2.3.17. Sei K = (Q, Σ, Γ , δ, q0 , #, F) ein NKA.
1. Wenn (q, x, α) ∗ (q , y, β),
dann gilt für alle w ∈ Σ∗ und γ ∈ Γ ∗ : (q, xw, αγ)
2. Wenn (q, xw, α) ∗ (q , yw, β), dann gilt (q, x, α)
∗
∗
(q , yw, βγ).
(q , y, β).
Definition 2.3.18 (Sprache eines NKA). Sei K = (Q, Σ, Γ , δ, q0 , #, F) ein NKA.
1. Die durch Endzustände akzeptierte Sprache von K ist definiert durch:
L(K) = { w ∈ Σ∗ | ∃q ∈ F . ∃α ∈ Γ ∗ . (q0 , w, #)
def
∗
(q, ε, α) }
2. Die durch leeren Keller akzeptierte Sprache von K ist definiert durch:
Lε (K) = { w ∈ Σ∗ | ∃q ∈ Q . (q0 , w, #)
def
∗
(q, ε, ε) }
Satz 2.3.19. Sei Σ ein Alphabet und L ⊆ Σ∗ . Dann sind die folgenden Aussagen äquivalent:
1. Es existiert eine kontextfreie Grammatik G = (V, Σ, P, S) mit L(G) = L.
2. Es existiert ein NKA K1 = (Q1 , Σ, Γ1 , δ1 , q0 , #, F) mit L(K1 ) = L.
3. Es existiert ein NKA K2 = (Q2 , Σ, Γ2 , δ2 , q0 , #, ∅) mit Lε (K2 ) = L.
4. Die Sprache L ist kontextfrei (Typ 2).
Version 17, 18. Dezember 2014
22
2.3
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Satz 2.3.20 (CFG in Greibach-Normalform
NKA). Sei G = (V, Σ, P, S) eine CFG in Greibachdef
Normalform. Dann gilt für den NKA K = ({ q0 } , Σ, V, δ, q0 , S) mit
δ(q0 , x, X) = { (q0 , Y1 . . . Yk ) | x ∈ Σ ∧ X → xY1 . . . Yk ∈ P } ∪ { (q0 , ε) | x = ε ∧ X → ε ∈ P } ,
def
dass Lε (K) = L(G).
Satz 2.3.21 (NKA
CFG). Sei K = (Q, Σ, Γ , δ, q0 , #) ein NKA.
def
Dann gilt für die CFG G = ({ S } ∪ (Q × Γ × Q) , Σ, P, S) mit
P = { S → (q0 , #, p) | p ∈ Q }
def
∪ (q, X, p) → a q , B1 , p1 (p1 , B2 , p2 ) . . . (pk−1 , Bk , p) |
q , B1 . . . Bk ∈ δ(q, a, X) ∧ a ∈ Σ ∧ k
∪
q, X, q
1 ∧ p, p1 , . . . , pk−1 ∈ Q
→ a | q , ε ∈ δ(q, a, X)
∪ (q, X, p) → q , B1 , p1 (p1 , B2 , p2 ) . . . (pk−1 , Bk , p) |
q , B1 . . . Bk ∈ δ(q, ε, X) ∧ a ∈ Σ ∧ k
∪
q, X, q
1 ∧ p, p1 , . . . , pk−1 ∈ Q
→ ε | q , ε ∈ δ(q, ε, X) ,
dass L(G) = Lε (K).
Satz 2.3.22. Alle regulären Sprachen sind kontextfrei.
Satz 2.3.23 (Abschlusseigenschaften). Seien LA , LB kontextfreie Sprachen über Σ. Dann gilt:
1. LA ∪ LB ist kontextfrei.
2. LA LB ist kontextfrei.
3. L∗A ist kontextfrei.
∗
und, falls LC ⊆ Σ eine reguläre Sprache ist:
4. LA ∩ LC ist kontextfrei.
5. LA \ LC ist kontextfrei.
Dagegen gilt:
6. LA ∩ LB ist nicht notwendigerweise kontextfrei.
7. Σ∗ \ LA ist nicht notwendigerweise kontextfrei.
8. LA \ LB ist nicht notwendigerweise kontextfrei.
Satz 2.3.24. Sei G eine CFG in Chomsky-Normalform und w ∈ L(G) mit w = ε.
Ist h die Höhe eines Ableitungsbaumes für w in G, so gilt:
log2 |w| + 1
Version 17, 18. Dezember 2014
23
h
|w|
2.3
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Satz 2.3.25 (Pumping Lemma).
Sei Σ ein Alphabet und L ⊆ Σ∗ . Sei die Formel PUMP(L) definiert durch:
def
PUMP(L) = ∃n ∈ N . ∀z ∈ L .
→ ∃u, v, w, x, y ∈ Σ∗ . ♣ ∧ ♥ ∧ ♠ ∧ ♦
mit:
def
= |z|
def
n
♣ = z = uvwxy
def
♥ = |vx| 1
def
♠ = |vwx| n
def
♦ = ∀k ∈ N . uvk wxk y ∈ L
Die Umkehrung ¬ PUMP(L) ist damit:
¬ PUMP(L) ↔ ∀n ∈ N . ∃z ∈ L .
∧ ∀u, v, w, x, y ∈ Σ∗ . (♣ ∧ ♥ ∧ ♠) → ¬♦
¬♦ ↔ ∃k ∈ N . uvk wxk y ∈
/L
Das Pumping Lemma für kontextfreie Sprachen besagt:
1. Wenn L kontextfrei ist, dann gilt die Formel PUMP(L).
2. Wenn die Formel ¬ PUMP(L) gilt, dann ist L nicht kontextfrei.
Bemerkung 2.3.26.
Die Umkehrung des Pumping Lemma gilt im Allgemeinen nicht,
d.h. es gibt nicht-kontextfreie Sprachen, die dem Pumping Lemma genügen.
Version 17, 18. Dezember 2014
24
2.3
2.3.1
Kontextfreie Sprachen (Typ 2)
Formale Systeme
Deterministisch Kontextfreie Sprachen
Definition 2.3.27 (DKA).
Ein deterministischer Kellerautomat (DKA) ist ein NKA K = (Q, Σ, Γ , δ, q0 , #, F) so, dass für alle
q ∈ Q, a ∈ Σ und X ∈ Γ gilt:
#(δ(q, a, X) ∪ δ(q, ε, X))
1
Eine Sprache L ist deterministisch kontextfrei, wenn es einen DKA K gibt, so dass L(K) = L.
Satz 2.3.28. Jede reguläre Sprache ist deterministisch kontextfrei und jede deterministisch kontextfreie Sprache ist kontextfrei. Es gibt Sprachen die deterministisch kontextfrei aber nicht regulär
sind. Es gibt Sprachen die kontextfrei aber nicht deterministisch kontextfrei sind.
Satz 2.3.29 (Abschlusseigenschaften). Seien LA , LB deterministisch kontextfreie Sprachen über Σ.
Dann gilt:
1. Σ∗ \ LA ist deterministisch kontextfrei.
und, falls LC ⊆ Σ∗ eine reguläre Sprache ist:
2. LA ∩ LC ist deterministisch kontextfrei.
3. LA \ LC ist deterministisch kontextfrei.
Dagegen gilt:
4. LA ∪ LB ist nicht notwendigerweise deterministisch kontextfrei.
5. LA ∩ LB ist nicht notwendigerweise deterministisch kontextfrei.
6. LA LB ist nicht notwendigerweise deterministisch kontextfrei.
7. LA \ LB ist nicht notwendigerweise deterministisch kontextfrei.
8. L∗A ist nicht notwendigerweise deterministisch kontextfrei.
Definition 2.3.30 (Präfixeigenschaft). Sei L ⊆ Σ∗ . L hat die Präfixeigenschaft, wenn für alle Wörter
w ∈ L und für alle echten Präfixe x von w, d.h. für alle Präfixe x von w mit |x| < |w|, gilt x ∈
/ L.
Satz 2.3.31. Sei L eine Sprache.
Dann ist L genau dann deterministisch kontextfrei mit der Präfixeigenschaft, wenn L = Lε (Kε ) für
einen DKA Kε .
Satz 2.3.32. Sei Σ ein Alphabet, $ ∈
/ Σ und L ⊆ Σ∗ .
Wenn L deterministisch kontextfrei ist, dann gibt es einen DKA Kε mit Lε (Kε ) = L$.
Version 17, 18. Dezember 2014
25
2.4
2.4
Kontextsensitive Sprachen (Typ 1)
Formale Systeme
Kontextsensitive Sprachen (Typ 1)
Definition 2.4.1 (Kontextsensitive Grammatik). Eine Grammatik G = (V, Σ, P, S) ist kontextsensitiv,
falls für jede Produktion (α → β) ∈ P gilt:
1. entweder |α| |β|
2. oder α = S und β = ε und
falls S → ε ∈ P dann gibt es keine Regel X → β so, dass S in β vorkommt.
Eine Sprache L ist kontextsensitiv, falls es eine kontextsensitive Grammatik G gibt, so dass L(G) = L.
Definition 2.4.2 (Normalform von kontextsensitiven Grammatiken).
Sei G = (V, Σ, P, S) eine kontextsensitive Grammatik. G ist in Kuroda-Normalform, falls jede Produktion aus P eine der folgenden Formen hat:
S→ε
W→a
W→X
W → XY
WX → YZ
mit W, X, Y, Z ∈ V und a ∈ Σ.
Satz 2.4.3. Zu jeder kontextsensitiven Grammatik G gibt es eine kontextsensitive Grammatik G in
Kuroda-Normalform mit L(G) = L(G ).
Satz 2.4.4. Jede kontextfreie Sprache ist kontextsensitiv.
Satz 2.4.5 (Abschlusseigenschaften).
Seien LA , LB kontextsensitive Sprachen über Σ. Dann gilt:
1. LA ∩ LB ist kontextsensitiv.
4. (LA )∗ ist kontextsensitiv.
2. LA ∪ LB ist kontextsensitiv.
5. Σ∗ \ LA ist kontextsensitiv.
3. LA LB ist kontextsensitiv.
6. LA \ LB ist kontextsensitiv.
2.5
Akzeptierbare oder Allgemeine Sprachen (Typ 0)
Definition 2.5.1 (Allgemeine Sprachen).
Eine Sprache L ist allgemein, wenn es eine eine Grammatik G gibt, so dass L(G) = L.
Satz 2.5.2. Jede kontextsensitive Sprache ist allgemein.
Satz 2.5.3 (Abschlusseigenschaften).
Seien LA , LB allgemeine Sprachen über Σ. Dann gilt:
1. LA ∩ LB ist allgemein.
3. LA LB ist allgemein.
2. LA ∪ LB ist allgemein.
4. (LA )∗ ist allgemein.
Version 17, 18. Dezember 2014
26
Formale Systeme
3
3.1
Aussagenlogik
Grundbegriffe
Definition 3.1.1 (Wahrheitswerte). In der Aussagenlogik unterscheiden wir zwei Wahrheitswerte:
1 (oder auch wahr oder
)
und
0 (oder auch falsch oder ⊥)
Die Menge B = { 0, 1 } wird Bool genannt.
Sei AP ein nicht-leere Menge von paarweise verschiedenen Booleschen Variablen.
Die Elemente von AP werden Aussagensymbole, Atome, oder atomare Formeln genannt.
Definition 3.1.2 (Aussagenlogische Formeln).
Die Menge aller aussagenlogischen Formeln über AP ist induktiv wie folgt gegeben:
1. true und false sind aussagenlogische Formeln über AP.
2. Jedes Aussagensymbol x ∈ AP ist eine aussagenlogische Formel über AP.
3. Wenn α und β aussagenlogische Formeln über AP, dann sind auch ¬α, α ∧ β, α ∨ β, α → β
und α ↔ β aussagenlogische Formeln über AP.
Die Operatorensymbole ¬, ∧, ∨, → und ↔ werden auch logische Junktoren genannt.
Notation 3.1.3 (Ausagenlogische Formeln).
Wir bezeichnen Ausagensymbole oft mit Kleinbuchstaben wie x, x1 , . . . , y, z und
ausagenlogische Formeln oft mit griechischen Buchstaben wie α, α1 , . . . , β, γ, . . ..
Für Formeln, die mehr als einen Junktor enthalten, verwenden wir Klammerpaare (·), um die Eindeutigkeit der Interpretation von Formeln sicherzustellen. Um die Klammerzahl zu reduzieren und
die Lesbarkeit der Formeln zu unterstützen, gelten darüberhinaus sogenannte Regeln des Operatorenvorrangs. Wir definieren, dass ¬ am stärksten bindet gefolgt von ∧, ∨, → und ↔ in dieser
Reihenfolge.
Definition 3.1.4 (Belegung).
Eine Belegung oder Interpretation für AP ist eine Abbildung I : AP → B.
Notation 3.1.5 (Belegung). Statt I : { x1 , . . . , xn } → B mit I(xi ) = bi für alle 1
wir oft kurz [x1 = b1 , . . . , xn = bn ] oder xI1 = b1 , . . . , xIn = bn .
i
n schreiben
Definition 3.1.6 (Wahrheitswert einer Formel).
Sei α eine aussagenlogische Formel über AP und I eine Belegung für AP.
Der durch I induzierte Wahrheitswert von α, geschrieben αI ∈ B, ist induktiv wie folgt definiert:
def
def
1. trueI = 1
5. falseI = 0
def
def
2. xI = I(x) für alle x ∈ AP
6. (α ∨ β)I = max αI , βI
def
def
3. (¬α)I = 1 − αI
7. (α → β)I = max (1 − αI ), βI
def
def
4. (α ∧ β)I = min αI , βI
8. (α ↔ β)I = 1 − αI − βI
Version 17, 18. Dezember 2014
27
3.1
Grundbegriffe
Formale Systeme
Definition 3.1.7 (Werte- oder Wahrheitstafeln). Der Wahrheitswert einer Formel unter einer Belegung kann auch mit Hilfe der Wahrheitstafeln für die Junktoren ermittelt werden.
α
0
1
¬α
1
0
α β
0 0
0 1
1 0
1 1
α∧β
0
0
0
1
α β
0 0
0 1
1 0
1 1
α∨β
0
1
1
1
α β
0 0
0 1
1 0
1 1
α→β
1
1
0
1
α β
0 0
0 1
1 0
1 1
α↔β
1
0
0
1
Definition 3.1.8 (Modell, Erfüllbarkeit, Gültigkeit).
Sei α eine aussagenlogische Formel über AP und I eine Belegung für AP.
Wenn αI = 1, dann nennen wir I eine erfüllende Belegung oder ein Modell für α.
α heißt erfüllbar, wenn es eine erfüllende Belegung für α gibt.
α heißt unerfüllbar, wenn α nicht erfüllbar ist.
α heißt Tautologie oder gültig, wenn alle Belegungen erfüllend sind.
Definition 3.1.9 (Logische Äquivalenz). Seien α und β aussagenlogische Formeln über AP.
α und β sind (semantisch) äquivalent, wenn sie unter jeder Interpretation denselben Wahrheitswert
haben. In diesem Fall schreiben wir α ≡ β.
Proposition 3.1.10 (Logische Äquivalenz).
α∧α
α∨α
α∧β
α∨β
α ∧ (α ∨ β)
α ∨ (α ∧ β)
α ∧ (β ∧ γ)
α ∨ (β ∨ γ)
α ∧ (β ∨ γ)
α ∨ (β ∧ γ)
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
¬¬α
¬false
¬true
¬ (α ∧ β)
¬ (α ∨ β)
α→β
α→β
α↔β
(α ∧ β) ∨ γ
(α ∨ β) ∧ γ
α
α
β∧α
β∨α
α
α
(α ∧ β) ∧ γ
(α ∨ β) ∨ γ
(α ∧ β) ∨ (α ∧ γ)
(α ∨ β) ∧ (α ∨ γ)
≡
≡
≡
≡
≡
≡
≡
≡
≡
≡
α
true
false
¬α ∨ ¬β
¬α ∧ ¬β
¬α ∨ β
¬β → ¬α
(α → β) ∧ (β → α)
(α ∨ γ) ∧ (β ∨ γ)
(α ∧ γ) ∨ (β ∧ γ)
Definition 3.1.11 (Modell und Erfüllbarkeit für Formelmengen).
Sei F eine Menge von Formeln über AP und I eine Belegung für AP.
I heißt Modell oder erfüllende Belegung für F, falls I ein Modell für alle Formeln α ∈ F ist.
F heißt erfüllbar/unerfüllbar, wenn es ein/kein Modell für F gibt.
F heißt tautologisch oder gültig, wenn jede Belegung über AP erfüllend für F ist.
Definition 3.1.12 (Logische Folgerung, Konsequenz).
Eine Formel α über AP ist eine logische Folgerung oder Konsequenz von einer Formelmenge F
über AP, wenn alle Modelle für F auch Modelle für α sind. In diesem Fall schreiben wir F α.
Version 17, 18. Dezember 2014
28
LITERATUR
Formale Systeme
Literatur
[EMC+ 01] Hartmut Ehrig, Bernd Mahr, Felix Cornelius, Martin Große-Rhode, and Philip Zeitz.
Mathematisch-strukturelle Grundlagen der Informatik. Springer, Berlin Heidelberg
New York, 2001. 2. Auflage, ISBN 3-540-41923-3.
[Hof11]
Dirk W. Hoffmann. Theoretische Informatik. Hanser Verlag, 2011. 2. Auflage, ISBN
978-3-446-42639-9.
[HUM02] John E Hopcroft, Jeffrey D Ullman, and Rajeev Motwani. Einführung in die Automatentheorie, Formale Sprache und Komplexität. Pearson Studium, 2002.
[Sch08]
Uwe Schöning. Theoretische Informatik – kurz gefasst. Springer, 2008. 5. Auflage,
ISBN 978-3-8274-1824-1.
Version 17, 18. Dezember 2014
29
Document
Kategorie
Seele and Geist
Seitenansichten
13
Dateigröße
286 KB
Tags
1/--Seiten
melden