Teil V
Weiterführende Themen, Teil 1:
Kontextsensitive Sprachen
und die Chomsky-Hierarchie
Zwei Sorten von Grammatiken
Kontextsensitive Grammatik (CSG)
(Σ, V, P, S), Regeln der Form
αAβ → αγβ
α, β ∈ (Σ ∪ V )∗ , A ∈ V , γ ∈ (Σ ∪ V )+ .
Wenn S nie auf einer rechten
Seite einer Regel vorkommt,
erlauben wir auch S → ε.
Jenseits von CFL
Kontextsensitive Sprachen
1 / 11
Zwei Sorten von Grammatiken
Kontextsensitive Grammatik (CSG)
(Σ, V, P, S), Regeln der Form
kontextsensitive Sprache:
wird von CSG erzeugt.
αAβ → αγβ
α, β ∈ (Σ ∪ V )∗ , A ∈ V , γ ∈ (Σ ∪ V )+ .
Wenn S nie auf einer rechten
Seite einer Regel vorkommt,
erlauben wir auch S → ε.
Jenseits von CFL
Kontextsensitive Sprachen
1 / 11
Zwei Sorten von Grammatiken
Kontextsensitive Grammatik (CSG)
(Σ, V, P, S), Regeln der Form
kontextsensitive Sprache:
wird von CSG erzeugt.
αAβ → αγβ
CSL: Klasse der
kontextsensitiven
Sprachen.
α, β ∈ (Σ ∪ V )∗ , A ∈ V , γ ∈ (Σ ∪ V )+ .
Wenn S nie auf einer rechten
Seite einer Regel vorkommt,
erlauben wir auch S → ε.
Jenseits von CFL
Kontextsensitive Sprachen
1 / 11
Zwei Sorten von Grammatiken
Kontextsensitive Grammatik (CSG)
(Σ, V, P, S), Regeln der Form
kontextsensitive Sprache:
wird von CSG erzeugt.
αAβ → αγβ
CSL: Klasse der
kontextsensitiven
Sprachen.
α, β ∈ (Σ ∪ V )∗ , A ∈ V , γ ∈ (Σ ∪ V )+ .
Monotone Grammatik
(Σ, V, P, S), Regeln der Form
α→β
Wenn S nie auf einer rechten
Seite einer Regel vorkommt,
erlauben wir auch S → ε.
mit α, β ∈ (Σ ∪ V )∗ , |α| ≤ |β|.
Jenseits von CFL
Kontextsensitive Sprachen
1 / 11
Äquivalenz der Grammatiktypen
Von monotoner Grammatik zu CSG
1
Stelle sicher, dass Regeln die folgende Form haben:
1
2
Jenseits von CFL
α → β, mit α, β ∈ V + , oder
A → a, mit A ∈ V , a ∈ Σ.
Kontextsensitive Sprachen
2 / 11
Äquivalenz der Grammatiktypen
Von monotoner Grammatik zu CSG
1
Stelle sicher, dass Regeln die folgende Form haben:
1
2
2
α → β, mit α, β ∈ V + , oder
A → a, mit A ∈ V , a ∈ Σ.
Zerlege Regeln α → β mit |α| ≥ 2.
Jenseits von CFL
Kontextsensitive Sprachen
2 / 11
Äquivalenz der Grammatiktypen
Von monotoner Grammatik zu CSG
1
Stelle sicher, dass Regeln die folgende Form haben:
1
2
2
α → β, mit α, β ∈ V + , oder
A → a, mit A ∈ V , a ∈ Σ.
Zerlege Regeln α → β mit |α| ≥ 2.
Diese haben die Form
A1 · · · Am → B1 · · · Bn
mit m, n ∈ N>0 , 2 ≤ m ≤ n
Jenseits von CFL
Kontextsensitive Sprachen
2 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
X1 A2 · · · Am → X1 X2 A3 · · · Am ,
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
X1 A2 · · · Am → X1 X2 A3 · · · Am ,
..
.
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
X1 A2 · · · Am → X1 X2 A3 · · · Am ,
..
.
X1 X2 · · · Xm−1 Am → X1 X2 · · · Xm Bm+1 · · · Bn ,
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
X1 A2 · · · Am → X1 X2 A3 · · · Am ,
..
.
X1 X2 · · · Xm−1 Am → X1 X2 · · · Xm Bm+1 · · · Bn ,
X1 X2 · · · Xm Bm+1 · · · Bn → B1 X2 · · · Xm Bm+1 · · · Bn ,
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
X1 A2 · · · Am → X1 X2 A3 · · · Am ,
..
.
X1 X2 · · · Xm−1 Am → X1 X2 · · · Xm Bm+1 · · · Bn ,
X1 X2 · · · Xm Bm+1 · · · Bn → B1 X2 · · · Xm Bm+1 · · · Bn ,
..
.
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Zerlegen von Regeln
Zu zerlegende Regel
A1 · · · Am → B 1 · · · B n
mit m, n ∈ N>0 , 2 ≤ m ≤ n.
A1 A2 · · · Am → X1 A2 · · · Am ,
X1 A2 · · · Am → X1 X2 A3 · · · Am ,
..
.
X1 X2 · · · Xm−1 Am → X1 X2 · · · Xm Bm+1 · · · Bn ,
X1 X2 · · · Xm Bm+1 · · · Bn → B1 X2 · · · Xm Bm+1 · · · Bn ,
..
.
B1 · · · Bm−1 Xm Bm+1 · · · Bn → B1 · · · Bn ,
Jenseits von CFL
Kontextsensitive Sprachen
3 / 11
Beispiel 1
G := (Σ, V, P, S),
Σ := {a, b, c},
V := {S, A, B, C},
P := {S → SABC, S → ABC}
∪ XY → Y X | X, Y ∈ {A, B, C}
∪ {A → a, B → b, C → c}.
Jenseits von CFL
Kontextsensitive Sprachen
4 / 11
Beispiel 2
G := (Σ, V, P, S), Σ := {a, b, c}, V := {S, B}
P := {S → aSBc,
S → abc,
Jenseits von CFL
cB → Bc,
bB → bb}.
Kontextsensitive Sprachen
5 / 11
Beispiel 3
Sei Σ ein Alphabet.
G := (Σ, V, P, S),
V := {S} ∪ {La , Ra , Xa | a ∈ Σ},
P := {S → aSXa | a ∈ Σ}
∪ {S → La Ra | a ∈ Σ}
∪ {Ra Xb → Xb Ra | a, b ∈ Σ}
∪ {Ra → a | a ∈ Σ}
∪ {La Xb → La Rb | a, b ∈ Σ}
∪ {La → a | a ∈ Σ}.
Jenseits von CFL
Kontextsensitive Sprachen
6 / 11
Zwei Beobachtungen zu CSL
Satz
CFL ⊂ CSL
Jenseits von CFL
Kontextsensitive Sprachen
7 / 11
Zwei Beobachtungen zu CSL
Satz
CFL ⊂ CSL
Satz
Das Wortproblem für monotone
Grammatiken ist entscheidbar.
Jenseits von CFL
Kontextsensitive Sprachen
7 / 11
Ein Maschinenmodell für CSL
Eingabeband
w
Kontrolle
Arbeitsband
Linear beschränkte Turingmaschine (LBA)
Eingabeband (nur Lesen, beide Richtungen)
nichtdeterministische endliche Kontrolle,
Arbeitsband
(Lesen und Schreiben, beide Richtungen)
Jenseits von CFL
Kontextsensitive Sprachen
8 / 11
LBAs und CSL
Satz
Eine Sprache L ist genau dann kontextsensitiv,
wenn Sie von einem LBA akzeptiert wird.
Jenseits von CFL
Kontextsensitive Sprachen
9 / 11
LBAs und CSL
Satz
Eine Sprache L ist genau dann kontextsensitiv,
wenn Sie von einem LBA akzeptiert wird.
Idee ⇒
simuliere monotone
Grammatik in LBA
möglich, da nur Satzformen
beschränkter Länge
betrachtet werden müssen
Jenseits von CFL
Kontextsensitive Sprachen
9 / 11
LBAs und CSL
Satz
Eine Sprache L ist genau dann kontextsensitiv,
wenn Sie von einem LBA akzeptiert wird.
Idee ⇒
Idee ⇐
simuliere monotone
Grammatik in LBA
simuliere LBA in monotoner
Grammatik
möglich, da nur Satzformen
beschränkter Länge
betrachtet werden müssen
Satzform entspricht
Arbeitsband
Jenseits von CFL
Kontextsensitive Sprachen
9 / 11
Allgemeine Grammatiken
Phrasenstrukturgrammatik (PSG)
G := (Σ, V, P, S)
Regeln α → β mit α, β ∈ (Σ ∪ V )∗
Jenseits von CFL
Die Chomsky-Hierarchie
10 / 11
Allgemeine Grammatiken
Phrasenstrukturgrammatik (PSG)
G := (Σ, V, P, S)
Regeln α → β mit α, β ∈ (Σ ∪ V )∗
Satz
Sei Σ, L ⊆ Σ∗ . Die folgenden Aussagen sind äquivalent:
1
Es existiert eine Phrasenstrukturgrammatik G mit L(G) = L.
2
Es existiert eine Turingmaschine M mit L(M ) = L.
3
Die Sprache L ist rekursiv aufzählbar.
Jenseits von CFL
Die Chomsky-Hierarchie
10 / 11
Allgemeine Grammatiken
Phrasenstrukturgrammatik (PSG)
G := (Σ, V, P, S)
Regeln α → β mit α, β ∈ (Σ ∪ V )∗
RE: Klasse der rekursiv
aufzählbaren Sprachen.
Satz
Sei Σ, L ⊆ Σ∗ . Die folgenden Aussagen sind äquivalent:
1
Es existiert eine Phrasenstrukturgrammatik G mit L(G) = L.
2
Es existiert eine Turingmaschine M mit L(M ) = L.
3
Die Sprache L ist rekursiv aufzählbar.
Jenseits von CFL
Die Chomsky-Hierarchie
10 / 11
Die Chomksky-Hierarchie
Satz
REG ⊂ CFL ⊂ CSL ⊂ RE
Jenseits von CFL
Die Chomsky-Hierarchie
11 / 11
Die Chomksky-Hierarchie
Satz
REG ⊂ CFL ⊂ CSL ⊂ RE
Grammatik
Typ 0
PSG
Typ 1
CSG
Typ 2
CFG
Typ 3
reg. G.
Jenseits von CFL
Automatenmodell
Turingmaschine
Sprachklasse
RE
LBA
CSL
PDA
CFL
endlicher Automat
REG
Die Chomsky-Hierarchie
11 / 11
© Copyright 2024 ExpyDoc
