Die Länge von wachsenden Grammatiken, die aus quasi wachsenden erzeugt werden

Studienarbeit

Gundula Niemann

Institut für Informatik

Julius-Maximilians-Universität Würzburg

Themenstellung und Betreuung:

Gerhard Buntrock Institut für Informatik, LS IV

Julius-Maximilians-Universität Würzburg

Dezember 1992

Inhaltsverzeichnis

1 Einführung 3 2 Eine Normalform für GCSG und die Länge einer normalisierten Grammatik 6 3 Abschlußeigenschaften von GCSL 9 4 Zu Grammatiken gehörende Ableitungsgraphen 10

4.1 Definitionen und Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 Eigenschaften von autonomen Teilgraphen . . . . . . . . . . . . . . . . . . . . . . 12

5 Der Abschluß von GCSL unter inversen Homomorphismen 15 6 Die Länge der ”invertierten“ Grammatik 20 7 Die Länge einer aus einer QGG erzeugten GCSG 22 Literaturverzeichnis 24

Vorwort

Wenn man Klassen von Grammatiken und die Klassen der von ihnen erzeugten Sprachen betrachtet und nach Beziehungen zwischen diesen forscht und es einem vielleicht gelingt, eine Inklusion oder sogar eine Gleichheit durch Überführung einer Grammatik in eine andere von einer anderen Klasse zu zeigen, fragt man sich manchmal, wie stark eine Grammatik bei einer solchen Behandlung eigentlich anwachsen kann.

Genau das soll hier einmal im Falle zweier recht neuer Klassen von Grammatiken untersucht werden. Es geht um quasi wachsende und um wachsend kontextsensitive Grammatiken. Wachsend kontextsensitive Grammatiken sind solche mit wachsenden Regeln, d.h. die rechte Seite ist länger als die linke, und quasi wachsende Grammatiken sind solche, für die es möglich ist, durch eine Funktion alle Terminale und Nichtterminale so zu gewichten (und durch natürliche Erweiterung auch Zeichenketten), daß für jede Regel das Gewicht auf der rechten Seite größer ist als auf der linken. Gerhard Buntrock und Krzysztof Lorys fanden heraus [BL92], daß beide Klassen von Grammatiken dieselbe Sprachklasse beschreiben und daß diese Klasse GCSL (growing context sensitive languages) außerdem gewisse Abschlußeigenschaften besitzt (sie bildet sogar eine AFL , abstract family of languages, s.[GGH69]). Sie erkannten dies in umgekehrter Reihenfolge. Denn es zeigte sich, daß die Abgeschlossenheit von GCSL unter inversen Homomorphismen der Schlüssel zum Beweis der Tatsache ist, daß sich zu jeder quasi wachsenden Grammatik eine wachsend kontextsensitive finden läßt, die dieselbe Sprache erzeugt.

Wie groß diese Grammatik im Verhältnis zur alten höchstens ist, ob polynomiell, exponentiell oder gar doppelt exponentiell, ist Gegenstand dieser Arbeit.

Da diese Untersuchung sich notwendigerweise an die Konstruktion in [BL92] anlehnt und die Darstellung dort etwas knapp ist, soll sie in dieser Arbeit nochmals und etwas ausführlicher dargelegt werden.

Auf den ersten Blick möchte man annehmen, daß dieses Anwachsen exponentiell ist, und man wird diese Annahme in vielen Fällen bestätigt finden.

1 Einführung

Es wird angenommen, daß der Leser vertraut ist mit den Grundlagen der Theorie über Formale Sprachen. Es sollen hier nur für die Arbeit grundlegende Schreibweisen in Erinnerung gerufen werden (vgl. [Schö92]).

Eine Grammatik ist ein Quadrupel ⟨N, Σ, S, P ⟩ mit endlichen, disjunkten Alphabeten N und Σ, einem Startsymbol S ∈ N und einer endlichen Menge von Regeln (Produktionen) der Form α → β mit α, β ∈ (Σ ∪ N)^{∗}, α ≠ ε, wobei ε das leere Wort bezeichnet. Für eine endliche Menge M bezeichne |M| die Anzahl der Elemente in M, und für eine Zeichenkette z bezeichne |z| die Länge von z. Grammatiken mit |α| ≤ |β| oder (α → β) = (S → ε) heißen kontextsensitiv, falls gilt: Wenn (S → ε) ∈ P ist, so taucht S in keiner Regel auf der rechten Seite auf.^{1} Solche kontextsensitiven Grammatiken, für die zusätzlich α ∈ N gilt, heißen kontextfrei. Die entsprechenden Sprachklassen werden mit CSL bzw. CFL bezeichnet.

Indem man obige Ungleichung durch eine strikte ersetzt, kommt man zu wachsend kontextsensitiven Grammatiken.

Definition 1.1 : Eine kontextsensitive Grammatik G = ⟨N, T, S, P ⟩ heißt wachsend ^{2}, wenn gilt:

• für jedes (α → β) ∈ P mit α, β ∈ (Σ ∪ N)^{∗} gilt: |α| < |β| ∨ α = S, β ∈ N ∪ Σ ∪ {ε}

• falls (S → ε) ∈ P, so taucht S in keiner Regel auf der rechten Seite auf

Die Menge der wachsend kontextsensitiven Grammatiken bezeichnen wir mit GCSG und die Klasse der durch sie erzeugten Sprachen mit GCSL .

Die Definition von wachsend kontextfreien Grammatiken ergibt wenig Sinn, da dies nicht zu einer neuen Sprachklasse führt, wie aus untenstehender Überlegung leicht klar wird. Aber führt obige Definition wirklich zu einer neuen Sprachklasse, und wo ist diese einzuordnen?

Es leuchtet sofort ein, daß eine kontextfreie Grammatik auch eine kontextsensitive Grammatik ist. Ebenso leuchtet sofort ein, daß eine wachsend kontextsensitive Grammatik ebenfalls eine kontextsensitive ist.

Sei nun eine kontextfreie Grammatik G = ⟨N, Σ, S, P ⟩ gegeben. Wir konstruieren eine äquivalente wachsend kontextsensitive Grammatik G′.

Sei (A → β) ∈ P eine nicht wachsende Regel, also β ∈ (Σ ∪ N). Für jede Regel (A′ → β′) ∈ P, in der A in β′ vorkommt, also β′ = uAv, u, v ∈ (Σ ∪ N)^{∗}, füge man die Regel A′ → uβv zu P hinzu. Dann wird die Regel A → β aus P gestrichen.

Dieser Vorgang wird für jede nicht wachsende Regel aus P wiederholt. So wird eine Regelmenge P′ konstruiert, in der nur wachsende Regeln vorkommen.

Man überlegt sich leicht, daß G′ = ⟨N, Σ, S, P′⟩ nur wachsende Regeln hat und außerdem L(G′) = L(G) gilt.

Also ist:

CFL ⊆ GCSL ⊆ CSL Bemerkung: In der gleichen Weise wie oben kann man sich überlegen, daß die Forderung

1Üblicherweise fordert man hier, daß sämtliche Regeln von der Form wXz → wyz mit w, x, y, z ∈ (Σ ∪ N)^{∗}, X ∈ N, y ≠ ε sind. Beide Charakterisierungen führen aber zur selben Sprachklasse.

2engl.: growing

∀(α → β) ∈ P : |α| < |β| ∨ α ∈ N, β ∈ Σ ∨ (α → β) = (S → ε)

statt Punkt 1 in Definition 1.1 zur Charakterisierung für wachsend kontextsensitive Sprachen bereits ausreicht. (siehe [FS91], Übungsaufgabe 9.2) Dies wird im folgenden Beispiel verwendet.

Beispiel 1.1 : L = {w ∈ {a, b, c}^{∗} | w = a^{n}b^{n}c^{n}, n ∈ IN} (aus [DW86]) L ∈ GCSL , L ∉ CFL Denn: G = ⟨{S, A, B, C, Z, 0, 1, 0′, 0′′, ℵ}, {a, b, c}, S, P ⟩ mit

P : S → a^{m}b^{m}c^{m}  für m ≤ 5  1A → AAA0′
S → ZAAABBBCCCℵ  0′B → BBB0′′
Z → Zα α ∈ {0, 1} 0′′C → CCC0
ZA → AA0  0CCℵ → CCCCℵ
ZA → AAA0′  0CCCℵ → CCCCCC
0X → XX0 X ∈ {A, B, C} A → a
0′A → AA0′  B → b
0′′B → BB0′′  C → c

ist eine Grammatik mit L(G) = L, und man überlegt sich leicht, daß es eine äquivalente wachsend kontextsensitive Grammatik gibt (s.o.). Aus dem Pumping Lemma für kontextfreie Sprachen folgt: L ∉ CFL .

Beispiel 1.2 : L = {ww | w ∈ {a, b}^{∗}} L ∈ CSL , L ∉ GCSL Denn: G = ⟨{S, A, B, C, D, E, F, Z, ℵ}, {a, b}, S, P ⟩ mit

P : S → aa  Z → aaC
S → bb  Z → abD
S → Zℵ  Z → baE
Z → ZaA  Z → bbF
Z → ZbB  Cℵ → aa
Xa → aX  X ∈ {A, B, C, D, E, F }  Dℵ → ab
Xb → bX  X ∈ {A, B, C, D, E, F }  Eℵ → ba
Aℵ → ℵa  F ℵ → bb
Bℵ → ℵb

