Lösungen zum Aufgabenblatt 10
Formale Sprachen und Automaten
Universität München, CIS, WS 2015/16
Hans Leiß
Ausgabe: Do 14.1.2016
Abgabe: Di 21.1.2016
Aufgabe 10.1 Sei G die Grammatik
S → ABC
A → a|ǫ
B → b|ǫ
C → c|ǫ
Berechne die zu G äquivalenten Grammatiken G1 und G2 wie folgt:
(a) G1 entstehe aus G, indem zuerst die Löschregeln beseitigt werden und dann die entstandene
Grammatik in Binärform gebracht wird.
(3 Punkte)
(b) G2 entstehe aus G, indem zuerst G in Binärform gebracht wird und dann aus der entstandenen Grammatik die Löschregeln beseitigt werden.
(3 Punkte)
P
Für eine Grammatik G = (Σ, N, S, P ) sei |G| := { |Aα| | (A → α) ∈ P }, wobei |α| die Länge
von α ∈ (N ∪ Σ)∗ ist. Vergleiche |G1 | und |G2 | mit |G|.
(2 Punkte)
Lösung von Aufgabe 10.1
(a) Man sieht leicht, daß jede der 4 Komponentensprachen
durch Berechnung der Grammatik G≥1 klar wird:
≥1
S
S ≥ ABC
≥1
A ≥ a+1
A
7→
G≥1 =
G=
≥1
B
≥
b
+
1
B
≥1
C ≥ c+1
C
das leere Wort enthält, was auch
≥
≥
≥
≥
Die kleinste Lösung von G≥1 ist (1, 1, 1, 1) = ({ǫ}, . . . , {ǫ}).
1
A≥1 B ≥1 C ≥1
(a + 1)≥1
= 1
(b + 1)≥1
= 1
(c + 1)≥1
= 1.
Daher ergibt die
−1
S
−1
G =
A−1
B −1
−1
C
Beseitigung der Löschregeln aus G:
≥
=
=
=
=
≥
≥
≥
(ABC)−1
A−1 (BC)−1 + A≥1 (BC)−1 + A−1 (BC)≥1
A−1 (BC)−1 + (BC)−1 + A−1
A−1 (BC)−1 + (B −1 C −1 + B −1 + C −1 ) + A−1
A−1 B −1 C −1 + A−1 B −1 + A−1 C −1 + B −1 C −1 + B −1 + C −1 + A−1
(a + 1)−1 = a
(b + 1)−1 = b
(c + 1)−1 = c
Um diese Grammatik in Binärform zu bringen, muß man noch die Regel S −1 → A−1 B −1 C −1
durch die Regeln S −1 → A−1 D und D → B −1 C −1 ersetzen.
(b) Bringt man zuerst G in Binärform, so erhält
S
A
B
G̃ =
C
D
Beseitigt man hierin die Löschregeln,
−1
S
A−1
B −1
G̃−1 =
C −1
−1
D
man
≥
≥
≥
≥
≥
AD
a+1
b+1
c+1
BC .
so erhält man
A−1 D−1 + A−1 + D−1
a
b
c
B −1 C −1 + B −1 + C −1 .
≥
≥
≥
≥
≥
Man erhält also eine kleinere Grammatik, da das Ausmultiplizieren“ mit D−1 unterbleibt.
”
(c) Die Grammatikgrößen sind
|G| = |SABC| + |Aa| + |A| + |Bb| + |B| + |Cc| + |C| = 4 + 9 = 13,
|G1 | = |S −1 A−1 D| + |DB −1 C −1 | + |S −1 A−1 B −1 | + . . . + |S −1 A−1 | + 6 = 21 + 6 = 27,
|G2 | = |S −1 A−1 D−1 | + |S −1 A−1 | + |S −1 D−1 | + 6
+ |D−1 B −1 C −1 | + |D−1 B −1 | + |D−1 C −1 | = 14 + 6 = 20.
Im allgemeinen, wenn die Regeln von der Form S ≥ A1 · · · An mit Ai ≥ a + 1 wären, wird
|G1 | von der Größenordnung 2|G| (da jede der 2n = O(2|G| ) Teilmengen von A1 , . . . , An
eine neue Regel liefert), aber |G2 | nur von der Größenordnung |G| sein (da nur jedes der
n Suffixe von A1 · · · An eine neue (binäre) Regel liefert).
Aufgabe 10.2 Die Beseitigung der Kettenregeln einer kontextfreien Grammatik G der Größe
|G| (Definition: siehe die vorige Aufgabe) kann zu einer Grammatik G′ der Größe |G|2 führen.
Können Sie ein Beispiel für ein G finden, wo das der Fall ist?
2
Tip: Was wird bei der Elimination einer Kettenregel A → B (bzw. eines variablen Summanden
in einer Ungleichung A ≥ . . . + B + . . .) gemacht, und wie sorgt man dafür, daß die entstehende
Grammatik dadurch möglichst viel größer wird?
Aufgabe 10.3 Sei t = a1 · · · an ∈ Σ+ ein Text über dem Alphabet Σ. Ein Vorkommen (Token)
von v ∈ Σ∗ in t ist ein Tripel (i, v, j) mit 0 ≤ i ≤ j ≤ n und v = ai+1 · · · aj . Sei
T (t) := (P(Tok (t)), +, ·, ∗ , 0, 1),
die (stetige) Kleene-Algebra aller Tokenmengen von t, mit
0 := ∅,
1 := { (i, ǫ, i) | 0 ≤ i ≤ n },
V +U
V ·U
V∗
:= V ∪ U,
:= { (i, vu, j) | Es gibt (i, v, k) ∈ V und (k ′ , u, j) ∈ U mit k = k ′ }
[
:=
{V n | n ∈ N}
mit V 0 := 1, V n+1 := V n · V . Die Bedeutung von a ∈ Σ in T (t) soll natürlich die Menge der
Vorkommen von a in t sein, also
aT (t) := { (i, a, i + 1) | a = ai+1 }.
Nach dem Fixpunktsatz hat jede kontextfreie Grammatik in jeder stetigen Kleene-Algebra
(K, +, ·, ∗ , 0, 1) mit Elementen zur Interpretation der Terminalsymbole eine Bedeutung, eben
das kleinste Tupel, das das Ungleichungssystem der Grammatik löst.
Sei G die kontextfreie Grammatik
≥ e|p|d nS
N
S ≥ rN V
(1)
≥ v
V
über dem Alphabet Σ := {d , n, e, r, p, v} für: Determinator, Nomen, Eigenname, Relativpronomen,
Personalpronomen, transitives Verb.
Da N von S und S von N abhängt, braucht die Fixpunktberechnung in P(Σ∗ ) unendlich viele
Stadien. G hat nach dem Fixpunktsatz in jedem P(Tok (t)) = T (t) mit t ∈ Σ+ eine Bedeutung,
die kleinste Lösung von (1). Da T (t) endlich ist, erreicht man sie schon nach endlich vielen
Stadien der Fixpunktberechnung. Führe die Berechnung des Fixpunkts für den Text
t := p v d n r d n r p v v
durch. (Ein Satz der Form t ist z.B. Er kennt die Frau, die das Buch, das er liest, schrieb.“)
”
Lösung von Aufgabe 10.3
Die Positionen im Text werden durch
t := 0 p
1
v
2
d
3
n
4
r
5
3
d
6
n
7
r
8
p
9
v
10
v 11
angedeutet. Die Bedeutung der Terminale in T := T (t) sind die Mengen ihrer Vorkommen:
eT
= ∅,
d
T
= {(2, d, 3), (5, d, 6)},
n
T
= {(3, n, 4), (6, n, 7)},
r
T
= {(4, r, 5), (7, r, 8)},
p
T
= {(0, p, 1), (8, p, 9)},
v
T
= {(1, v, 2), (9, v, 10), (10, v, 11)}.
Die rechten Seiten der Grammatik schreibe ich als reguläre Ausdrücke, also
N
= p+d ·n·S
S = r·N ·V
V
= v
4
Die Stadienberechnung ergibt:
N0 := ∅
S0 := ∅
V0 := ∅
N1 := pT ∪ dT · nT · S0 = pT
S1 = rT · N0 · V0 = ∅
V1 = v T
N2 := pT ∪ dT · nT · S1 = pT = N1
S2 = rT · N1 · V1 = rT · pT · v T = {(7, rpv, 10)}
V2 = v T = V1
N3 := pT ∪ dT · nT · S2 = pT ∪ {(5, dnrpv, 10)}
S3 = rT · N2 · V2 = rT · pT · v T = S2
V3 = v T = V2
N4 := pT ∪ dT · nT · S3 = N3
S4 = rT · N3 · V3
= rT · (pT ∪ {(5, dnrpv, 10)}) · v T
= S3 ∪ rT · {(5, dnrpv, 10)} · v T
= {(7, rpv, 10), (4, rdnrpvv, 11)}
V4 = v T = V3
N5 :=
=
S5 =
V5 =
pT
pT
rT
vT
∪ dT · nT · S4
∪ {(5, dnrpv, 10), (2, dnrdnrpvv, 11)}
· N4 · V4 = S4
= V3
N6 := pT ∪ dT · nT · S5 = N5
S6 = rT · N5 · V5 = rT · N5 · v T
= r T · pT · v T
∪ rT · {(5, dnrpv, 10), (2, dnrdnrpvv, 11)} · v T
= {(7, rpv, 10)} ∪ {(4, rdnrpvv, 11)}
= S5
V6 = v T = V5
Damit ist der kleinste Fixpunkt erreicht, da im Stadium 6 alle Komponenten dieselben Mengen
sind wie im Stadium 5.
5
© Copyright 2024 ExpyDoc
