close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Aktueller Speiseplan als PDF zum

EinbettenHerunterladen
F ORMALE S YSTEME
— Wintersemester 2014/15 —
Formelsammlung
Version 08
Kirstin Peters
18. November 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
Mathematische Grundlagen
1.1 Mengen . . . . . . . . . . . .
1.2 Relationen . . . . . . . . . . .
1.3 Ordnungen und Äquivalenzen
1.4 Abbildungen und Kardinalität
.
.
.
.
1
1
3
5
7
2
Formale Sprachen
2.1 Wörter und Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Reguläre Sprachen (Typ 3) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 Kontextfreie Sprachen (Typ 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
10
12
19
3
Aussagenlogik
22
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Literatur
Version 08, 18. November 2014
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
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 08, 18. November 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 08, 18. November 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
P(A) = { B | B ⊆ A }
def
Potenzmenge von A.
Satz 1.1.12. Sei A eine beliebige Menge. Dann gilt:
#(P(A)) =
1.2
2#(A)
∞
, falls #(A) = ∞
, falls #(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 08, 18. November 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 08, 18. November 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 08, 18. November 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 08, 18. November 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 08, 18. November 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 08, 18. November 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(P(A)) .
Version 08, 18. November 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 08, 18. November 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 08, 18. November 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 08, 18. November 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 × (Σ ∪ { ε }) → P(Q) 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 08, 18. November 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 × Σ → P(Q) statt δ : Q × (Σ ∪ { ε }) → P(Q).
Definition 2.2.15 (Berechnungen). Sei M = (Q, Σ, δ, S, F) ein ε-NFA.
Wir erweitern δ auf δ : P(Q) × Σ∗ → P(Q) 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 08, 18. November 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:
QD = P(Q)
def
δD (X, a) =
q∈X δ(q, a)
def
def
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 08, 18. November 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 Abbildung L : E → P(Σ∗ ) 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 08, 18. November 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 08, 18. November 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 08, 18. November 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 08, 18. November 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 08, 18. November 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 .
Version 08, 18. November 2014
21
Formale Systeme
3
Aussagenlogik
Version 08, 18. November 2014
22
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 08, 18. November 2014
23
Document
Kategorie
Seele and Geist
Seitenansichten
12
Dateigröße
252 KB
Tags
1/--Seiten
melden