ist eine kontextsensitive Grammatik mit L(G) = L. Nun gilt aber:

Wird L von einem 1–auxPDA (Einweg–Kellerautomat mit zusätzlichem Arbeitsband, Schreibweise nach [WW86]) erkannt, so benötigt dieser wenigstens linear viel Platz auf dem Hilfsband (siehe [Lau88]).

und man kann aus dem Beweis zu dem Satz: ”Jede Sprache aus GCSL ist in polynomieller Zeit durch eine Turingmaschine erkennbar“ aus [DW86] folgern (mit der Bemerkung im letzten Abschnitt):

Jede Sprache aus GCSL kann von einem 1–auxPDA mit logarithmischem Platzbearf auf dem Hilfsband erkannt werden.

Daraus folgt sofort: L ∉ GCSL .

Also gilt

CFL ⊂ GCSL ⊂ CSL

d.h. beide Inklusionen sind echt.

Definition 1.2 : Eine Grammatik G = ⟨N, Σ, S, P ⟩ ist quasi-wachsend, falls es eine Funktion f : (N ∪ Σ) → IN gibt, so daß gilt:

• für jedes (α → β) ∈ P gilt:

f(α) < f(β) ∨ α = S, β ∈ N ∪ Σ ∪ {ε}

wobei f(a_{1}a_{2} … a_{n}) = ∑_{i=1}^{n} f(a_{i}) für a_{1} … a_{n} ∈ (Σ ∪ N)^{∗}.

• falls (S → ε) ∈ P, so taucht S in keiner Regel auf der rechten Seite auf.

Die Menge aller quasi-wachsenden Grammatiken wird mit QGG bezeichnet.

Beispiel 1.3 : L = {w ∈ {a, b, c}^{∗} | w = a^{n}b^{n}c^{n}, n ∈ IN} L ist erzeugbar durch eine quasi wachsende Grammatik Denn: G = ⟨{S, A, B, C, Z, 0, 1, 0′, 0′′, ℵ}, {a, b, c}, S, P ⟩ mit

P : S → abc  1A → AAA0′
S → ZABCℵ  0′B → BBB0′′
Z → Zα α ∈ {0, 1} 0′′C → CCC0
ZA → AA0  0Cℵ → CCℵ
ZA → AAA0′  0Cℵ → CC
0X → XX0 X ∈ {A, B, C} A → a
0′A → AA0′  B → b
0′′B → BB0′′  C → c

ist eine Grammatik mit L(G) = L, und mit der Funktion f: (Σ ∪ N) → IN mit:

\begin{aligned}f(Z) & = 1 & f(0′′) & = 1 & f(A) & = 3 & f(a) & = 4 \\ f(0) & = 1 & f(1) & = 1 & f(B) & = 3 & f(b) & = 4 \\ f(0′) & = 1 & f(ℵ) & = 1 & f(C) & = 3 & f(c) & = 4 \end{aligned}

folgt G ∈ QGG und damit die Behauptung. Diese Grammatik hat nur 19 Regeln, gegenüber 23 Regeln in Beispiel 1.1.

Bemerkung: Trivialerweise ist jede wachsend kontextsensitive Grammatik auch quasi wachsend, nämlich mit:

f: (Σ ∪ N) → IN, f(a) = 1 ∀a ∈ (Σ ∪ N)

Die ”quasi–Umkehrung“, nämlich daß es zu jeder QGG eine GCSG gibt, die die gleiche Sprache erzeugt, ist weniger trivial und wird in Satz 7.1 gezeigt.

Dazu wird eine Normalform für GCSG gebraucht, welcher wir uns jetzt zuwenden.

2 Eine Normalform für GCSG und die Länge einer normalisierten Grammatik

Definition 2.1 : Wir nennen eine GCSG G = ⟨N, Σ, S, P ⟩ k–normal, falls alle Produktionen aus P eine der folgenden Formen haben:

1. S → β, wobei β ∈ Σ^{∗} und |β| ≤ k

2. S → β, wobei β ∈ (Σ ∪ N)^{k}

3. α → β, wobei α, β ∈ (Σ ∪ N)^{∗}, |α| = k und |β| = k + 1

Satz 2.1 : (über k–Normalisierung)

Zu jeder Sprache L ∈ GCSL gibt es ein k_{0} ∈ IN, so daß es zu jedem k ≥ k_{0} eine Grammatik G_{k} ∈ GCSG gibt, die k–normal ist und genau L erzeugt, also mit L(G_{k}) = L.

Beweis: Sei G = ⟨N, Σ, S, P ⟩ eine GCSG mit L(G) = L, o.B.d.A. tauche S in P nicht auf der rechten Seite einer Regel auf (ist durch Einführung eines neuen Startsymbols stets erreichbar). Wir setzen k_{0} := max {|α| : (α → β) ∈ P }.

Die Produktionsmenge P_{k} von G_{k} = ⟨N, Σ, S, P_{k}⟩ erzeugen wir in drei Schritten:

1. Normalisierung der Produktionen der Form S → β:

Für diese gilt eine der folgenden Eigenschaften:

(a) β ∈ Σ^{∗}, |β| ≤ k

(b) β ∈ (Σ ∪ N)^{k}

(c) β ∈ (Σ ∪ N)^{∗}, |β| > k oder

(d) β ∈ (Σ ∪ N)^{+}, |β| < k, β enthält Nichtterminale.

In den Fällen (a) und (b) ist nichts zu tun.

Im Falle (c) normalisiere nach 3.

Im Falle (d) wende auf alle Nichtterminale in β jede anwendbare Regel aus P einmal an. Die so entstandenen Regeln erfüllen wieder eine der Eigenschaften (a)–(d) und werden entsprechend behandelt. Da die Grammatik wachsend ist, bleibt irgendwann keine Regel mit der Eigenschaft (d) mehr übrig.

2. Normalisierung von α:

Jedes α → β ∈ P_{1} wird ersetzt durch α_{1}αα_{2} → α_{1}βα_{2} für alle α_{1}, α_{2} ∈ (Σ ∪ N \ {S})^{∗} mit |α_{1}αα_{2}| = k.

3. Normalisierung von β:

Jede Produktion a_{1}a_{2} … a_{k} → b_{1}b_{2} … b_{k+c} wird ersetzt durch Produktionen:

\begin{aligned}a_{1}a_{2} … a_{k} & → & b_{1}B_{2} … B_{k+1}, \\ B_{i}B_{i+1} … B_{k+i−1} & → & b_{i}B_{i+1} … B_{k+i} für i = 2, … c − 1, \\ B_{c} … B_{k+c−1} & → & b_{c} … b_{k+c} \end{aligned}

wobei B_{i} für i = 2, …, k + c − 1 neue Nichtterminale sind.

Daß G_{k} und G äquivalent sind, ist klar. ♣

Satz 2.2 : Die Anzahl der Regeln wächst bei der Normalisierung einer wachsend kontextsensitiven Grammatik G = ⟨N, Σ, S, P ⟩ nach Satz 2.1 höchstens quadratisch mit |P | und exponentiell mit k, ebenso die Anzahl der Nichtterminale.

Beweis: Abschätzung des Wachstums einer Grammatik G = ⟨N, Σ, S, P ⟩ bei Normalisierung: Sei q := |P \ {S → β}|, κ := min {|α| : (α → β) ∈ P, α ≠ S}.

• Bei der Normalisierung von Produktionen der Form S → β: Im schlimmsten Fall ist jede Regel S → β aus P rechts ”zu kurz“, also |P | − q viele. Das Verfahren muß dabei für jede dieser Regeln nicht häufiger als (k − |β|)–mal durchgeführt werden, wobei maximal an (|β| − κ) Stellen von β wenigstens eine Regel anwendbar ist. Also erhöht sich die Anzahl der Regeln der Form S → β höchstens auf

(|P | − q) · ∑_{i=1}^{k−|β|} (|β| + i − κ) · q für k ≥ 2

< (|P | − q) · (k − |β|) · |β| · q + (|P | − q) · ∑_{i=1}^{k−κ−1} q · i da κ > 0 und |β| ≥ κ + 1

= (|P | − q) · q · ((k − |β|) · |β| + \frac{(k − κ − 1)(k − κ)}{2})

≤ (|P | − q) · q · (\frac{k^{2}}{4} + \frac{(k − 2)(k − 1)}{2})  da (k − |β|) · |β| maximal für |β| = \frac{k}{2} und da κ ≥ 1

≤ \frac{|P |^{2}}{4} · (\frac{k^{2}}{4} + \frac{k^{2} − 3k + 2}{2})

≤ \frac{|P |^{2}}{4} · (\frac{k^{2}}{4} + \frac{k^{2}}{2} )

≤ \frac{1}{4}k^{2} · |P |^{2} für k ≥ 2

• Bei der Normalisierung von α:

Dann wächst die Anzahl der Regeln in P_{1} in diesem Schritt nicht mehr als auf höchstens

q · (|Σ ∪ N \ {S}|)^{k−κ} · (k − κ + 1) = q · (|Σ ∪ N| − 1)^{k} · k ≤ |P | · k · (|Σ ∪ N|)^{k}

an.

• Bei der Normalisierung von β:

Schlimmstenfalls sind nun alle Regeln rechts ”zu lang“, sei c das maximale c, um das eine solche Regel rechts ”zu lang“ ist. Sei q̃ die Anzahl der Regeln in P_{1} direkt vor dieser Normalisierung von β. Dann erhöht sich die Anzahl der Regeln also höchstens auf q̃ · c und die Anzahl der Nichtterminale höchstens auf |N| + q̃ · c.

• Insgesamt erhöht sich die Anzahl der Regeln also höchstens auf:

(|P | · k · |Σ ∪ N|^{k} + \frac{1}{2}k^{2} · |P |^{2}) · c

und die Anzahl der Nichtterminale höchstens auf

|N| + (|P | · k · |Σ ∪ N|^{k} + \frac{1}{2}k^{2} · |P |^{2}) · (c − 1)

Wegen |P | · k · |Σ ∪ N|^{k} + \frac{1}{2}k^{2} · |P |^{2} ≤ 2 · k^{2} · |P |^{2} · |Σ ∪ N|^{k} und k^{2} ≤ 3^{k} für alle k ∈ IN ist damit die Behauptung gezeigt. ♣ Beispiel 2.1 : Sei eine Familie von wachsend kontextsensitiven Grammatiken {G^{(p)} : p ∈ IN} gegeben durch: G^{(p)} = ⟨{S, A, B}, {a, b}, S, P^{(p)}⟩ mit

P^{(p)} : S → AB  B → BB
S → BA  B → BA
A → AA  B → AB
A → AB  A → aa
A → BA  B → bb
\begin{matrix}A → ABA^{i} \\ B → BAB^{i} \\ S → AB(AB)^{⌊ \frac{i}{2} ⌋}A^{i mod 2} \end{matrix} \} für i = 0, 1, 2, …, p

( Es ist L(G) = {w ∈ {a, b}^{∗} | |w| ≥ 4, ∃v ∈ {a, b}^{∗} : w = h(v)} mit einem Homomorphismus h: {a, b}^{∗} → {a, b}^{∗} mit h(a) = aa, h(b) = bb. ) Sei G_{k}^{(p)} = ⟨{S, A, B}, {a, b}, S, P_{k}^{(p)}⟩ für jedes k und jedes p die nach dem Beweis von Satz 2.1 zu G konstruierte k–normale Grammatik. Dann können wir für alle k ≥ 3 und alle p ∈ IN:

|P_{k}^{(p)}| ≥ \frac{1}{60} (|P^{(p)}| · k · (|Σ ∪ N| − 1)^{k} + \frac{1}{2}k^{2} · |P^{(p)}|^{2})

wie folgt zeigen:

• bei der Normalisierung der Regeln der Form S → β wächst die Anzahl solcher Regeln auf wenigstens

\frac{2 + p}{10 + 3p} · |P^{(p)}| · ∑_{i=1}^{k−2}(2 + i − 1) · \frac{3 + p}{10 + 3p} · |P^{(p)}|

• bei der Normalisierung von α wächst die Anzahl der Regeln der Form α → β auf

\frac{8 + 2p}{10 + 3p} · |P^{(p)}| · k · |Σ ∪ N \ \{S\}|^{k−1}

an.

• bei der Normalisierung von β kann die Anzahl der Regeln nochmals anwachsen (und zwar um ∑_{i=0}^{p} 3 · i Regeln, also kommen für p = 0 keine hinzu).

Man hat also wenigstens

\frac{2 + p}{10 + 3p} · |P^{(p)}| · ∑_{i=1}^{k−2}(2 + i − 1) · \frac{3 + p}{10 + 3p} · |P^{(p)}| + \frac{8 + 2p}{10 + 3p} · |P^{(p)}| · k · |Σ ∪ N \ \{S\}|^{k−1}

Regeln in P_{k}^{(p)}. Das sind mehr als:

\frac{1}{3} · \frac{2 + p}{4 + p} · |P^{(p)}| · (k − 2 + \frac{(k − 2)(k − 3)}{2}) · \frac{1}{3} · \frac{3 + p}{4 + p} · |P^{(p)}|

+\frac{2}{3} · \frac{4 + p}{4 + p} · |P^{(p)}| · k · \frac{1}{4} · (|Σ ∪ N| − 1)^{k}  durch Faktorisieren und wegen |Σ ∪ N| − 1 = 4

≥ \frac{1}{3} · \frac{2}{4} · \frac{1}{3} · \frac{3}{4} · |P^{(p)}|^{2} · \frac{(k − 2)(k − 1)}{2} + \frac{2}{3} · \frac{1}{4} · |P^{(p)}| · k · (|Σ ∪ N| − 1)^{k}

≥ \frac{2}{12} · \frac{3}{12} (\frac{1}{2}(k^{2} − 3k + 2) · |P^{(p)}|^{2} + |P^{(p)}| · k · (|Σ ∪ N| − 1)^{k})

= \frac{1}{24} (\frac{1}{2}(k^{2} − 3k + 2) · |P^{(p)}|^{2} + |P^{(p)}| · k · (|Σ ∪ N| − 1)^{k})

Wegen \frac{1}{2}(k^{2} − 3k + 2) ≥ \frac{1}{5}k^{2} für k ≥ 3 folgt daraus die Behauptung.

Das heißt, die Abschätzung aus Folgerung 2.2 ist in dem Sinne scharf, daß |P′| quadratisch von |P | und exponentiell von k abhängen kann.

3 Abschlußeigenschaften von GCSL

Die Erkenntnis, daß GCSL eine AFL bildet, darf hier nicht fehlen. (siehe [BL92])

Definition 3.1 : Eine abstrakte Sprachfamilie (AFL)^{3} ist eine Sprachfamilie^{4} abgeschlossen unter: Vereinigung, Konkatenation, Iteration, Durchschnittsbildung mit regulären Sprachen, ε–freie Homomorphismen und inverse Homomorphismen.

Lemma 3.1 : Sei F eine Sprachfamilie. Falls F ε–frei, abgeschlossen unter Konkatenation, ε–freien Homomorphismen und inversen Homomorphismen ist, dann ist F abgeschlossen unter Durchschnittsbildung mit regulären Sprachen.

zum Beweis siehe [GGH69].

Lemma 3.2 : Die Klasse GCSL ist abgeschlossen unter Vereinigung, Konkatenation, Iteration, Substitution und ε–freien Homomorphismen.

Beweis: Durch Standardmethoden unter Verwendung der Tatsache, daß es für jede Sprache L ∈ GCSL eine wachsend kontextsensitive Grammatik gibt, die L erzeugt und in deren Regeln Terminalsymbole nur auf der rechten Seite auftauchen. ♣

Zum Abschluß dieses Kapitels noch die Feststellung:

Satz 3.1 : Die Klasse GCSL bildet eine AFL .

Beweis: Aus den Lemmata 3.1 und 3.2 sowie Satz 5.3, den wir in Kap. 5 beweisen werden. ♣

3abstract family of languages

4eine Sprachfamilie ist eine Ansammlung (Kollektion) von Sprachen, die wenigstens eine nichtleere Sprache enthält

4 Zu Grammatiken gehörende Ableitungsgraphen

Wir wollen jetzt Eigenschaften von Ableitungen in wachsend kontextsensitiven Grammatiken näher untersuchen, und dazu sind gewisse graphische Darstellungen von Ableitungen ein sehr nützliches Hilfsmittel, nämlich planare azyklische Graphen (siehe [BL92]).

4.1 Definitionen und Beispiele

Definition 4.1 : Mit jeder Ableitung in G = ⟨N, Σ, S, P ⟩ assoziieren wir einen planaren azyklischen Graphen, genannt den Ableitungsgraphen. Die Knoten in einem solchen Graphen sind markiert mit den zugehörigen Symbolen und Regeln, die in der Ableitung verwendet werden. Die Markierung^{5} eines Knotens v bezeichenen wir mit l(v). Für eine Ableitung α_{1} ⟹_{G} α_{2} ⟹_{G} … ⟹_{G} α_{k} ist der Ableitungsgraph D_{k} = (V_{k}, E_{k}) induktiv definiert. In jedem Schritt entsprechen die Quellen von D_{i} dem α_{1}, und die Senken entsprechen α_{i}.

1. falls α_{1} = a_{1}a_{2} … a_{r}, dann D_{1} = ({v_{j} : j = 1, …, r und l(v_{j}) = a_{j}}, ∅)

2. falls α_{i−1} ⟹ α_{i} mit α_{i−1} = wαw′, α_{i} = wβw′ und α ⟹ β, also α_{i−1} = wαw′ ⟹ wβw′ = α_{i}, mit α = a_{1}a_{2} … a_{r}, β = b_{1}b_{2} … b_{s}, dann

• V_{i} = V_{i−1} ∪ {v^{i}, v_{1}^{i}, …, v_{s}^{i}}, wobei v^{i}, v_{1}^{i}, …, v_{s}^{i} neue Knoten sind, v^{i} ist markiert mit der Produktion (α → β) und l(v_{j}^{i}) = b_{j} für j = 1, …, s.

• E_{i} = E_{i−1} ∪ {(u_{j}, v^{i}) : j = 1, …, r} ∪ {(v^{i}, v_{j}^{i}) : j = 1, …, s}, wobei u_{1}, u_{2}, …, u_{r} ∈ V_{i−1} zu α gehören, also l(u_{j}) = a_{j} für j = 1, …, r.

Definition 4.2 : Unter einer Senkstelle s eines Teilgraphen F eines Ableitungsgraphen D verstehen wir einen Knoten s aus F, der innerhalb des Teilgraphen H weniger Ausgänge besitzt als in dem ursprünglichen Graphen D. Eine Teilmenge S ⊆ V von Knoten eines Graphen D = (V, E) heißt Senke, falls es in E keine Kante (v, u) gibt mit v ∈ S, u ∉ S. (Enthält S = {v} nur einen Knoten, so schreiben wir v statt {v}, und dies ist eine Senke im üblichen Sinne.)

Vgl. dazu die Definition von traps in markierten Petrinetzen (oder markierten Stellen- /Transitionsnetzen) z.B. in [Rei86], in Kap. 7.1 auf S. 115, oder (einfacher dargestellt) in [NLII84], in Kap. 7 auf S. 204.

Beispiel 4.1 : Sei G = ⟨{Z, A, B, C, 0, ℵ}, {a, b, c}, S, P ⟩ mit:

P : S → aabbcc  0CCℵ → CCCCℵ
S → ZAABBCCℵ  0CCCℵ → CCCCCC
Z → Z0  0BCCℵ → BBCCCC
ZA → AA0  A → a
0X → XX0 X ∈ {A, B, C} B → b
AB → A0B  C → c
BC → B0C

(L(G) = {a^{2^{i}}b^{2^{j}}c^{2^{k}} | i, j, k ∈ IN, 0 < i ≤ j ≤ k})

5engl.: label

Betrachte nun einen Ableitungsgraphen D zu 0A0ABBC ⟹^{∗}_{G} A^{5}BB0B^{3}0B^{6}0C^{4}0C^{3}0C0 und darin einen Teilgraphen F (fett gezeichnet) :

[figure: 1; 0A→AA0; 10; 0C→CC0; 11; AB→A0B; 15; 0A→AA0; 20; 0B→BB0; 16; 0B→BB0; 21; 0B→BB0; 18; 0C→CC0; 22; 0B→BB0; 23; 0C→CC0; 19; 0C→CC0; 13; BC→B0C; 14; 0C→CC0; 4; 0A→AA0; 6; 0C→CC0; 12; 0B→BB0; 17; 0B→BB0; 8; 0B→BB0; 9; 0B→BB0; 7; AB→A0B; 5; 0B→BB0; 2; 0A→AA0; 3; BC→B0C; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; 0; A; A; A; A; A; A; A; A; A; A; A; A; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; B; C; C; C; C; C; C; C; C; C; C; C; C; C; C; C]

Die Knoten 2, 3, 7, 8, 9, 12 und 17 sind Senkstellen des Teilgraphen F = (V_{F} , E_{F}), aber {2, 3, 7, 8, 9, 12, 17} ist keine Senke von F, da (2, 5) ∈ E_{F}. {17} ist eine Senke von F, {16, 20, 21} und {13, 17, 18, 22, 23} sind Senken von D.

Uns interessieren hier nur spezielle Teilgraphen eines Ableitungsgraphen, nämlich solche, die für z ⟹^{∗}_{G} u ein Anfangsstück eines möglichen Ableitungsweges beschreiben und dabei nur die veränderten Teilwörter von z und u betrachten (vgl. [BL92]).

Definition 4.3 : Sei D ein Ableitungsgraph, der zu z ⟹^{∗}_{G} u gehört. Wir sagen, ein Teilgraph F ⊆ D ist autonom, falls gilt:

1. aufgefaßt als ungerichteter Graph ist F zusammenhängend

2. alle Vorgänger von Knoten aus F gehören ebenfalls zu F

3. alle Senkstellen von F sind markiert mit Produktionen

Beispiel 4.2 : Der im obigen Beispiel 4.1 eingezeichnete Teilgraph F ist autonom.

Definition 4.4 : Sei v_{1}, …, v_{s} die Folge aller Quellen eines autonomen Teilgraphen F eines Ableitungsgraphen D und sei v′_{1}, …, v′_{s′} die Folge aller Nachfolger von Senkstellen aus F, welche nicht zu F gehören (man bedenke die natürliche Ordnung der Quellen und Senkstellen sowie deren Nachfolger durch die Planarität von F). Das Wort l(v_{1}) … l(v_{s}) nennen wir Basis von F und das Wort l(v′_{1}) … l(v′_{s′}) nennen wir Ableitung von F.

Es ist leicht zu sehen, daß die Basis ein Teilwort von z ist und daß D \ F ein Ableitungsgraph einer Ableitung z′ ⟹^{∗}_{G} u ist, wobei z′ aus z entsteht durch das Ersetzen der Basis von F durch die Ableitung von F.

Beispiel 4.3 : In Beispiel 4.1 ist 0ABBC die Basis und AAB^{6}0B00C die Ableitung des autonomen Teilgraphen F.

Definition 4.5 : Sei D wieder ein Ableitungsgraph zu einer Ableitung z ⟹^{∗}_{G} u in einer Grammatik G = ⟨N, Σ, S, P ⟩. Ein Produktionsknoten ist ein Knoten v mit l(v) ∈ P. Ist v ein Produktionsknoten, dann bezeichenen wir mit I(v) denjenigen Teilgraphen von D, der durch v und seine Vorgänger induziert wird. Als Größe eines autonomen Teilgraphen F ⊆ D bezeichnen wir die Anzahl der Produktionsknoten in F. Als Tiefe eines Knotens v aus D bezeichnen wir die maximale Anzahl von Produktionsknoten auf einem Weg von einem Basisknoten von D zum Knoten v.

Beispiel 4.4 : In Beispiel 4.1 ist der autonome Teilgraph F = I(v_{17}), die Größe von I(v_{17}) ist 8 und die Tiefe von v_{17} ist 6. Die Größe von I(v_{22}) ist 12, und die Tiefe von v_{13} ist 5. .

4.2 Eigenschaften von autonomen Teilgraphen

Aus den Definitionen 4.3 und 4.5 ergibt sich sofort:

• I(v) ist autonom ist für jedes v.

• die Vereinigung F̃ von autonomen Teilgraphen F und F′ eines Graphen G ist wieder autonom, falls F̃ betrachtet als ungerichteter Graph wieder zusammenhängend ist.

Die nun betrachteten Eigenschaften autonomer Teilgraphen von Ableitungsgraphen sind sehr nützlich beim Nachweis des Abschlusses von GCSL unter inversen Homomorphismen.

Satz 4.1 : Sei D ein Ableitungsgraph zu einer Ableitung in einer k–normalen wachsend kontextsensitiven Grammatik. Dann gilt: Für jeden Knoten v ∈ D hat der Teilgraph I(v) eine Basis einer Länge nicht größer als (2h − 1)k − 2(h − 1), wobei h die Tiefe von v ist.

Beweis: durch vollständige Induktion:

h = 1: Die Basis umfaßt offenbar k = (2 · 1 − 1)k − 2(1 − 1) Knoten

h → h + 1: Sei b_{h} die Länge der Basis B_{h} bei Tiefe h.

Falls F := I(v) einen Produktionsknoten enthält, dessen zugehörige Produktion von der Form S → β ist, läßt sich die Tiefe nicht (durch Heranziehen einer vorhergehenden Ableitungsebene) erhöhen, da laut Voraussetzung S nicht auf der rechten Seite einer Regel auftaucht. Also besitze jeder Produktionsknoten k Eingänge und k + 1 Ausgänge. Nun wird aus I(v) mit der Tiefe h ein maximaler Ableitungsgraph I(v) mit der Tiefe h + 1 gebildet, indem zu F eine Ebene von Ableitungsschritten in G hinzugenommen wird, die aus einer Satzform B_{h+1} die alte Bass B_{h} erzeugt. Die Basislänge b_{h} erhöht sich maximal, wenn nur einer der Ausgänge eines neuen Produktionsknotens zur alten Basis gehört.

Skizze:

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; alte Basis; I(v); neuer Produktionsknoten]

Das geht wegen der Planarität von F nur an höchstens zwei Stellen.

Die Hinzunahme einer dritten Produktion, die einen Knoten der alten Basis verwendet, erhöht die Anzahl der Basisknoten nicht mehr, wenn die Tiefe h + 1 beibehalten werden soll.

Im Maximalfall bleiben also von der alten Basis alle Knoten bis auf 2 erhalten, dafür kommen 2k Knoten hinzu.

⇒ b_{h+1} ≤ b_{h} − 2 + 2k

b_{h} ≤ (2h − 1)k − 2(h − 1) laut Induktionsvoraussetzung

\begin{aligned}⇒ b_{h+1} & ≤ (2h − 1)k − 2(h − 1) − 2 + 2k = (2h + 1)k − 2(h) \\ & = (2(h + 1) − 1)k − 2((h + 1) − 1) \end{aligned}

♣

Satz 4.2 : Sei D ein wieder Ableitungsgraph zu einer Ableitung in einer k–normalen wachsend kontextsensitiven Grammatik. Ist H ⊆ D als ungerichteter Graph zusammenhängend von der Größe t, so besitzt H eine Basis der Länge höchstens t(k − 1) + 1. Insbesondere gilt dies für autonome Teilgraphen H ⊆ D.

Beweis: Beweis durch vollständige Induktion:

t = 1: Basis umfaßt k = 1 · (k − 1) + 1 Knoten

t → t + 1: Um in einen Graphen H der Größe t einen Produktionsknoten einzufügen, so daß der Graph weiterhin zusammenhängend bleibt, muß man wenigstens einen Eingang und einen Ausgang miteinander verkleben. Dazu gibt es zwei Möglichkeiten:

• ein Ausgang eines Produktionsknotens von H, der bisher nicht als Eingang für einen anderen Produktionsknoten aus H verwendet wird, wird zu einem Eingang des neu hinzuzufügenden Produktionsknotens, oder

• ein Ausgang des neu hinzuzufügenden Knotens wird zu einem Eingang eines Produktionsknotens aus H, der bisher nicht als Ausgang eines anderen Produktionsknotens aus H verwendet wird.

In beiden Fällen erhöht sich die Länge der Basis um höchstens k − 1.

Das heißt die Basislänge ist höchstens

t(k − 1) + 1 + (k − 1) = (t + 1)(k − 1) + 1

♣

Satz 4.3 : Für einen Ableitungsgraphen D zu einer Ableitung in einer k–normalen wachsend kontextsensitiven Grammatik ist stets eine der folgenden Bedingungen erfüllt:

(i) es existiert ein autonomer Teilgraph F in D mit einer Größe mindestens k, und die Basis ist nicht länger als 2k(k − 1).

(ii) alle autonomen Teilgraphen von D haben eine Größe kleiner als k.

D.h. falls ein autonomer Teilgraph F in D mit Größe ≥ k existiert, dann existiert auch einer mit Größe ≥ k und Basis ≤ 2k(k − 1).

Beweis: Ann: Es existiert ein autonomer Teilgraph F ⊆ D mit einer Größe ≥ k und einer Basis länger als 2k(k − 1). Wir konstruieren nun aus diesem einen autonomen Teilgraphen, dessen Basis hinreichend klein ist.

Falls F einen Knoten der Tiefe k enthält, dann folgt aus Satz 4.1: Die Basis von I(v) ist nicht länger als

(2k − 1)k − 2(k − 1) \{ \begin{matrix}≤ & 2(k − 1)k & für k ≥ 2 \\ = & 1 & für k = 1 \end{matrix}

Sei nun angenommen, daß alle Knoten von F eine Tiefe nicht größer als k − 1 haben. Seien v_{1}, …, v_{r} nachfolgende Produktionsknoten der (einelementigen) Senken von F (also Knoten aus D \ F). Sei nun

F′_{i} = ⋃_{j=1}^{i} I(v_{j})

Da F laut Voraussetzung ein autonomer Teilgraph von D ist, sind die F′_{i} wegen des Zusammenhangs von F wieder zusammenhängend und damit autonome Teilgraphen von D.

Falls für ein i ∈ {1, …, r} gilt, daß I(v_{i}) eine Größe ≥ k hat, ist (i) gezeigt (da seine Tiefe ≤ k ist, folgt das aus Satz 4.1).

Seien also alle I(v_{i}) von einer Größe ≤ k − 1. Sei F′_{i_{0}} das erste F′_{i} mit einer Größe von mindestens k. Also hat F′_{i_{0}−1} höchstens die Größe k − 1 und nach Satz 4.2 also eine Basis von höchstens (k − 1)(k − 1) + 1.

I(v_{i_{0}}) besitzt höchstens die Größe k − 1, also ebenfalls eine Basis, die nicht länger ist als (k − 1)(k − 1) + 1.

Im schlimmsten Fall stoßen F′_{i_{0}−1} und I(v_{i_{0}}) gerade in der letzten Reihe vor der Basis aneinander.

Also:

|{ Basisknoten von F′_{i_{0}}}| ≤ |{ Basisknoten von F′_{i_{0}−1}}| + |{ Basisknoten von I(v_{i_{0}}) }|
≤ (k − 1)(k − 1) + 1 + (k − 1)(k − 1) + 1
= 2k(k − 1) − 2(k − 1) + 2
≤ 2k(k − 1) für k ≥ 2
♣

5 Der Abschluß von GCSL unter inversen Homomorphismen

Wie eingangs erwähnt ist die Abgeschlossenheit von GCSL unter inversen Homomorphismen der Schlüssel zu unserer Konstruktion einer wachsend kontextsensitiven Grammatik aus einer quasi wachsenden Grammatik.

Bemerkung: Sei L ⊆ Σ^{∗} eine wachsend kontextsensitive Sprache, sei h: Δ^{∗} → Σ^{∗} ein Homomorphismus und sei l := max {|h(a)| : a ∈ Σ}.

Da GCSL unter Substitution abgeschlossen ist, genügt es, den Abschluß von GCSL unter inversen Homomorphismen für ε–freie Homomorphismen zu zeigen. Denn falls Δ_{1} := {a ∈ Δ : h(a) = ε} und Δ_{2} := Δ \ Δ_{1} nichtleer sind, dann ist h_{1} := h |_{Δ_{2}} ε–frei und

h^{−1}(L) = S(h_{1}^{−1}(L)),

wobei S eine Substitution ist, so daß S(a) = Δ_{1}^{∗}aΔ_{1}^{∗} für jedes a ∈ Δ_{2}.

Wir wollen nun zeigen, daß h^{−1}(L) ∈ GCSL ist, indem wir (intuitiv) für jedes Wort u ∈ L eine Ableitung S ⟹^{∗}_{G} u für eine Grammatik G, die L erzeugt, in einzelne, in gewissem Sinne voneinander unabhängige (autonome) Abschnitte unterteilen. Diese ”Abschnitte“ sollen dann jeweils in einer Regel von G′ = ⟨N′, Δ, S′, P′⟩ zusammengefaßt werden. Um zu sehen, daß und wie diese Einteilung in ”Abschnitte“ möglich und sinnvoll ist, werden die Erkenntnisse über Ableitungsgraphen aus Kap. 4.2 verwendet.

In solchen ”Abschnitten“, in denen ein Stück von u entstehen würde, wollen wir stattdessen die Urbilder möglichst großer Präfixe eines solchen Stückes von u ableiten. Die dabei anfallenden ”Reste“ sollen natürlich eingesammelt und später weiterverwendet werden. Da das Urbild eines Wortes u unter h im schlimmsten Fall nur \frac{1}{l} mal so lang ist wie sein Bild, werden als Nichtterminalzeichen von G′ hinreichend lange Tupel über (Σ∪N) definiert, um auch hier noch wachsende Regeln zu erhalten.

Beides, die Anwendung von Satz 4.3 und die sinnvolle Definition der Regeln aus P′ für Tupel erfordert eine k–normale Grammatik G, die L erzeugt, wobei k (die Länge der Tupel) hinreichend groß sein muß. Man wird sehen, daß k > 2l hinreichend ist.

Nach Satz 2.1 existiert eine k–normale Grammatik G = ⟨N, Σ, S, P ⟩, die L erzeugt.

Nun definieren wir dazu eine neue kontextsensitive Grammatik G′ = ⟨N′, Δ, S′, P′⟩, weisen nach, daß sie wachsend ist, und zeigen dann L(G′) = h^{−1}(L).

Die Definition von G′ = ⟨N′, Δ, S′, P′⟩ :

Wir setzen N′ = N_{1} ∪ N_{2}, wobei N_{1} = (Σ ∪ N)^{k} und N_{2} = ⋃_{j=1}^{k−1}(Σ ∪ N)^{j}. Die Menge P′ der Produktionen ist aufgeteilt in vier Teilmengen P_{0}, P_{1}, P_{2}, P_{3}. In der Beschreibung dieser Teilmengen verwenden wir folgende natürliche Projektion von N′ nach (Σ ∪ N)^{∗}: C (⟨a_{1}, a_{2}, …, a_{j}⟩) = a_{1}a_{2} … a_{j} für jedes ⟨a_{1}, a_{2}, …, a_{j}⟩ ∈ N′.

Nun definieren wir:

P_{0} = {S′ → w | w ∈ Δ^{∗}, |h(w)| ≤ 2k(k − 1) + k und S ⟹^{∗}_{G} h(w)}
P_{1} = {S′ → β | β ∈ (N_{1})^{2(k−1)+1} und S ⟹^{∗}_{G} C(β)}
P_{2} = {α → β | α ∈ (N_{1})^{2(k−1)+1}, β ∈ (N_{1})^{2(k−1)+2} und C(α) ⟹^{∗}_{G} C(β)}

P_{3} = \{t_{1}α → wt_{2}α′ | \begin{matrix}t_{1}, t_{2} ∈ N_{2} ∪ \{ε\}, α ∈ (N_{1})^{m}, 1 ≤ m ≤ k, α′ ∈ N_{1} ∪ \{ε\}, \\ w ∈ Δ^{∗} mit |h(w)| ≥ k und α′ ≠ ε ⇒ |C(t_{2})| ≤ l − 2 \\ und C(t_{1}α) ⟹^{∗}_{G} h(w)C(t_{2}α′) in weniger als k Schritten \end{matrix} \}

In P_{0} werden alle die Wörter erzeugt, die für die weitere Behandlung zu kurz sind.

In P_{1} werden alle Anfangstücke möglicher Ableitungen zusammengefaßt, die als Grundlage für einen in einer Regel aus P_{2} zusammengefaßten ”Abschnitt“ lang genug sind.

In P_{2} sind alle Regeln, die solche ”Abschnitte“ zusammenfassen.

Und in P_{3} passiert das wesentliche: In jeder Regel wird zusammengefaßt: Eine mögliche Folge von Ableitungsschitten in G, die zu einem (möglichen) Teilwort eines Wortes u ∈ L führt, und das Bilden eines Urbildes eines hinreichend langen Präfixes von u sowie das Sammeln der dabei anfallenden Reste.

Satz 5.1 : Die oben definierte Grammatik G′ ist für k > 2l und l := max {|h(a)| : a ∈ Σ} wachsend.

Beweis: Die Regeln aus P_{0}, P_{1} und P_{2} sind trivialerweise wachsend.

Betrachte nun die Regeln aus P_{3}:

Wegen |h(w)| ≥ k > 2l ist stets |w| ≥ 3. Also sind zunächs die Regeln aus P_{3} mit |t_{1}α| ≤ 2 wachsend. Sei also nun |t_{1}α| ≥ 3.

t_{1} = ε: Sei also f := |α|.

⇒ |C(α)| = f · k ⇒ |h(w)C(t_{2}α′)| > f · k

Es gilt:

|C(t_{2}α′)| ≤ k + l − 2

⇒ |h(w)| ≥ f · k − (k + l − 2) = (f − 1)k − l + 2 ≥ (f − 2)k + l + 2 ⇒ |w| ≥ 2(f − 2) + 2 = 2 · f − 2 > f für f ≥ 3

Für f = 2 folgt wegen |t_{1}α| ≥ 3, daß t_{2} ≠ ε. Also sind die Regeln dieses Typs wachsend.

t_{1} ≠ ε: Wir setzen wieder f := |α|.

⇒ |C(t_{1}α)| ≥ f · k + 1

α′ = ε: |C(t_{2})| ≤ k − 1 ⇒ |h(w)| ≥ f · k + 1 − (k − 1) = (f − 1)k + 2
⇒ |w| ≥ 2(f − 1) + 1 = 2 · f − 1 > f für f ≥ 2
α′ ≠ ε: |C(t_{2}α′)| ≤ k + l − 2
⇒ |h(w)| ≥ f · k + 1 − (k + l − 2) = (f − 1)k − l + 3 ≥ (f − 2)k + l + 3
⇒ |w| ≥ 2(f − 2) + 2 = 2 · f − 2 > f − 1 für f ≥ 2

Also sind auch die Regeln dieses Typs wachsend.

Damit ist die Behauptung gezeigt. ♣

Bemerkung: Das α′ wurde in den Regeln aus P_{3} also nur eingeführt, um zu gewährleisten, daß die Regeln wachsend sind. Erlaubt man, daß |C(t_{2})| ≤ k + l − 2 (spart man sich also die Aufsplittung der gesammelten Bruchstücke auf zwei Tupel), dann kann für |α| = 2 und |C(t_{1})| < l − 2 nicht gewährleistet sein, daß die Regeln wachsend sind, denn dann ist: 2k + 1 ≤ |C(t_{1}α)| ≤ 2k + l − 3, für |C(t_{2})| = k + l − 2 also k − l + 3 < |h(w)| ≤ k − 1, also für k ≤ 3l − 3 möglicherweise |w| = 2 und die entsprechende Regel nicht wachsend.

Wählt man also k > 3l statt k > 2l, so kann man sich die Aufspaltung sparen, muß allerdings in Kauf nehmen, daß G′ dann womöglich 1.5 mal so lange und |Σ ∪ N|^{l} mal so viele Regeln hat, sowie (1 + |Σ ∪ N|^{l}) mal so viele Nichtterminale.

Satz 5.2 : Für eine wachsend kontextsensitive Sprache L ⊆ Σ^{∗}, einen ε–freien Homomorphismus h: Δ^{∗} → Σ^{∗} und l, k wie in Satz 5.1, G = ⟨N, Σ, S, P ⟩ k–normal mit L(G) = L und G′ = ⟨N′, Δ, S′, P′⟩ dazu wie oben definiert gilt:

L(G′) = h^{−1}(L)

Beweis: Man kann leicht per Induktion über die Länge der Ableitung zeigen, daß alle Satzformen abgeleitet aus S′ die Form haben:

α_{1}w_{1}α_{2}w_{2} … w_{s−1}α_{s}  mit  S ⟹^{∗}_{G} C(α_{1})h(w_{1})C(α_{2})h(w_{2}) … h(w_{s−1})C(α_{s})

wobei alle α ∈ (N′)^{∗} und alle w ∈ Δ^{∗}.

Daraus folgt: w ∈ L(G′) ⇒ ∃u ∈ L : h(w) = u. ⇒ L(G′) ⊆ h^{−1}(L)

Es bleibt also zu zeigen:

h^{−1}(L) ⊆ L(G′)

Sei also w ∈ h^{−1}(L), und sei u ∈ L so, daß h(w) = u.

Falls |u| ≤ 2k(k − 1) + k, dann wird w durch eine Produktion aus P_{0} abgeleitet. Also nehme man |u| > 2k(k − 1) + k an.

Nun soll die Ableitung S ⟹^{∗}_{G} u in autonome ”Abschnitte“ eingeteilt werden.

Wähle u_{1} so, daß S ⟹^{∗}_{G} u_{1}, u_{1} ⟹^{∗}_{G} u und |u_{1}| = 2k(k − 1) + k. Das ist möglich, da nach der ersten Regelanwendung einer Regel aus G die erhaltene Satzform kürzer ist als k < 2k(k − 1) und mit jeder weiteren Regelanwendung die Satzform um nur 1 länger wird aufgrund der k– Normalität von G. Selbstverständlich existiert ein z_{1} ∈ (N_{1})^{2(k−1)+1}, so daß C(z_{1}) = u_{1}, also ist S′ → z_{1} ∈ P_{1}. Damit hat man also die ”Anfangsabschnitte“.

Sei F_{1} ein Ableitungsgraph für u_{1} ⟹^{∗}_{G} u. Falls F_{1} einen autonomen Teilgraphen enthält von der Größe wenigstens k, dann kann man durch geeignet oftmaliges wiederholen einer Operation, die eine (einelementige) Senke aus dem Teilgraphen entfernt, einen Teilgraphen F^{(1)} ⊆ F_{1} erhalten mit der Größe k. Es ist klar: F^{(1)} gehört zu einer Folge von k Produktionen, die angewandt auf die Basis von F_{1} aus dem Wort u_{1} ein Wort u_{2} ableiten mit u_{2} ⟹^{∗}_{G} u.

Sei z_{2} ∈ (N_{1})^{2(k−1)+2} so, daß C(z_{2}) = u_{2}. Dann gilt nach der Definition der Menge P_{2} also

z_{1} ⟹_{G′} z_{2}.

Nun kann man das Verfahren rekursiv auf F_{2} := F_{1} \ F^{(1)} anwenden:

Falls der Ableitungsgraph F_{i} für u_{i} ⟹^{∗}_{G} u einen autonomen Teilgraph enthält von der Größe wenigstens k, dann kann man daraus wie oben einen autonomen Teilgraphen F^{(i)} finden von der Größe k, und F^{(i)} gehört zu einer Folge von k Produktionen, die angewandt auf die Basis von F_{i} aus dem Wort u_{i} ein Wort u_{i+1} ableiten mit u_{i+1} ⟹^{∗}_{G} u.

Aus Satz 4.3 folgt, daß die Basis von F^{(i)} nicht größer ist als 2k(k − 1). Es gibt also ein z̃_{i} ∈ (N_{1})^{2(k−1)+1} mit: Die Basis von F^{(i)} ist ein Teilwort von C(z̃_{i}), und z̃_{i} ist ein Teilwort von z_{i}.

Sei z_{i+1} ∈ (N_{1})^{2(k−1)+2} so, daß C(z_{i+1}) = u_{i+1}. Nach der Definition von P_{2} gilt also: z_{i} ⟹_{G′} z_{i+1}.

Da die Ableitung S ⟹^{∗}_{G} u aus endlich vielen Schritten besteht, gibt es Wörter u_{x} ∈ (Σ ∪ N)^{∗} und z_{x} ∈ (N_{1})^{∗} so, daß:

1. S′ ⟹^{∗}_{G′} z_{x}

2. C(z_{x}) = u_{x}

3. u_{x} ⟹^{∗}_{G} u , und alle autonomen Teilgraphen des zugehörigen Ableitungsgraphen H sind von der Größe < k. (folgt aus Satz 4.3)

Damit hat man also säuberlich gleichmäßige Abschnitte, so weit es geht.

Und nun kommen die wichtigsten, die ”Schlußabschnitte“. Da die autonomen Teilgraphen von H jeder eine Basis nicht länger als 1 + (k − 1)(k − 1) = k +(k −1)(k −2) haben (vgl. Satz 4.2), kann man die Wörter u_{x} und u aufteilen in Teilwörter u_{x}^{1}, u_{x}^{2}, …, u_{x}^{r} und u_{1}, u_{2}, …, u_{r}, so daß gilt: ∀_{1≤i≤r}k ≤ |u_{x}^{i}| ≤ k + (k − 1)(k − 2) und u_{i} wird abgeleitet aus u_{x}^{i} in weniger als k Schritten (dabei sind auch 0 Schritte möglich).

(Also u_{x} = u_{x}^{1}u_{x}^{2} … u_{x}^{r} ⟹^{∗}_{G} u_{1}u_{2} … u_{r} = u mit u_{x}^{i} ⟹^{∗}_{G} u_{i} in weniger als k Schritten für alle i = 1, …, r.)

Nun definieren wir für jedes i = 1, …, r Wörter w_{i}, s_{i}, z_{j_{i}}, z′_{j_{i}}, z′′_{j_{i}}, t_{i}, α_{i} wie folgt (dabei sei w_{0} = ε):

• w_{i} ist das größte Präfix von w^{↖w_{i−1}}, so daß h(w_{i}) ein Präfix von u_{1}u_{2} … u_{i}^{↖h(w_{i−1})} ist.

(Dabei bedeute v^{↖ṽ} dasjenige Wort, welches von v übrig bleibt, wenn man das Präfix ṽ wegnimmt.)

• s_{i} ist das Suffix von u_{1}u_{2} … u_{i}, so daß u_{1}u_{2} … u_{i} = h(w_{1}) … h(w_{i})s_{i}, also s_{i} ∈ ⋃_{i=0}^{l−1} Σ^{i}. Bedenke s_{r} = ε.

• falls z_{x} = z_{1}z_{2} … z_{y}, wobei z_{1}, …, z_{y} ∈ N_{1}, dann definiere z′_{j_{i}}, z′′_{j_{i}} ∈ (Σ ∪ N)^{∗} für j_{i} ∈ {1, 2, …, y}, i = 1, 2, …, r durch:

C(z_{j_{i}}) = z′_{j_{i}}z′′_{j_{i}} und u_{x}^{1}, u_{x}^{2}, …, u_{x}^{i} = C(z_{1} … z_{j_{i}−1})z′_{j_{i}}

also z′_{j_{i}} ∈ ⋃_{j=1}^{k}(Σ ∪ N)^{j}, z′′_{j_{i}} ∈ ⋃_{j=0}^{k−1}(Σ ∪ N)^{j}, also z′′_{j_{i}} = ε erlaubt. Bedenke z′_{j_{r}} = z_{j_{r}}, z′′_{j_{i}} = ε. Anders ausgedrückt:

u_{x}^{i} = z′′_{j_{i−1}}C(z_{j_{i−1}+1} … z_{j_{i}−1})z′_{j_{i}}

mit j_{0} = 0, z_{0} = z′′_{0} = ε.

• t_{i} ∈ ⋃_{j=0}^{k−1}(Σ∪N)^{j} = N_{2}∪{ε} und α_{i} ∈ (Σ∪N)^{k}∪{ε} = N_{1}∪{ε} sind so, daß C(t_{i}α_{i}) = s_{i}z′′_{j_{i}} (bedenke t_{r} = ε, α_{r} = ε)

Skizze (Beispiel):

. . . . . . . . . ................  ................  ................  ................  ................  ................  ................ ...............  ...............  ...............  ...............  ............... .......  .......  .......  .......  ....... ................  ............................  ..........................  ......................  ....................  .................. u_{x}  u_{1}  u_{2}  u_{3}  u_{4}  u_{r} α_{1}  t_{1}α_{2} = εt_{2}  α_{3} = εt_{3}  α_{4} = εt_{4}  α_{r−1} t_{r−1}  α_{r} = ε t_{r} = ε h(w^{1}) s_{1} h(w_{2}) s_{2}  h(w_{3})  s_{3} h(w_{4}) s_{4} = ε h(w_{5}) …  s_{r−1} h(w_{r})  s_{r} = ε z_{x} z_{1}  z_{2}  z_{3}  z_{4}  z_{5}  z_{6}  z_{7}  z_{y−1} z_{y} z′_{j_{1}} z′′_{j_{1}} z′_{j_{2}} z′′_{j_{2}}  z′_{j_{3}} z′′_{j_{3}} = ε z′_{j_{4}} z′′_{j_{4}}  z′_{j_{r−1}} z′′_{j_{r−1}} z′_{j_{r}} z′′_{j_{r}} = ε

Man kann beobachten, daß:

• Wegen k ≤ |u_{x}^{i}| ≤ k + (k − 1)(k − 2) = k(k − 2) + 2 < k(k − 1) (da k > 2)

ist j_{i} − j_{i−1} ≤ k − 1, also außer über das ”Bruchstück“ z′′_{j_{i−1}} erstreckt sich u_{x}^{i} über ≤ k − 1 viele von den z_{j}.

• Wegen |z′′_{j_{i}}| ≤ k − 1 und |s_{i}| ≤ l − 1 für alle i ist stets |C(t_{i}α_{i})| ≤ k + l − 2, also gilt: α_{i} ≠ ε ⇒ |C(t_{i})| ≤ l − 2.

Folgende Ableitung ist also durch Regeln aus P_{3} möglich:

z_{x} ⟹_{G′} w_{1}t_{1}α_{1}z_{j_{1}+1} … z_{y} ⟹_{G′} w_{1}w_{2}t_{2}α_{2}z_{j_{2}+1} … z_{y} ⟹^{∗}_{G′} w_{1}w_{2} … w_{r} = w

Also ist w ∈ L(G′), und damit ist L(G′) = h^{−1}(L) gezeigt. ♣

Der Beweis der eingangs angeführten Behauptung ist also glücklich gelungen, so daß diese jetzt als Satz formuliert werden darf:

Satz 5.3 : Die Klasse GCSL ist abgeschlossen unter inversen Homomorphismen.

Beweis: Folgt aus der Eingangsbemerkung, Satz 5.1 und Satz 5.2. ♣

6 Die Länge der ”invertierten“ Grammatik

Satz 6.1 : Sei L ∈ Σ^{∗} eine kontextsensitive Sprache, sei h: Δ^{∗} → Σ^{∗} ein ε–freier injektiver Homomorphismus. Seien l und k wie in Satz 5.1, G = ⟨N, Σ, S, P ⟩ k–normal mit L(G) = L und G′ = ⟨N′, Δ, S′, P′⟩ mit L(G′) = h^{−1}(L) wie in Satz 5.2. Dann gilt:

|Σ ∪ N|^{k} ≤ |N′| ≤ 2 · |Σ ∪ N|^{k}
|P′| ≤ (k + l + 2) · |Σ ∪ N|^{2k^{2}}

Beweis: Seien q_{1} die Anzahl der Regeln der Form (1), q_{2} die Anzahl der Regeln der Form (2) und q_{3} die Anzahl der Regeln der Form (3) aus Def 2.1.

Abschätzung:

Zunächst berechnen wir |N′|.

|N′| = \frac{|Σ ∪ N|^{k} − 1}{|Σ ∪ N| − 1} + |Σ ∪ N|^{k} \{ \begin{matrix}≤ 2 · |Σ ∪ N|^{k} \\ ≥ |Σ ∪ N|^{k} \end{matrix}

Die Zahl der Regeln:

• in P_{0}: Es gibt nicht mehr als

∑_{i=1}^{2k(k−1)+k} |Σ|^{i} = \frac{|Σ|^{2k^{2}−k+1} − 1}{|Σ| − 1} ≤ |Σ|^{2k^{2}−k+1}

Wörter der Länge ≤ 2k(k − 1) + k in L, d.h. es gibt nicht mehr als |Σ|^{2^{k}−k+1} Regeln in P_{0}.

• in P_{1}: Es gibt nicht mehr als

min (q_{2} · q_{3}^{2k(k−1)+k−1}, |Σ ∪ N|^{2k(k−1)+k})

in G ableitbare Satzformen der Länge 2k(k − 1) + k. Also höchstens ebensoviele Regeln in P_{1}, das sind

\begin{matrix}min & (|P |^{2k(k−1)+k}, |Σ ∪ N|^{2k(k−1)+k}) \\ ≤ |Σ ∪ N|^{2k^{2}−k} . \end{matrix}

• in P_{2}: Es gibt |Σ ∪ N|^{2k(k−1)+k} viele Satzformen der Länge 2k(k − 1) + k. Aus jeder lassen sich nicht mehr als min (q_{3}^{k}, |Σ ∪ N|^{k}) Satzformen ableiten. Also gibt es

≤ |Σ ∪ N|^{2k(k−1)+k} · |Σ ∪ N|^{k} ≤ |Σ ∪ N|^{2k^{2}}

Regeln in P_{2}.

• in P_{3}: Wieviele Ableitungen C(t_{1}α) ⟹^{∗}_{G} vC(t_{2}) mit v ∈ Σ^{∗}, t_{1}, t_{2} ∈ N_{2} ∪ {ε}, α ∈ (N_{1})^{m} , m ≤ 2(k − 1) und weniger als k Ableitungsschritten gibt es?

Es gibt nicht mehr als

(|N_{2}| + 1) · (∑_{i=1}^{k} (|Σ ∪ N|^{k})^{i}) = ∑_{j=0}^{k−1} |Σ ∪ N|^{j} · \frac{(|Σ ∪ N|^{k})^{k+1} − 1}{|Σ ∪ N|^{k} − 1}

≤ |Σ ∪ N|^{k} · (|Σ ∪ N|^{k})^{k+1} = |Σ ∪ N|^{k} · |Σ ∪ N|^{k(k+1)} = |Σ ∪ N|^{k(k+2)} linke Seiten. Aus den Projektionen dieser linken Seiten lassen sich nicht mehr als

|Σ ∪ N|^{k(k+2)} · (∑_{i=0}^{k−1} |Σ ∪ N|^{i}) ≤ |Σ ∪ N|^{k(k+2)} · |Σ ∪ N|^{k} ≤ |Σ ∪ N|^{k(k+3)}

Satzformen ableiten. ^{6} Dabei gibt es nicht mehr als k +l −2 Möglichkeiten, die abgeleitete Satzform auf h(w) und die Tupel t_{2} und α′ zu verteilen. Also gibt es nicht mehr als

(|Σ ∪ N|^{k(k+3)}) · (k + l − 2)

Regeln in P_{3}.

Insgesamt also erhöht sich die Anzahl der Regeln in G′ gegenüber der in G, falls G k–normal, auf höchstens

|Σ|^{2k^{2}−k+1}
+|Σ ∪ N|^{2k^{2}−k}
+|Σ ∪ N|^{2k^{2}}
+ (|Σ ∪ N|^{k(k+3)}) · (k + l − 2)
≤ (|Σ|^{2k^{2}} + |Σ ∪ N|^{2k^{2}} + |Σ ∪ N|^{2k^{2}} + |Σ ∪ N|^{2k^{2}}) · (k + l − 2)
≤ (k + l + 2) · |Σ ∪ N|^{2k^{2}}
♣

Beispiel 6.1 : Sei L = Σ^{∗}, G = ⟨N, Σ = {a_{1}, …, a_{n}}, S, P ⟩ mit L(G) = L so, daß sich mit G auch alle Satzformen aus (Σ ∪ N)^{∗} erzeugen lassen. Sei Δ = {b_{1}, b_{2}, …, b_{n}}, h: Δ → Σ definiert durch:

h(a_{i}) = b_{i} ∀i = 1, …, n

h ist also injektiv. Konstruiere G′ = ⟨N′, Δ, S, P′⟩ mit L(G′) = h^{−1}(L) wie in Satz 5.1. Dann sind die Abschätzungen aus Folgerung 6.1 zu P_{1} und P_{2} scharf. Für P_{0} und P_{3} gilt:

|P_{0}| = ∑_{i=1}^{2k(k−1)+k} |Σ|^{i} = \frac{|Σ|^{2k^{2}−k+1}−1}{|Σ|−1}
≥ |Σ|^{2k^{2}−k}
|P_{3}| ≥ (k + l − 2) · |Σ ∪ N|^{k(k+3)}

Insgesamt gilt also:

|P′| ≥ |Σ|^{2k^{2}−k} + |Σ ∪ N|^{2k^{2}−k}| + |Σ ∪ N|^{2k^{2}} + (k + l − 2) · |Σ ∪ N|^{k(k+3)}
≥ (k + l + 2) · |Σ|^{k^{2}} für k ≥ 2

Das heißt, die Abschätzung aus Folgerung 6.1 ist in dem Sinne scharf, daß |P′| exponentiell von k^{2} abhängen kann.

6Aus der Projektion jeder linken Seite lassen sich nicht mehr als ∑_{i=0}^{k−1} q_{3}^{i} ≤ |P |^{k} Satzformen ableiten, für |P | ≥ |Σ ∪ N| führt dieser Weg also zu einer gröberen Abschätzung.

Bemerkung: Bei einem nicht injektiven Homomorphismus gibt es in P_{1} (analog in P_{3}) für jedes Wort u (Teilwort u′) statt einer Regel (S → w) (bzw. (t_{1}α → wt_{2}α′)) mit h(w) = u (bzw. h(w) = u′) so viele, wie h(w) = u (bzw. h(w) = u′) Urbilder besitzt.

Bei einem Homomorphismus der Form h: Δ^{∗} → Σ^{∗} mit Δ = {a_{1,1}, a_{1,2}, a_{1,3}, a_{2,1}, …, a_{n−1,3}, a_{n,1}, a_{n,2}, a_{n,3}} und Σ = {a_{1}, …, a_{n}} definiert durch:

h(a_{i,1}) = h(a_{i,2}) = h(a_{i,3}) = a_{i} ∀i = 1, …, n

sind das zum Beispiel 3^{|h(w)|} viele (in P_{3} sind das wegen der Forderung |h(w)| ≥ k also exponentiell in k viele).

7 Die Länge einer aus einer QGG erzeugten GCSG

Satz 7.1 : Die Sprachen, die durch QGG’s und durch GCSG ’s erzeugt werden können, sind dieselben.

Beweis: Jede GCSG kann als QGG mit einer konstanten Gewichtsfunktion gesehen werden.

Sei L erzeugt durch eine quasi–wachsende Grammatik G = ⟨N, Σ, S, P ⟩ mit einer Gewichtsfunktion f. Ohne Beschränkung der Allgemeinheit kann man annehmen, daß S nicht auf einer rechten Seite einer Produktion auftaucht und daß f(S) = 1.

Sei x ∉ Σ ∪ N und sei h ein Homomorphismus, so daß h(a) = ax^{f(a)−1} für jedes a ∈ Σ ∪ N.

Dann ist G′ = ⟨N ∪ {x}, Σ, S, P′⟩, wobei P′ = {h(α) → h(β) : (α → β) ∈ P }, eine wachsend kontextsensitive Grammatik und L(G) = h^{−1}(L(G′)).

Aus Satz 3.1 (oder Satz 5.3) folgt also die Behauptung. ♣

Satz 7.2 : Sei L erzeugt durch eine quasi–wachsende Grammatik G = ⟨N, Σ, S, P ⟩ mit einer Gewichtsfunktion f, f(S) = 1, und S tauche nicht auf einer rechten Seite einer Produktion auf. Dann gibt es eine wachsend kontextsensitive Grammatik G′ = ⟨N, Σ, S′, P′⟩ mit L(G′) = L und

|P′| ≤ 2k · (|Σ| + |N| + (|P | · k · |Σ ∪ N|^{k} + \frac{1}{2}k^{2} · |P |^{2}) · (c − 1))^{2k^{2}}

wobei k = 2l + 1 mit l = max{f(a) : a ∈ Σ}, c = max{f(β) − f(α) | (α → β) ∈ P }.

Beweis: Folgt aus der Konstruktion im Beweis von Satz 7.1 sowie Satz 2.1 und Satz 5.3, da der im Beweis von Satz 7.1 definierte Homomorphismus injektiv ist. ♣ Das bedeutet, daß bei der Umformung einer quasi wachsenden Grammatik G in eine wachsend kontextsensitive das Anschwellen von G abhängig ist von der zugehörigen Gewichtsfunktion f:

• Ist f linear in |Σ ∪ N|, so ist das Anschwellen polynomiell,

• Ist f polynomiell, so ist das Anschwellen exponentiell,

• Ist f exponentiell, so ist das Anschwellen doppelt exponentiell,

• usw.

Das Verhalten ist also genauso ungemütlich wie auf den ersten Blick vermutet.

Andererseits ist es auch wieder erfreulich, da es darauf hinweist, daß es bei einigen Sprachen möglicherweise lohnenswert einfacher ist, ihre Zugehörigkeit zu GCSL durch Angabe einer quasi wachsenden Grammatik zu zeigen, da letztere in einigen Fällen erheblich (exponentiell) kürzer sein kann.

Dank

sagen möchte ich alle denen, die mich fachlich und moralisch unterstützt haben, insbesondere Gerhard Buntrock für seine unermüdlichen Ratschläge und wiederholtes Durcharbeiten dieser Studienarbeit und Siegfried Pihan für seinen unermüdlichen moralischen Beistand. Bedanken möchte ich mich auch bei Diana Emme, Thomas Feilhauer, Norbert Hemrich, Ansgar Lammen, Eva und Joachim Kix, Carmen Schwenkel, Jörg Sobel, Heribert Vollmer, Klaus Wagner, Michael Wellenbrock.

Der größte Dank gebührt Jesus Christus, unserem Herrn, der mir die entscheidenden Punkte in den Beweisen und Abschätzungen aufzeigte und mich mit unendlicher Geduld und Liebe immer wieder aufrichtete und motivierte.

Literatur

[FS91] Gerhard Buntrock und Ulrich Hertrampf, Theorie der Formalen Sprachen, Skript zur Vorlesung mit Übung, SS 1991

[BL92] Gerhard Buntrock und Krzysztof Lorys, On growing context-sensitive languages, TR 38, Universität Würzburg, Januar 1992, 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 623, p. 77-88, 1992

[DW86] Elias Dahlhaus und Manfred K. Warmuth, Membership for growing context-sensitive grammars is polynomial, Journal of Computer and System Sciences, 33: 456–472, 1986

[GGH69] Seymour Ginsburg, Sheila Greibach and John Hopcroft, Studies in abstract families of languages, Memoir #87, American Mathematical Society, 1969

[Lau88] Clemens Lautemann, One pushdown and a small tape, In Klaus W. Wagner, editor, Dirk Siefkes zum 50. Geburtstag, S. 42–47, Technische Universität Berlin und Universität Augsburg, 1988

[NLII84] H.Noltemeier/R.Laue, Informatik II — Einführung in Rechnerstrukturen und Programmierung, Hanser, 1984

[Rei86] Wolfgang Reisig, Petrinetze — Eine Einführung, Springer, Studienreihe Informatik, 1986

[Schö92] Uwe Schöning, Theoretische Informatik kurz gefaßt, BI Wissenschaftsverlag, 1992

[WW86] Klaus W. Wagner and Gerd Wechsung, Computational Complexity, Reidel Verlag, Dordrecht, 1986 and VEB Deutscher Verlag der Wissenschaften, 1986