Gundula Niemann

Charakterisierungen

mit

schwach wachsend kontextsensitiven Grammatiken

Diplomarbeit

Betreuer: Prof. Dr. Klaus W. Wagner, Dr. Gerhard Buntrock

März 1994

Lehrstuhl für Theoretische Informatik · Bayerische Julius-Maximilians-Universität Würzburg

Zusammenfassung

Eine Einschränkung kontextsensitiver Grammatiken erhält man, indem man jedem Zeichen durch eine Zeichenbewertung ein Gewicht zuordnet und für jede Regel verlangt, daß die Summe aller Gewichte der Zeichen auf der linken Seite kleiner ist als die der Zeichen auf der rechten Seite. Es ist seit kurzem bekannt, daß die so beschriebenen quasi wachsend kontextsensitiven Grammatiken die Klasse der wachsend kontextsensitiven Sprachen (GCSL ) charakterisieren.

Zusätzlich zur reinen Zeichenbewertung lassen sich Stellenbewertungen für Regeln einführen. Dabei wird jeder Position innerhalb einer Regel ein Wert zugewiesen. Die Bewertung einer Regelseite ergibt sich dann als die Summe über die Produkte der Zeichenbewertung und der Stellenbewertung der Zeichen. Eine kontextsensitive Grammatik heißt schwach wachsend bezüglich einer Stellenbewertung, falls es eine Zeichenbewertung gibt, die den Zeichen Gewichte so zuordnet, daß für jede Regel die Bewertung der linken Seite kleiner ist als die der rechten. Die schwach wachsend kontextsensitiven Grammatiken mit konstanten Stellenbewertungen charakterisieren GCSL .

Wir unterscheiden drei Familien von Stellenbewertungen: Die gleichmäßigen Stellenbewertungen, das sind Stellenbewertungen, die sich als Anfangsstück einer Exponentialfunktion schreiben lassen, die ungleichmäßigen Stellenbewertungen und die mit Nullstellen.

Es stellt sich heraus, daß schwach wachsend kontextsensitive Grammatiken bezüglich ungleichmäßiger Stellenbewertungen die Klasse der kontextsensitiven Sprachen (CSL ) charakterisieren. Ebenso charakterisieren schach wachsend kontextsensitive Grammatiken bezüglich Stellenbewertungen mit Nullstellen die Klasse CSL .

Im Gegensatz dazu bilden die schwach wachsend kontextsensitiven Sprachen bezüglich nichtkonstanter gleichmäßiger Stellenbewertungen eine Hierarchie, die die exponentielle Zeithierarchie von CSL charakterisiert. Weiterhin ist der Abschluß jeder dieser Sprachklassen unter inversen Homomorphismen CSL .

Außerdem zeigt sich: Jede schwach wachsend kontextsensitive Grammatik bezüglich einer gleichmäßigen Stellenbewertung läßt sich in Cremers-Normalform überführen. Und genau dann, wenn dies auch für ungleichmäßige Stellenbewertungen gilt, kollabiert die exponentielle Zeithierarchie für CSL .

Vorwort

Die vorliegende Diplomarbeit wurde im März 1994 an der Universität Würzburg abgegeben. Die Forschung auf dem hierin behandelten Gebiet ist inzwischen weiter gediehen, wenn auch neue Erkenntnisse sich vorwiegend auf Feinheiten beziehen. In der hier vorliegenden Version wurde allerdings auf korrigierende, verbessernde oder kürzende Eingriffe verzichtet, lediglich Tipp-, Rechtschreib- und Flüchtigkeitsfehler wurden ausgebessert. Außerdem wurde die Erklärung über das selbständige Abfassen der Arbeit durch eine Danksagung ersetzt. Offensichtlich wurde auch ein Vorwort eingefügt.

Ein ”Extended Abstract“ zu dieser Arbeit erscheint demnächst in LATIN’95, 2nd Latin American Symposium on Theoretical Informatics, Valparaíso/Viña del Mar, Chile, April 1995, Proceedings, in Lecture Notes of Computer Science (LNCS), Springer-Verlag.

Gundula Niemann

Würzburg, im Dezember 1994

Inhaltsverzeichnis

Einleitung 3

1 Grundlagen 7 1.1 Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Turingmaschinen und linear beschränkte Automaten . . . . . . . . . . . . . . 12

2 Robustheit, Abschluß und Normalform 15 2.1 Robustheit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Abschlußeigenschaften . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.3 Normalform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 Charakterisierung der kontextsensitiven Sprachen 29 3.1 Linear beschränkte Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2 Die ungleichmäßige Stellenbewertung . . . . . . . . . . . . . . . . . . . . . . . 33

4 Gleichmäßige Stellenbewertung 55

4.1 Effiziente Simulation einer Grammatik . . . . . . . . . . . . . . . . . . . . . . 55 4.1.1 Verbundene Grammatiken . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1.2 Effiziente Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4.2 Zähler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.3 Simulation zeitbeschränkter linearer Automaten . . . . . . . . . . . . . . . . . 74

5 Konsequenzen und abschließende Bemerkungen 81 5.1 Die Stellenbewertung mit Nullstellen . . . . . . . . . . . . . . . . . . . . . . . 81 5.2 Charakterisierung der exponentiellen Zeithierarchie von CSL . . . . . . . . . 85 5.3 Kontextsensitiv versus Nichtverkürzend . . . . . . . . . . . . . . . . . . . . . 89 5.4 Offene Fragen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

Literaturverzeichnis 93

Einleitung

Die Theorie der Formalen Sprachen hat sich aus dem Wunsch heraus gebildet, natürliche Sprachen durch ein formales Ersetzungskalkül beschreiben zu können. Noam Chomsky führte 1959 Grammatiken für formale Sprachen ein. Solch eine Grammatik besteht nach Chomsky aus einer endlichen Menge von Nichtterminalzeichen, einer endlichen Menge von Terminalzeichen, einem Startsymbol und einer endlichen Menge von Ersetzungsregeln. Als Sprache einer solchen Grammatik wird die Menge aller Zeichenketten bezeichnet, die aus Terminalen bestehen und aus dem Startsymbol mittels der Ersetzungsregeln abgeleitet werden können. Dabei unterschied Chomsky folgende vier Typen von Grammatiken ([Cho59]):

• Typ 0: Falls die Ersetzungsregeln einer Grammatik keinerlei Einschränkungen unterliegen, nennt man die Grammatik auch allgemein.

• Typ 1: Falls die Ersetzungsregeln einer Grammatik so beschaffen sind, daß in ihnen genau ein Nichtterminal abhängig von einem Kontext rechts und links durch eine nichtleere Zeichenkette ersetzt wird, nennt man die Grammatik kontextsensitiv.

• Typ 2: Falls in sämtlichen Regeln einer Grammatik jeweils nur ein Nichtterminal durch eine Zeichenkette ersetzt wird und keine anderen Zeichen rechts oder links davon betrachtet werden, nennt man die Grammatik kontextfrei.

• Typ 3: Falls schließlich eine Grammatik kontextfrei ist und in jeder ihrer Regeln jeweils ein Nichtterminal durch eine Zeichenkette bestehend aus höchstens einem Nichtterminal gefolgt von beliebig vielen Terminalen (auch keinem) ersetzt wird, nennt man die Grammatik regulär.

Eine (formale) Sprache nennt man kontextsensitiv, wenn es eine kontextsensitive Grammatik gibt, die diese Sprache erzeugt. Analog sind kontextfreie und reguläre Sprachen erklärt.

Weiterhin war es Chomsky, der die nichtverkürzenden (oder auch monotonen) Grammatiken betrachtete, deren Regeln nur dadurch eingeschränkt sind, daß in jeder Regel eine Zeichenkette durch eine wenigstens ebenso lange Zeichenkette ersetzt wird, und nachwies, daß die Klasse der von nichtverkürzenden Grammatiken erzeugten Sprachen gerade die der kontextsensitiven Sprachen ist. Daher kommt es auch, daß heute häufig nichtverkürzende Grammatiken als kontextsensitiv bezeichnet werden.

Für die Beschreibung natürlicher Sprachen haben diese Grammatiken allerdings nie eine wesentliche Bedeutung erlangt. Doch für die Konstruktion und Beschreibung von Programmiersprachen sind insbesondere die kontextfreien und zum Teil auch die kontextsensitiven Grammatiken nicht mehr wegzudenken.

Für jede kontextfreie Grammatik gibt es einen Kellerautomaten, der für jedes Eingabewort entscheidet, ob es von der Grammatik erzeugt wird. Solch ein Automat besitzt als einziges Speichermedium einen Keller, das ist ein Band, auf dem nur an einem Ende Zeichen geschrieben, ersetzt oder gelöscht werden dürfen; darüberhinaus benötigt er nur lineare Rechenzeit (im Verhältnis zur Eingabelänge). Diese Eigenschaft wird beim Syntaxtest von Programmiersprachen genutzt. Daher werden Programmiersprachen in der Regel kontextfrei entworfen.

Kontextfreie Sprachen haben den Nachteil, daß sie für die Wünsche und Anforderungen an Programmiersprachen zu wenig mächtig sind. Viele Vereinbarungen müssen zusätzlich zur Grammatik getroffen werden.

Kuroda hat gezeigt, daß kontextsensitive Sprachen durch linear beschränkte Automaten charakterisiert werden, das sind Automaten, die als einziges Speichermedium ein Band besitzen, auf dem ihnen linear viel Platz (im Verhältnis zur Eingabelänge) zur Verfügung steht. Vorteilhafterweise können wohl alle Programmiersprachen mit kontextsensitiven Grammatiken vollständig definiert werden. Allerdings ist die Rechenzeit allein für den Syntaxtest im allgemeinen exponentiell (im Verhältnis zur Eingabelänge).

Daher wurden vielfältige Erweiterungen kontextfreier und Einschränkungen kontextsensitiver Grammatiken untersucht, um mehr über Sprachen zwischen kontextfreien und kontextsensitiven Sprachen zu erfahren.

Eine Einschränkung kontextsensitiver Grammatiken erhält man, indem man von sämtlichen Regeln einer Grammatik verlangt, daß eine Zeichenkette durch eine echt längere ersetzt wird. Solche Grammatiken heißen wachsend kontextsensitive Grammatiken, die durch sie erzeugten Sprachen wachsend kontextsensitive Sprachen ([DW86], [Jan92]). Elias Dahlhaus und Manfred Warmuth wiesen in [DW86] nach, daß jede wachsend kontextsensitive Sprache mit Hilfe eines Kellerautomaten mit zusätzlichem logarithmisch platzbeschränktem Arbeitsband in polynomieller Zeit erkannt werden kann. Dabei darf man sogar verlangen, daß in der Eingabe nicht ”zurückgeblättert“ wird ([Bun93]). Genauer gilt, daß man jede wachsend kontextsensitive Sprache mit Hilfe von logarithmischem Platz in eine kontextfreie transformieren kann; auch dabei kann auf das ”Zurückblättern“ verzichtet werden ([Lau88], [Bun93]). Daraus folgern wir, daß unter diesem Gesichtspunkt die wachsend kontextsensitiven Sprachen von derselben Komplexität wie die kontextfreien Sprachen sind. Andererseits sind die wachsend kontextsensitiven Sprachen mächtiger als die kontextfreien ([DW86]).

Um zu einer anderen Einschränkung kontextsensitiver Grammatiken zu kommen, übertrugen Gerhard Buntrock und Krzysztof Lorys̀ in [BL92] die Idee von Bewertungsfunktionen aus der Theorie der Termersetzungssysteme (siehe dazu [BO93], [Jan88]) auf Grammatiken: Eine kontextsensitive Grammatik heißt quasi wachsend kontextsensitiv, falls es eine Zeichenbewertung gibt, die jedem Zeichen der Grammatik ein Gewicht so zuordnet, daß in jeder Regel die Summe aller Gewichte auf der linken Seite kleiner ist als die der Zeichen auf der rechten. In [BL92] wurde nun gezeigt, daß die quasi wachsend kontextsensitiven Grammatiken gerade die Klasse der wachsend kontextsensitiven Sprachen charakterisieren. Dies gilt auch, wenn man auf die Bedingung der Kontextsensitivität verzichtet ([BL92]). Erlaubt man allerdings, daß die Summe aller Gewichte der Zeichen auf beiden Seiten einer Regel gleich ist, so erhält man eine Charakterisierung der kontextsensitiven Sprachen ([BL94]).

Auf der Suche nach einer Sprachklasse, die zwischen den wachsend kontextsensitiven Sprachen und den kontextsensitiven Sprachen liegt, aber immer noch in Polynomialzeit erkennbar ist, schlug Gerhard Buntrock 1992 Stellenbewertungen zusätzlich zur reinen Zeichenbewertung vor. Dabei werden den Positionen von Zeichen innerhalb der Regeln Werte zugewiesen. Die Bewertung einer Regelseite ergibt sich aus der Summe über die Produkte aus der Zeichenbewertung der Zeichen und der Stellenbewertung der Position, auf der sie stehen. Eine nichtverkürzende Grammatik heißt schwach wachsend kontextsensitiv bezüglich einer Stellenbewertung, falls es eine Zeichenbewertung gibt, die den Zeichen Gewichte so zuordnet, daß für jede Regel die Bewertung der linken Seite kleiner ist als die der rechten.

Die schwach wachsend kontextsensitiven Grammatiken bezüglich solcher Stellenbewertungen, die sich als Exponentialfunktion zur Basis zwei schreiben lassen, wurden von Carmen Schwenkel in [Sw93] untersucht. Dabei stellte sich heraus, daß in solchen schwach wachsend kontextsensitiven Grammatiken exponentiell lange Ableitungen (im Verhältnis zur Länge des erzeugten Wortes) vorkommen können. Also kann sich beim Erkennen einer solchen Sprache durch einen linear beschränkten Automaten auch eine exponentielle Rechenzeit ergeben. Weiterhin stellte sich heraus, daß sich jede schwach wachsend kontextsensitive Grammatik bezüglich einer solchen Stellenbewertung umformen läßt in eine in Cremers-Normalform, die bezüglich derselben Stellenbewertung schwach wachsend kontextsensitiv ist.

In der vorliegenden Arbeit werden schwach wachsend kontextsensitive Sprachen bezüglich verschiedener Stellenbewertungen strukturiert und untersucht.

Wir unterscheiden zwischen gleichmäßigen Stellenbewertungen, deren Werte von einer Stelle zur nächsten stets um denselben Faktor anwachsen bzw. fallen (d.h. gleichmäßige Stellenbewertungen sind Anfangsstücke von Exponentialfunktionen), und ungleichmäßigen Stellenbewertungen sowie Stellenbewertungen mit Nullstellen, welche zum Teil gleichzeitig ungleichmäßig sind.

Es stellt sich heraus, daß die schwach wachsend kontextsensitiven Grammatiken bezüglich einer ungleichmäßigen Stellenbewertung gerade die kontextsensitiven Sprachen charakterisieren. Das hängt damit zusammen, daß in diesem Fall beliebig lange Ableitungen möglich sind. Ebenso führt der Fall, daß die Stellenbewertung eine Stelle mit Null bewertet, stets dazu, daß die bezüglich ihr schwach wachsend kontextsensitiven Grammatiken die kontextsensitiven Sprachen charakterisieren.

Im Gegensatz dazu ist die Anzahl der Ableitungsschritte in einer schwach wachsend kontextsensitiven Grammatik bezüglich einer gleichmäßigen Stellenbewertung (exponentiell) beschränkt. Denn eine wesentliche Eigenschaft jeder gleichmäßigen Stellenbewertung besteht darin, daß sie in eindeutiger Weise auf Satzformen und Terminalwörter fortsetzbar ist. Die Bewertung eines Terminalwortes führt dann zu einer natürlichen oberen Schranke der Ableitungslänge. Mit einer konstanten Stellenbewertung erhält man so genau die quasi wachsend kontextsensitiven Grammatiken. Außerdem ergibt sich, daß jede schwach wachsend kontextsenistive Grammatik, die gleichzeitig kontextsensitiv im klassischen Sinne ist, eine wachsend kontextsensitive Sprache liefert.

Halten wir nun eine gleichmäßige nichtkonstante Stellenbewertung fest. Die Ableitungslänge in jeder schwach wachsend kontextsensitiven Grammatik bezüglich dieser Stellenbewertung ist also exponentiell beschränkt. Man kann mit solchen Grammatiken jede kontextsensitive Grammatik, deren Ableitungslänge exponentiell mit einem kleineren Faktor im Exponenten beschränkt ist, simulieren. Andererseits ist jede schwach wachsend kontextsensitive Sprache ja auch kontextsensitiv. In diesem Sinne charakterisiert die Hierarchie der schwach wachsend kontextsensitiven Sprachen bezüglich gleichmäßiger nichtkonstanter Stellenbewertungen die exponentielle Zeithierarchie der kontextsensitiven Sprachen.

Weiterhin kann man mit der oben angewandten Simulationsmethode zeigen: Für jede kontextsensitive Sprache und jede gleichmäßige Stellenbewertung gibt es einen Homomorphismus, so daß das Bild der kontextsensitiven Sprache unter diesem Homomorphismus eine bezüglich dieser Stellenbewertung schwach wachsend kontextsensitive Sprache ist.

Außerdem läßt sich das Ergebnis aus [Sw93] über die Cremers-Normalform auf alle gleichmäßigen nichtkonstanten Stellenbewertungen übertragen. Für ungleichmäßige Stellenbewertungen bleibt diese Frage hier offen. Allerdings zeigt sich: Genau dann, wenn sich jede schwach wachsend kontextsensitive Grammatik bezüglich einer festen ungleichmäßigen Stellenbewertung in Cremers-Normalform überführen läßt, kollabiert auch die exponentielle Zeithierarchie der kontextsensitiven Sprachen. Das hängt damit zusammen, daß in Grammatiken in Cremers-Normalform in jeder Regel maximal zwei Symbole durch maximal zwei Symbole ersetzt werden. Stellenbewertungen für solche Regeln lassen sich stets gleichmäßig fortsetzen.

Grundlagen

1.1 Grammatiken

Es wird vorausgesetzt, daß der Leser vertraut ist mit den Grundlagen der Theorie Formaler Sprachen. Es sollen hier nur einige für diese Arbeit grundlegende Schreibweisen in Erinnerung gerufen werden (vgl. [Sal78], [WW86]).

Eine Grammatik oder auch allgemeine Grammatik ist ein Quadrupel ⟨N, T, S, P ⟩ mit endlichen disjunkten Alphabeten N (Menge der Nichtterminale) und T (Menge der Terminale), einem Startsymbol S ∈ N und einer endlichen Menge P von Regeln (Produktionen) der Form α → β mit α, β ∈ (N ∪ T)^{∗}, wobei α wenigstens ein Nichtterminal enthält.

Ein Element w ∈ T^{∗} nennt man Wort, ein Element v ∈ (N ∪ T)^{∗} eine Satzform. Das leere Wort wird mit ε bezeichnet. Sind u, v ∈ (N ∪ T)^{∗} Satzformen, so heißt v aus u direkt erzeugbar (oder direkt ableitbar) in G, in Zeichen u ⟹_{G} v, falls es eine Regel r ∈ P gibt, so daß durch Anwendung von r auf u die Satzform v entsteht. Es heißt v aus u erzeugbar (oder ableitbar) in G, in Zeichen u ⟹^{∗}_{G} v, falls es eine Folge von Satzformen v_{0} = u, v_{1}, v_{2}, …, v_{m} = v ∈ (N ∪ T)^{∗} gibt, so daß gilt:

v_{0} ⟹_{G} v_{1} ⟹_{G} v_{2} ⟹_{G} … ⟹_{G} v_{m}, oder falls u = v.

Ist aus dem Zusammenhang eindeutig ersichtlich, innerhalb welcher Grammatik abgeleitet wird, so wird statt u ⟹_{G} v auch u ⟹ v und statt u ⟹^{∗}_{G} v auch u ⟹^{∗} v geschrieben.

Die Sprache L(G) einer Grammatik G = ⟨N, T, S, P ⟩ ist die Menge aller Wörter, die durch Anwendungen von Regeln aus P aus dem Startsymbol S abgeleitet werden können, also L(G) = {w ∈ T^{∗} | S ⟹^{∗}_{G} w}, und wir sagen, G erzeugt die Sprache L(G).

Für eine endliche Menge M bezeichnet |M| die Anzahl der Elemente in M, und für eine Zeichenkette z bezeichnet |z| die Länge von z. Weiterhin nennt man die Länge der längsten Regelseite

ord(G) = max {max {|α|, |β|} | (α → β) ∈ P }

die Ordnung einer Grammatik G.

Eine Grammatik G = ⟨N, T, S, P ⟩ heißt kontextsensitiv, falls für jede Regel (α → β) ∈ P gilt: |α| ≤ |β| oder (α → β) = (S → ε), und falls (S → ε) ∈ P, so taucht S in keiner Regel aus P auf der rechten Seite auf.^{1} Die Menge aller kontextsensitiven Grammatiken wird mit CSG , die aller kontextsensitiven Sprachen mit CSL bezeichnet.

1Üblicherweise fordert man hier, daß sämtliche Regeln von der Form wXz → wyz mit w, y, z ∈ (N ∪ T)^{∗}, X ∈ N, y ≠ ε sind (mit der gleichen Regelung für (S → ε) wie oben). Beide Charakterisierungen führen zur selben Sprachklasse ([Cho59], nachzulesen in [Sal78], S. 82).

Grammatiken, bei denen α ∈ N für jede Regel (α → β) ∈ P gilt, heißen kontextfrei. Die Menge aller kontextfreien Grammatiken wird mit CFG , die aller kontextfreien Sprachen mit CFL bezeichnet. Schränkt man die Regeln (α → β) ∈ P noch weiter ein, so daß β ∈ NT^{∗}, dann erhält man die regulären Grammatiken. Die durch sie erzeugbaren Sprachen werden als reguläre Sprachen oder auch als reguläre Mengen bezeichnet, die Menge aller regulären Sprachen nennt man REG .

Ersetzt man in der Definition der kontextsensitiven Grammatiken die Ungleichung durch eine strikte, erhält man die wachsend kontextsensitiven Grammatiken (vgl. [DW86], [BL92], [Ni92]):

Definition 1.1.1 : Eine Grammatik G = ⟨N, T, S, P ⟩ heißt wachsend kontextsensitiv, wenn gilt:

• für jedes (α → β) ∈ P mit α, β ∈ (N ∪ T)^{∗} gilt:

|α| < |β| ∨ α = S, β ∈ N ∪ T ∪ {ε}

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

Die Menge der wachsend kontextsensitiven Grammatiken wird mit GCSG (engl: growing context-sensitive grammars) und die Menge der durch sie erzeugten Sprachen mit GCSL (engl: growing context-sensitive languages) bezeichnet.

Bemerkung: Es gilt CFL ⊂ GCSL ⊂ CSL ; die Inklusionen sind echt. ([DW86], siehe auch [Ni92])

Nun kann man die in einer Regel auftauchenden Nichtterminale und Terminale auch gewichten (oder bewerten), statt sie nur zu zählen. Das führt zu einer anderen Klasse von Grammatiken ([BL92]):

Definition 1.1.2 : Eine Grammatik G = ⟨N, T, S, P ⟩ heißt quasi wachsend kontextsensitiv, falls gilt:

• G ist kontextsensitiv

• es gibt eine Funktion f: N ∪ T → IN , so daß für jede Regel (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P gilt:

∑_{i=1}^{n} f(α_{i}) < ∑_{i=1}^{m} f(β_{i})

oder α = S, β = ε.

Die Menge aller quasi wachsend kontextsensitiven Grammatiken heißt QGCSG (engl: quasi growing context-sensitive grammars). Die Funktion f nennt man Zeichenbewertung für G.

Verzichtet man in Definition 1.1.2 auf die Forderung der Kontextsensitivität, fordert aber weiterhin von G = ⟨N, T, S, P ⟩, daß falls (S → ε) ∈ P, so taucht S in keiner Regel auf der rechten Seite auf, so erhält man die quasi wachsenden Grammatiken, und die Menge aller solchen heißt QGG (engl: quasi growing grammars).

In [BL92] wurde gezeigt, daß sowohl die quasi wachsenden Grammatiken als auch die quasi wachsend kontextsensitiven Grammatiken gerade die Klasse der wachsend kontextsensitiven Sprachen charakterisieren (auch nachzulesen in [Ni92]).

Das heißt, indem den Nichtterminalen und Terminalen einer (nicht notwendig kontextsensitiven) Grammatik Gewichte zugeordnet werden und verlangt wird, daß in jeder Regel die Summe der Gewichte der Zeichen auf der rechten Seite echt größer ist als die der Zeichen auf der linken, erhält man eine Sprachklasse, die echt zwischen CFL und CSL liegt, nämlich GCSL .

Nun kann man statt der einzelnen Zeichen selbst auch noch die Stelle bewerten, an der sie innerhalb einer Regel stehen. Eine Stellenbewertung soll mindestens eine Stelle tatsächlich bewerten, keine Bewertungslücken haben, weil sonst die Bewertung einer Regel nicht sinnvoll definiert werden kann, und nicht identisch 0 sein.

Definition 1.1.3 : Eine Stellenbewertung ist eine Funktion s: IN^{+} → IN , für die gilt:

Ist s für ein j ∈ IN^{+} definiert, so ist s auch für jedes i ∈ IN^{+} mit i < j definiert, und es gibt ein i ∈ IN^{+} mit s(i) = c ≠ 0 mit c ∈ IN^{+}.

Ist s für alle i ∈ IN^{+} definiert, so sagen wir, s ist eine unendliche Stellenbewertung — im anderen Fall, s ist eine endliche Stellenbewertung. Wie nennen jedes i ∈ IN^{+}, für das s(i) definiert ist, eine bewertete Stelle von s, und im Falle einer endlichen Stellenbewertung nennen wir das größte solche i die letzte bewertete Stelle von s, und s heißt eine Stellenbewertung mit i bewerteten Stellen. Eine Stellenbewertung s heißt Stellenbewertung mit Nullstellen, falls es eine Stelle i ∈ IN^{+} gibt mit s(i) = 0. Andernfalls heißt s eine Stellenbewertung ohne Nullstellen oder auch nullstellenfrei. Eine Stellenbewertung s heißt konstant, falls es ein c ∈ IN^{+} gibt mit s(i) = c für alle bewerten Stellen i ∈ IN^{+} von s. Im anderen Fall heißt s nichtkonstant. Weiterhin heißt s (streng) monoton wachsend oder fallend, falls s auf ihren bewerteten Stellen diese Eigenschaft besitzt.

Definition 1.1.4 : Sei s eine Stellenbewertung. Eine Grammatik G = ⟨N, T, S, P ⟩ heißt schwach wachsend kontextsensitiv bezüglich der Stellenbewertung s oder auch s-schwach wachsend kontextsensitiv, falls gilt:

(i) Für alle Regeln (α → β) ∈ P gilt: |α| ≤ |β| ∨ (α → β) = (S → ε) und falls (S → ε) ∈ P, so taucht S in keiner Regel auf der rechten Seite auf. (Mit anderen Worten: G ist kontextsensitiv.)^{2}

(ii) Falls s endlich ist: Ist l die Ordnung von G und j die letzte bewertete Stelle von s, so gilt l ≤ j.

2Mit der in der Fußnote auf Seite 7 erwähnten Definition kontextsensitiver Grammatiken erhält man andere als die hier definierten Sprachklassen, siehe Kapitel 5.3, Satz 5.3.2.

(iii) Es gibt eine Funktion f: N ∪ T → IN , so daß für jede Regel (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P gilt:

∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i})

oder α = S, β ∈ T^{∗} mit |β| < k mit k = min{i ∈ IN^{+} | s(i) ≠ 0}.

Eine solche Funktion f heißt Zeichenbewertung für G. Die Auswertung des Ausdrucks auf der linken bzw. der rechten Seite der Ungleichung wird als Bewertung der linken bzw. rechten Seite der Regel α → β bezeichnet. Ist die Ungleichung erfüllt, so wird die Regel (α → β) s-schwach wachsend mit f genannt.

Die Menge aller schwach wachsend kontextsensitiven Grammatiken bezüglich einer Stellenbewertung s heißt WGCSG_{s} (engl: weak growing context-sensitive grammars), die Menge der durch sie erzeugten Sprachen WGCSL_{s} (engl: weak growing context-sensitive languages).

Eine Grammatik G = ⟨N, T, S, P ⟩ ist also genau dann s-schwach wachsend kontextsensitiv, wenn sie kontextsensitiv ist, die Ordnung von G nicht die Anzahl der durch s bewerteten Stellen übersteigt und es eine Zeichenbewertung f: N ∪ T → IN gibt, so daß alle Regeln aus P s-schwach wachsend mit dieser Funktion f sind. Dabei bewirkt die letzte Bedingung in Definition 1.1.4 (iii), daß auch falls die Stellenbewertung auf einem Anfangsstück konstant 0 ist, kurze Wörter erzeugt werden können.

Definition 1.1.5 : Eine Grammatik G, zu der es eine Stellenbewertung s gibt, so daß G ∈ WGCSG_{s} ist, heißt schwach wachsend kontextsensitive Grammatik. Eine Sprache L, für die es eine schwach wachsend kontextsensitive Grammatik G gibt, die L erzeugt, heißt schwach wachsend kontextsensitive Sprache.

Indem nun zusätzlich die Stellung eines Zeichens innerhalb einer Regel bewertet wird, ist es auch möglich, zwei Zeichen durch eine Regel einfach zu vertauschen. Das kann man benutzen, um zu zeigen, daß die Sprache W W := {ww | w ∈ {a, b}^{∗}} schwach wachsend kontextsensitiv bezüglich einer beliebigen nichtkonstanten Stellenbewertung ist (siehe [Sw93]). Um eine Intuition für schwach wachsend kontextsensitive Grammatiken zu vermitteln, wollen wir dieses Beispiel hier explizit ausführen:

Beispiel 1.1.6 : [Sw93] Betrachte also die Sprache W W := {ww | w ∈ {a, b}^{∗}}. Sei s eine beliebige Stellenbewertung mit wenigstens zwei bewerteten Stellen und s(1) < s(2). Definiere eine Grammatik G = ⟨N, {a, b}, S, P ⟩ durch:

N = {S, A, A′, B, B′, (X, a), (X, b)}

und P bestehend aus den folgenden Regeln:

\begin{matrix}S → AA′S & S → BB′S & S → A(X, a) & S → B(X, b) \\ A′A → AA′ & A′B → BA′ & B′A → AB′ & B′B → BB′ \\ A′(X, a) → (X, a)a & A′(X, b) → (X, a)b & B′(X, a) → (X, b)a & B′(X, b) → (X, b)b \\ (X, a) → a & (X, b) → b & A → a & B → b \end{matrix}

Diese Grammatik ist kontextsensitiv, von der Ordnung 2 und erzeugt die Sprache W W. Sei nun f: N ∪ T → IN definiert durch:

\begin{matrix}f(S) = f(A) = f(B) = f((X, a)) = f((X, b)) = 1 \\ f(A′) = f(B′) = 2, f(a) = f(b) = 2 \end{matrix}

Durch einfaches Nachrechnen erkennt man, daß sämtliche Regeln aus P schwach wachsend mit dieser Zeichenbewertung sind. Also ist die Grammatik G s-schwach wachsend kontextsensitiv.

Es ist W W ∉ GCSL ([Bun93]), und damit also WGCSL_{s} ⊈ GCSL für jede nichtkonstante Stellenbewertung s.

Eine Berechtigung für die Definition 1.1.4 liefert der folgende Satz, dessen Beweis eine Intuition über die Grenzen der Möglichkeiten schwach wachsend kontextsensitiver Grammatiken vermittelt.

Satz 1.1.7 : [Sw92] Es gibt eine Grammatik G ∈ CSG so, daß für alle Stellenbewertungen s gilt: G ∉ WGCSG_{s}.

Beweis: Sei G = ⟨N, T, S, P ⟩ eine kontextsensitive Grammatik mit {A, B} ⊆ N, und P enthalte die folgenden Regeln:

\begin{matrix}(1) & AB → BA \\ (2) & BA → AB \end{matrix}

Sei s eine beliebige Stellenbewertung. Für eine Zeichenbewertung f für G muß gelten:

s(1) · f(A) + s(2) · f(B) < s(1) · f(B) + s(2) · f(A) wegen Regel (1)

und gleichzeitig

s(1) · f(B) + s(2) · f(A) < s(1) · f(A) + s(2) · f(B) wegen Regel (2)

Das ist aber unmöglich. ♣

Also gibt es kontextsensitive Grammatiken, die nicht schwach wachsend kontextsensitiv sind.

Für eine genauere Einordnung schwach wachsend kontextsensitiver Sprachen bezüglich verschiedener Stellenbewertungen konzentrieren wir uns auf Stellenbewertungen ohne Nullstellen, da die Einordnung für Stellenbewertungen mit Nullstellen sich mit den dabei angewandten Techniken ergibt (siehe Kapitel 5.1).

Bezüglich einer Stellenbewertung, die auf allen ihren bewerteten Stellen den Wert 0 annimmt, sind laut Definition nur endliche Sprachen schwach wachsend kontextsensitiv. Deshalb wollen wir solche Stellenbewertungen nicht weiter betrachten. Da bezüglich Stellenbewertungen mit nur einer bewerteten Stelle nur Sprachen mit einbuchstabigen Wörtern schwach wachsend kontextsensitiv sind, wollen wir auch diese Stellenbwertungen nicht weiter betrachten.

Wie oben schon erwähnt, hat sich für quasi wachsend kontextsensitive Grammatiken gezeigt, daß man durch den Verzicht auf die Eigenschaft der Kontextsensitivität Grammatiken erhält, die wieder dieselbe Sprachklasse GCSL charakterisieren ([BL92]).

Im Fall schwach wachsend kontextsensitiver Grammatiken ist dies nicht so: Verzichtet man in Definition 1.1.4 auf die Forderung der Kontextsensitivität, erhält man die quasi schwach wachsenden Grammatiken (vgl. [Sw93]), die bereits die durch allgemeine Grammatiken erzeugbaren Sprachen charakterisieren ([Nie]).

1.2 Turingmaschinen und linear beschränkte Automaten

Es wird vorausgesetzt, daß der Leser vertraut ist mit dem Aufbau und der Arbeitsweise von Turingmaschinen. Es sollen hier nur grundlegende Schreibweisen und Eigenschaften in Erinnerung gerufen und einige Vereinbarungen getroffen werden; insbesondere werden wir uns auf Einband-Maschinen ohne extra Eingabeband beschränken. Für genauere Informationen über Turingmaschinen wird der interessierte Leser auf [HU79], [Har78] verwiesen.

Eine Turingmaschine, wie wir sie verwenden wollen, besitzt ein unendliches Arbeitsband, auf dem zu Beginn die Eingabe steht, einen Schreib-/Lesekopf sowie eine endliche Kontrolle, die sich immer in genau einem von endlich vielen Zuständen befindet. Zu Beginn der Berechnung steht die Eingabe auf dem Band, links und rechts davon Blanksymbole, der Schreib-/Lesekopf steht auf dem linkesten Symbol der Eingabe. Der Kopf darf sich in jedem Schritt um ein Feld nach rechts oder links bewegen oder auch stehenbleiben und steht, falls die Turingmaschine hält, am Ende der Berechnung rechts neben dem letzten beschriebenen Feld.

Formal wird eine (nichtdeterministische) Turingmaschine beschrieben durch ein 7-Tupel M = (Q, Σ, Γ, □, δ, q_{0}, F) (vgl. [HU79], S. 148, [Har78], S. 280), wobei Q die endliche Zustandsmenge, Σ das endliche Eingabealphabet, Γ mit Σ ⊆ Γ das endliche Arbeitsalphabet, □ ∈ Γ \ Σ das Blanksymbol, δ die Übergangsfunktion, q_{0} den Startzustand und F die Menge der Endzustände bezeichnet.

Eine Konfiguration einer Turingmaschine M = (Q, Σ, Γ, □, δ, q_{0}, F) wird beschrieben durch α_{1}qα_{2} mit α_{1}, α_{2} ∈ Γ^{∗}, q ∈ Q. Dabei bezeichnet α_{1}α_{2} den aktuellen Bandinhalt vom linkesten Zeichen ungleich dem Blanksymbol oder dem Zeichen, welches der Kopf gerade liest, je nachdem, welches von beiden weiter links ist, bis zum rechtesten Zeichen ungleich dem Blanksymbol oder dem Zeichen, welches der Kopf gerade liest, je nachdem, welches von beiden weiter rechts ist. Weiter bezeichent q den aktuellen Zustand, und das erste Zeichen von α_{2} beschreibt das Feld des Bandes, welches der Kopf gerade liest. Falls α_{2} = □, liest M gerade das Blanksymbol. Zum Beispiel beschreibt q□ eine Konfiguration mit leerem Band.

Eine Konfiguration q_{0}w mit w ∈ Σ^{∗} heißt Startkonfiguration, eine Konfiguration vq_{F} □ mit v ∈ Γ^{∗}, q_{F} ∈ F heißt akzeptierende Konfiguration.

Sind K und K′ Konfigurationen von M, so heißt K′ erreichbar von K oder auch K überführbar in K′, in Zeichen K _{M}^{∗} K′, wenn es eine Berechnung von M gibt, die K in endlich vielen Schritten in K′ überführt.

Ist aus dem Zusammenhang eindeutig ersichtlich, welche Turingmaschine betrachtet wird, so schreibt man statt K _{M}^{∗} K′ auch K ^{∗} K′.

Die von einer Turingmaschine M = (Q, Σ, Γ, □, δ, q_{0}, F) erkannte Sprache L(M) ist die Menge aller Wörter aus Σ^{∗}, für die von der Startkonfiguration aus eine akzeptierende Konfiguration erreicht werden kann, also

L(M) = {w ∈ Σ^{∗} | q_{0}w _{M}^{∗} vq_{F} □, v ∈ Γ^{∗}, q_{F} ∈ F }

Eine Sprache L heißt rekursiv aufzählbar (engl: recursive enumerable), falls es eine Turingmaschine M gibt mit L(M) = L. Hierbei stellt die Beschränkung auf Einband-Turingmaschinen ohne extra Eingabeband keine Einschränkung dar; die Menge der Mehrband-Turingmaschinen mit extra Eingabeband charakterisiert ebenfalls die Klasse der rekursiv aufzählbaren Sprachen ([HU79], [Har78]). Die Menge der rekursiv aufzählbaren Sprachen wird ebenfalls durch die allgemeinen Grammatiken charakterisiert ([Har78], [HU79]).

Seien S: IN → IN und T: IN → IN Funktionen.

Eine Turingmaschine M heißt S(n)-platzbeschränkt, falls sie für jedes akzeptierte Eingabewort der Länge n einen akzeptierenden Rechenweg besitzt, auf dem sie höchstens S(n) Felder betritt, und man sagt dann, M erkennt die Sprache L(M) auf dem Platz S(n). Eine Turingmaschine M heißt T (n)-zeitbeschränkt, falls sie für jedes akzeptierte Eingabewort der Länge n einen akzeptierenden Rechenweg besitzt, auf dem sie höchstens T (n) Schritte rechnet, und man sagt dann, M erkennt die Sprache L(M) in der Zeit T (n). (Siehe [HU79], S. 285ff, [Har78], S. 283f).

Die entsprechenden Sprachklassen werden mit T –NSPACE (S(n)) bzw. T –NTIME (T (n)) bezeichnet ([WW86]), dabei weist das ”T –“ darauf hin, daß es sich um eine Einband-Turingmaschine ohne extra Eingabeband handelt, was für alle Zeitbetrachtungen und sublineare Platzbeschränkungen eine wichtige Rolle spielt ([HU79], [WW86] und zahlreiche andere)^{3}. Man nennt eine Sprache L ∈ T –NSPACE (S(n)) erkennbar auf dem Platz S(n), und eine Sprache L ∈ T –NTIME (T (n)) erkennbar in der Zeit T (n).

Weiterhin bezeichnet T –NSPACE-TIME (S(n), T (n)) die Klasse aller Sprachen L, für die es eine Turingmaschine M gibt, die L auf Platz S(n) und zugleich in der Zeit T (n) erkennt (siehe [WW86]). Diese Klasse ist im allgemeinen kleiner als der Schnitt von T –NSPACE (S(n)) und T –NTIME (T (n)).

Es ist bekannt, daß man ohne Beschränkung der Allgemeinheit annehmen kann, daß der Schreib-/Lesekopf einer Turingmaschine während der Berechnung nicht stehenbleibt und sich die Rechenzeit dann im Verhältnis zu allgemeinen Turingmaschinen höchstens verdoppelt ([Tur36]).

Ein linear beschränkter Automat ist eine Turingmaschine, die auf dem Platz S(n) = n arbeitet. Wir beschränken uns auch hier auf das Einband-Modell, was aber nur für angestrebte Zeitschranken von Bedeutung ist, nicht aber für die Klasse der überhaupt von linear beschränkten Automaten erkennbaren Sprachen. Die Menge der durch einen linear beschränkten Automaten erkennbaren Sprachen ist also T –NSPACE (n) = NSPACE (n). Wie wir nach def Definition 1.2.1 erwähnen, gilt sogar eine etwas stärkere Aussage.

Nun wollen wir noch die O-Notation für Funktionen nach [Knu76] definieren:

Definition 1.2.1 : Sei f: IN → IN eine Funktion. Dann bezeichnet O (f(n)) die Menge aller Funktionen g: IN → IN , für die ein c ∈ IN und ein n_{0} ∈ IN existieren, so daß für alle n ≥ n_{0} gilt:

|g(n)| ≤ c · f(n)

In diesem Sinne bezeichnet also T –NSPACE-TIME (n, O (T (n))) die Menge aller Sprachen L, für die es einen nichtdeterministischen linear beschränkten Automaten M gibt, der L erkennt und für den gilt:

Es gibt Konstanten c, n_{0} ∈ IN , so daß für jedes Eingabewort w ∈ L mit |w| ≥ n_{0} gilt: M akzeptiert die Eingabe w nach höchstens c · T (|w|) Schritten.

3z.B. ist Q = multiT–NTIME (O(n)), die Klasse aller Sprachen, die mit Mehrband-Turingmaschinen nichtdeterministisch in Linearzeit erkennbar sind, nicht dieselbe wie T –NSPACE-TIME (n, O(n)), die Klasse aller Sprachen, die in Linearzeit mit Einband-Turigmaschinen erkennbar sind.

(Gladkij in [Gla64]: W W^{T} W = {ww^{T} w | w ∈ Σ^{∗}} ∉ CSL _{lin}, die Menge aller kontextsensitiven Sparchen mit linearer Ableitungslänge)

Analoges gilt für T –NSPACE (O(n)). Außerdem gilt: T –NSPACE (O(n)) = NSPACE (n) (folgt z.B. aus [HU79], Satz 12.1, S. 288f) (Stichwort: lineare Bandkompression). Der Beweis läßt sich direkt übertragen, um zu zeigen, daß es zu jedem linear beschränkten Automaten M einen linear beschränkten Automaten M′ gibt, der eine linear komprimierte Version von L(M) erkennt. Um dies als Satz zu formulieren (da wir diese Kompression in den Kapiteln 3.2 und 4.3 verwenden werden) noch eine Definition:

Definition 1.2.2 : Für ein Menge von Zeichen Σ und k ∈ IN^{+} bezeichne

Σ^{k} = {(a_{1}, …, a_{k}) | a_{i} ∈ Σ für i ∈ {1, …, k}}

Σ^{≤k} = ⋃_{1≤j≤k} Σ^{j} Σ^{∞} = ⋃_{k∈IN^{+}} Σ^{k}

Definiere eine Abbildung nat: Σ^{∞} → Σ^{∗} durch:

für alle α ∈ Σ^{∞}, α = (a_{1}, …, a_{k}) ist nat(α) = a_{1} … a_{k}

und deren Fortsetzung auf (Σ^{∞})^{∗}, welche wieder nat heißen soll, durch:

für alle α_{1}, …, α_{n} ∈ Σ^{∞} ist nat(α_{1} … α_{n}) = nat(α_{1}) · . . . · nat(α_{n}) und nat(ε) = ε

Es gilt also:

Satz 1.2.3 : Sei M = (Q, Σ, Γ, □, δ, q_{0}, F) ein linear beschränkter Automat, der die Sprache L in der Zeit d · 2^{c·n} für c, d ∈ IN erkennt. Dann existiert ein linear beschränkter Automat M_{k} = (Q_{k}, Σ_{k}, Γ_{k}, □_{k}, δ_{k}, q_{0,k}, F_{k}) der die Sprache

L_{k} := {w ∈ (Σ^{k})^{∗} · Σ^{≤k} | nat(w) ∈ L}

erkennt. Dabei ist Σ_{k} = Σ^{≤k}, und für ein Wort w ∈ L_{k} arbeitet M_{k} auf dem Platz |w| = ⌈\frac{|nat(w)|}{k}⌉ und in der Zeit d · 2^{c·|nat(w)|} ≤ d · 2^{c·k·|w|}, also in derselben ”absoluten“ Zeit.

Bemerkung: Weiterhin gilt:

NSPACE (n) = ⋃_{c∈IN^{+}} T –NSPACE-TIME (n, O (2^{c·n})) = ⋃_{c∈IN^{+}} T –NSPACE-TIME (n, 2^{c·n})

(siehe [WW86], S. 76).

Robustheit, Abschluß und Normalform

2.1 Robustheit

Wir wollen zunächst verschiedene Robustheitseigenschaften der schwach wachsend kontextsensitiven Sprachen ausarbeiten.

Man kann zu jeder allgemeinen, kontextsensitiven oder kontextfreien Grammatik eine gleichwertige Grammatik gleichen Typs finden, in der jede Regel, in der ein Terminal auftaucht, von der Form A → a, A Nichtterminal, a Terminal, ist (siehe [Sal78], [Har78]).

Das kann man auch für schwach wachsend kontextensitive Grammatiken bezüglich einer beliebigen Stellenbewertung mit s(1) ≠ 0 zeigen (vgl. [Sw93]):

Satz 2.1.1 : Sei s eine Stellenbewertung mit s(1) ≠ 0. Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Dann gibt es eine Grammatik G′ = ⟨N′, T, S, P′⟩ mit G′ ∈ WGCSG_{s}, L(G′) = L(G), und in P′ tauchen Terminale nur in Regeln der Form A → a, A ∈ N′, a ∈ T auf.

Beweis: Sei s eine Stellenbewertung mit s(1) ≠ 0. Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}, sei f eine Zeichenbewertung für G.

Definiere G′ durch N′ := N ∪ T′, wobei T′ = {a′ | a ∈ T } aus neuen Symbolen, den Kopien der Elemente aus T, besteht. Die Regeln aus P′ erhält man aus den Regeln aus P, indem man jedes Terminal a durch seine Kopie a′ ersetzt und dann die Regeln {a′ → a | a ∈ T } hinzunimmt. Dann erzeugen G und G′ nach [Sal78], S. 19 dieselbe Sprache und G′ ∈ CSG . Die Ordnung von G′ ist sicher nicht größer als die von G.

G′ ∈ W GCSG_{s} sieht man nun mit folgender Zeichenbewertung f′: N′ ∪ T → IN für G′:

f′(A) = f(A)  für alle A ∈ N
f′(a′) = f(a)  für alle a′ ∈ T′
f′(a) = f(a) + 1 für alle a ∈ T

Alle Regeln aus P′, die aus Regeln aus P hervorgegangen sind, werden also bewertet wie diese und sind damit sicherlich s-schwach wachsend mit f′. Für die Regeln (a′ → a) ∈ P′, a′ ∈ T′ gilt (wegen s(1) > 0):

s(1) · f′(a′) = s(1) · f(a) < s(1) · (f(a) + 1) = s(1) · f′(a)

und damit sind auch diese Regeln s-schwach wachsend mit f′. ♣ In allgemeinen, kontextsensitiven oder kontextfreien Grammatiken kann man Kettenregeln, also Regeln der Form A → B, eliminieren ([Har78]). Auf die gleiche Weise wie für die genannten Grammatiktypen kann man das auch bei schwach wachsend kontextsensitiven Grammatiken. Und zwar auch, wenn man für eine gegebene Stellenbewertung und eine kontextsensitive Grammatik mit passender Ordnung nur eine Zeichenbewertung vorliegen hat, die für einige Kettenregeln die Zeichen rechts und links gleich bewertet.

Satz 2.1.2 : Sei s eine Stellenbewertung. Sei G = ⟨N, T, S, P ⟩ eine Grammatik, für die die Bedingungen (i) und (ii) aus Definition 1.1.4 erfüllt sind und für die es außerdem eine Funktion f: N ∪ T → IN gibt mit: Für jede Regel (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P gilt eine der folgenden Bedingungen:

a)  ∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i}) ∧ m ≥ 2 oder (α → β) = (S → ε)

b)  n = 1, m = 1, α_{1} ∈ N, β_{1} ∈ N ∪ T und f(α_{1}) ≤ f(β_{1})

Das heißt G besitzt Kettenregeln, und f bewertet in diesen Regeln das Zeichen rechts wenigstens so hoch wie das Zeichen links. Dann gibt es eine Grammatik G′ = ⟨N, T, S, P′⟩ ∈ WGCSG_{s}, in der keine Kettenregeln vorkommen, mit L(G) = L(G′), und f ist Zeichenbewertung für G′.

Beweis: Seien alle Voraussetzungen des Satzes erfüllt. P′ wird nun nach folgendem Algorithmus konstruiert:

1. P′ := {(α → β) ∈ P | (α → β) erfüllt Bed. a) }

2. Für jede Regel (A → B) ∈ P mit A ∈ N, B ∈ N ∪ T wiederhole:

für jede Regel

(∗) (α_{1} … α_{n} → β_{1} … β_{i−1}Aβ_{i+1} … β_{m}) ∈ P′ füge die Regel

(∗′) (α_{1} … α_{n} → β_{1} … β_{i−1}Bβ_{i+1} … β_{m}) zu P′ hinzu.

Der Nachweis L(G′) = L(G) ist straight forward und soll hier nicht weiter ausgeführt werden (vgl. [Har78]). Außerdem ist G′ kontextsensitiv und von der gleichen Ordnung wie G.

In P′ kommen keine Regeln der Form b) vor, und alle in Schritt 2 hinzugekommenen Regeln (∗′) haben entweder die gleiche Bewertung wie die Regeln (∗), aus denen sie hervorgegangen sind, oder die Bewertung der rechten Seite ist gegenüber der der alten Regel noch angewachsen. Das heißt für sie gilt a).

Also ist f Zeichenbewertung für G′, in P′ gibt es keine Kettenregeln und G′ ∈ WGCSG_{s}. ♣

Nun wenden wir uns der Stellenbewertung zu. Wenn man sie ”abschneidet“, erhält man logischerweise eine Teilmenge der zuvor bezüglich dieser Stellenbewertung schwach wachsend kontextsensitiven Grammatiken.

Satz 2.1.3 : Sei s eine Stellenbewertung. Sei eine von s bewertete Stelle j ∈ IN^{+} gegeben. Definiere nun eine Stellenbewertung s′: IN^{+} → IN durch s′(i) = s(i) für alle i ≤ j, s′(i) sei nicht definiert für alle i > j. Dann gilt:

WGCSG_{s′} ⊆ WGCSG_{s}

und

[G ∈ WGCSG_{s} ∧ ord(G) ≤ j] ⇒ G ∈ WGCSG_{s′}

Beweis: folgt direkt aus Definition 1.1.4. ♣

Man kann eine Stellenbewertung auch um einen konstanten Faktor ”strecken“, ohne daß sich dadurch die Menge der bezüglich ihr schwach wachsend kontextsensitiven Grammatiken ändert.

Satz 2.1.4 : Seien k ∈ IN^{+} und s eine Stellenbewertung. Dann gilt: WGCSG_{s} = WGCSG_{k·s} .

Beweis: Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} . Dann ist jede bewertete Stelle von s auch eine bewertete Stelle von k · s und umgekehrt. Also ist die letzte bewertete Stelle von s auch die letzte bewertete Stelle von k ·s. Sei j diese letzte bewertete Stelle. Es ist ord(G) ≤ j.

Es gibt eine Zeichenbewertung f: N ∪ T → IN für die Grammatik G, also gilt für alle Regeln (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P:

∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i})

Wegen k > 0 ist dies äquivalent zu

k · ∑_{i=1}^{n} s(i) · f(α_{i}) < k · ∑_{i=1}^{m} s(i) · f(β_{i})

⇔ ∑_{i=1}^{n} k · s(i) · f(α_{i}) < ∑_{i=1}^{m} k · s(i) · f(β_{i})

⇔ ∑_{i=1}^{n}(k · s)(i) · f(α_{i}) < ∑_{i=1}^{m}(k · s)(i) · f(β_{i})

Daraus folgt aber G ∈ WGCSG_{k·s}. Die Umkehrung folgt analog. ♣

Man könnte also auch Stellenbewertungen mit Werten aus Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} _{0}^{+} einführen, ohne dadurch neue Grammatikklassen zu erhalten.

Bemerkung: Sei C: IN^{+} → IN^{+} eine konstante Stellenbewertung mit wenigstens zwei bewerteten Stellen. Dann gilt WGCSG_{C} = QGCSG und folglich WGCSL_{C} = GCSL . Damit gilt Satz 2.1.2 auch für QGCSG .

Weiterhin kann man auch die Zeichenbewertung um einen konstanten Faktor ”strecken“, und man kann sie auch ”verschieben“, was zu folgendem Resultat führt:

Satz 2.1.5 : In Definition 1.1.4 (iii) genügt es, die Existenz einer Zeichenbewertung mit Werten aus Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} zu fordern.

Beweis: (vgl. [Sw93], Satz 2 und 3) Sei s eine Stellenbewertung, und sei G = ⟨N, T, S, P ⟩ eine Grammatik, die die Bedingungen (i) und (ii) in Definition 1.1.4 erfüllt und für die gilt:

(iii*) es gibt eine Funktion f: N ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} , so daß für alle Regeln (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P gilt:

(∗)  ∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i})

Es genügt zu zeigen: Dann gibt es auch eine Funktion g: N ∪ T → IN , die (∗) erfüllt. Sei N ∪ T =: {a_{1}, …, a_{k}}. Es ist f(a_{j}) = \frac{z_{j}}{n_{j}} mit geeigneten z_{j} ∈ ZZ, n_{j} ∈ IN^{+} für alle j = 1, …, k. Sei r = kgV(n_{1}, …, n_{k}), r_{j} = \frac{r}{n_{j}} (∈ ZZ), sei z = r · | min\{z_{1}, …, z_{k}, 0\}|. Dann ist

∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i})

gleichwertig mit

r · ∑_{i=1}^{n} s(i) · f(α_{i}) + ∑_{i=1}^{n} s(i) · z < r · ∑_{i=1}^{m} s(i) · f(β_{i}) + ∑_{i=1}^{n} s(i) · z

⇔ ∑_{i=1}^{n} s(i) · (r · f(α_{i}) + z) < ∑_{i=1}^{m} s(i) · r · f(β_{i}) + ∑_{i=1}^{n} s(i) · z

Daraus folgt wegen m ≥ n:

∑_{i=1}^{n} s(i) · (r · f(α_{i}) + z) < ∑_{i=1}^{m} s(i) · (r · f(β_{i}) + z)

Nun gilt aber für alle a_{j} ∈ N ∪ T:

r · f(a_{j}) + z = r · \frac{z_{j}}{n_{j}} + z = \frac{r}{n_{j}} · z_{j} + z = r_{j} · z_{j} + z ∈ ZZ

und dabei ist 0 ≤ r_{j} ≤ r, z ∈ IN . Falls z_{j} > 0, folgt r · f(a_{j}) + z ∈ IN . Falls z_{j} < 0, so folgt min{z_{1}, …, z_{k}, 0} ≤ z_{j}, also r · |z_{j}| ≤ z. Daraus folgt: r · f(a_{j}) + z ∈ IN . Das heißt, die Funktion g: N ∪T → IN definiert durch g(a_{j}) = r·f(a_{j})+z für jedes a_{j} ∈ N ∪T erfüllt (∗) und damit die Bedingung (iii) in Definition 1.1.4. ♣

2.2 Abschlußeigenschaften

Um eine Sprachklasse näher kennenzulernen, ist es sinnvoll, ihre Abschlußeigenschaften zu betrachten. Dazu erklären wir zunächst einige Operationen auf Sprachklassen:

Für zwei Sprachen L_{1} und L_{2} über ein Alphabet Σ sind

L_{1} ∪ L_{2} = {w ∈ Σ^{∗} | w ∈ L_{1} ∨ w ∈ L_{2}} die Vereinigung
L_{1} ∩ L_{2} = {w ∈ Σ^{∗} | w ∈ L_{1} ∧ w ∈ L_{2}} der Schnitt und
L_{1} · L_{2} = {w ∈ Σ^{∗} | w = uv mit u ∈ L_{1} ∧ v ∈ L_{2}} die Konkatenation

der Sprachen L_{1} und L_{2}.

Für ein Wort w = w_{1} … w_{n} mit Zeichen w_{i} aus einem Alphabet Σ für i = 1, …, n ist w^{T} = w_{n} … w_{1} die Transposition von w. Die Transposition einer Sprache L über ein Alphabet Σ ist erklärt durch L^{T} = {w ∈ Σ^{∗} | w^{T} ∈ L}.

Der Durchschnitt einer Sprachklasse C mit regulären Mengen ist erklärt durch:

{L̃ | L̃ = L_{1} ∩ L_{2} mit L_{1} ∈ C, L_{2} ∈ REG }

Ein Homomorphismus h: Σ^{∗} → Δ^{∗} ist eine Abbildung mit h(a) ∈ Δ^{∗} für alle a ∈ Σ und h(ab) = h(a)h(b) für alle a, b ∈ Σ, h(ε) = ε. Ein ε-freier Homorphismus ist ein Homomorphismus h: Σ^{∗} → Δ^{∗} mit h(a) ≠ ε für alle a ∈ Σ.

Ein inverser Homomorphismus h^{−}: Δ^{∗} → Σ^{∗} zu einem Homomorphismus h: Σ^{∗} → Δ^{∗} ist erklärt durch:

h^{−}(u) = {v ∈ Σ^{∗} | h(v) = u}

Ein Homomorphismus heißt k-beschränkt für eine Sprache L, falls gilt:

für jedes w ∈ L mit w = xyz mit x, y, z ∈ Σ^{∗} und h(y) = ε gilt: |y| ≤ k.

Sei Σ eine Zeichenmenge, seien Δ_{a} für jedes a ∈ Σ Zeichenmengen. σ heißt Substitution, falls gilt: Für jedes a ∈ Σ ist σ(a) ⊆ Δ_{a}^{∗} eine Sprache über Δ_{a}, σ(ε) = ε, und für alle a_{1}, …, a_{k} ∈ Σ ist σ(a_{1} … a_{k}) = σ(a_{1}) · . . . · σ(a_{k}). σ heißt ε-frei, falls σ(a) ≠ {ε} für alle a ∈ Σ, und σ heißt regulär, falls für jedes a ∈ Σ gilt: σ(a) ist eine reguläre Sprache. Für eine Sprache L ist σ(L) = {σ(w) | w ∈ L}.

Eine Sprachklasse heißt abgeschlossen unter einer Operation, falls diese Operation angewandt auf Sprachen dieser Klasse wieder zu einer Sprache aus dieser Klasse führt.

Der Abschluß einer Sprachklasse C unter einer Operation ist die kleinste Sprachklasse, die C enthält und abgeschlossen unter dieser Operation ist.

Anmerkung: Um nachzuweisen, daß eine Sprachklasse D der Abschluß einer Sprachklasse C unter inversen Homomorphismen ist, genügt es zu zeigen, daß es zu jeder Sprache L ∈ D einen Homomorphismus h gibt mit h(L) ∈ C.

In [Sw93] werden einige Abschlußeigenschaften für schwach wachsend kontextsensitive Sprachen bezüglich Stellenbewertungen s der Form s(i) = 2^{k·(i−1)} für alle i ∈ IN gezeigt. Die Beweise sind allerdings unabhängig von dieser speziellen Wahl der Stellenbewertung, nur daß sie keine Nullstellen hat und wenigstens zwei Stellen bewertet, wird benutzt. Also gilt nach [Sw93]:

Satz 2.2.1 : Sei s eine nullstellenfreie Stellenbewertung mit wenigstens zwei bewerteten Stellen. WGCSL_{s} ist abgeschlossen unter ε-freien Homomorphismen, Vereinigung, ε-freier regulärer Substitution, Konkatenation und Durchschnitt mit regulären Mengen.

Für Stellenbewertungen mit Nullstellen wollen wir hier keine Abschlußeigenschaften untersuchen, da sie sich in Kapitel 5.1 auf anderem Wege ergeben.

Außerdem zeigen wir:

Satz 2.2.2 : Sei s eine Stellenbewertung mit wenigstens zwei bewerteten Sellen und mit s(1) ≠ s(2). Dann ist WGCSL_{s} abgeschlossen unter Transposition.

Beweis: Sei s eine Stellenbewertung mit s(1) < s(2), sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}. Sei f eine Zeichenbewertung für G.

Konstruiere nun eine Grammatik G̃ = ⟨Ñ, T, S̃, P̃⟩ wie folgt:

Ñ = N ∪ {S̃} ∪ {a′ | a ∈ T } ∪ {(M, X) | X ∈ N} ∪ {(M, a′) | a ∈ T }

Bei der Konstruktion der Regelmenge P̃ wird wie folgt vorgegangen:

Zunächst soll für ein Wort w = w_{1} … w_{n} ∈ L die Satzform (M, w′_{1})w′_{2} … w′_{n} erzeugt werden. Danach wird diese Satzform mit Regeln der Form

(M, a′)b′ → (M, b′)a
ab′ → b′a
(M, a′) → a

in das Wort w_{n} … w_{1} umgeformt.

Insgesamt bestehe die Regelmenge P̃ aus den folgenden Regeln:

Anfangsregel:

S̃ → (M, S)

Erzeugungsregeln:

Seien α_{1}, …, α_{n}, β_{1}, …, β_{m} ∈ N ∪ T, und für jedes i ∈ {1, …, n} sei β_{i}^{∗} = β_{i}, falls β_{i} ∈ N, und β_{i}^{∗} = β′_{i} gerade die Kopie von β_{i}, falls β_{i} ∈ T. Für (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P enthalte P̃ die Regeln

α_{1} … α_{n} → β_{1}^{∗} … β_{m}^{∗}, (M, α_{1})α_{2} … α_{n} → (M, β_{1}^{∗})β_{2}^{∗} … β_{m}^{∗}

Schlußregeln (Spiegelregeln):

Seien a, b ∈ T und a′, (M, a′) gerade die Kopien von a sowie b′, (M, b′) gerade die Kopien von b. P̃ enthalte die Regeln

(M, a′)b′ → (M, b′)a, ab′ → b′a, (M, a′) → a

Offensichtlich ist L(G̃) = L(G)^{T}. G̃ ist kontextsensitiv und von der gleichen Ordnung wie G.

Definiere eine Funktion f̃: Ñ ∪ T → IN durch:

f̃(S̃) = f̃((M, S)) = f̃(S) = 1
f̃(A) = f̃((M, A)) = f(A) für alle A ∈ N
f̃(a′) = f̃((M, a′)) = f(a) für alle a ∈ T
f̃(a) = 2 · max{f(b) | b ∈ T } für alle a ∈ T

f̃ erfüllt die Bedingungen aus Satz 2.1.2, also gilt L(G̃) ∈ WGCSL_{s}.

Für den Fall s(1) > s(2) folgt die Behauptung analog mit der Regelmenge P̃ bestehend aus den Regeln:

Anfangsregel:

S̃ → (M, S)

Erzeugungsregeln:

Seien α_{1}, …, α_{n}, β_{1}, …, β_{m} ∈ N ∪ T, und für jedes i ∈ {1, …, n} sei β_{i}^{∗} = β_{i}, falls β_{i} ∈ N, und β_{i}^{∗} = β′_{i} gerade die Kopie von β_{i}, falls β_{i} ∈ T. Für (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P enthalte P̃ die Regeln

α_{1} … α_{n} → β_{1} … β_{m}, α_{1} … α_{n−1}(M, α_{n}) → β_{1} … β_{m−1}(M, β_{m})

Schlußregeln (Spiegelregeln):

Seien a, b ∈ T und a′, (M, a′) gerade die Kopien von a sowie b′, (M, b′) gerade die Kopien von b. P̃ enthalte die Regeln

a′(M, b′) → b(M, a′), a′b → ba′, (M, a′) → a

und der gleichen Zeichenbewertung. ♣

Der Beweisgedanke aus Satz 2.2.2 läßt sich auf nichtkonstante Stellenbewertungen s mit s(1) = s(2) durch Verschieben des ”Spiegelpunktes“ (M, X) und geeignete Randbehandlung übertragen. Also gilt:

Satz 2.2.3 : Sei s eine nichtkonstante Stellenbewertung. Dann ist WGCSL_{s} abgeschlossen unter Transposition.

Was fehlt, ist die Abgeschlossenheit unter inversen Homomorphismen und die unter k-beschränkten Homomorphismen, wobei aus [GGH69] bekannt ist, daß wegen Satz 2.2.1 aus der Gültigkeit der einen die Gültigkeit der anderen folgt und umgekehrt.

Diese Abgeschlossenheit kann hier weder gezeigt noch widerlegt werden; in Kapitel 5.2 werden die Konsequenzen einer Entscheidung dieser Frage diskutiert.

2.3 Normalform

Es ist in vielerlei Hinsicht nützlich, für eine Klasse von Grammatiken eine Normalform zu kennen, in die jede Grammatik dieser Klasse überführt werden kann. Weiterhin bietet das im Fall schwach wachsend kontextsensitiver Grammatiken die Möglichkeit, die durch die verschiedenen Stellenbewertungen gegebenen Klassen etwas zu ”sortieren“.

Wir führen nun die Cremers-Normalform ein, die wir in dieser Arbeit verwenden werden ([Cre73], vgl. dazu [Sw93] mit Blick auf Satz 2.1.2).

Definition 2.3.1 : Eine kontextsensitive Grammatik G = ⟨N, T, S, P ⟩ ist in Cremers-Normalform, wenn alle Regeln aus P von der Form

AB → CD  A → CD  A → a

mit A, B, C, D ∈ N, a ∈ T sind.

In [Cre73] wird gezeigt, daß jede beliebige kontextsensitve Grammatik in eine in Cremers-Normalform überführt werden kann. Da jede Grammatik in Cremers-Normalform höchstens von der Ordnung 2 ist, erhalten so die Stellenbewertungen mit 2 bewerteten Stellen eine besondere Bedeutung. Daher sollen sie und die mit ihnen definierten Grammatik- und Sprachklassen eigene Namen erhalten.

Definition 2.3.2 : Es bezeichne s_{c,d} mit c, d ∈ IN die Stellenbewertung definiert durch:

s_{c,d}(1) = c,  s_{c,d}(2) = d,  s_{c,d}(i) nicht definiert für alle i ≥ 3

Außerdem seien WGCSG_{s_{c,d}} einfach mit WGCSG_{c,d} und WGCSL_{s_{c,d}} einfach mit WGCSL_{c,d} bezeichnet.

Es zeigt sich, daß für den Nachweis der Überführbarkeit einer s-schwach wachsend kontextsensitiven Grammatik in Cremers-Normalform zentral wird, ob s von einer Stelle zur nächsten stets um den gleichen Faktor anwächst.

In folgender Definition wird dies präzise formuliert.

Definition 2.3.3 : Eine Stellenbewertung s: IN^{+} → IN heißt gleichmäßig, wenn sie nullstellenfrei ist und entweder genau zwei Stellen bewertet oder für jede bewertete Stelle i ∈ IN^{+} von s, für die auch i − 1 und i + 1 von s bewertet sind, gilt:

\frac{s(i)}{s(i − 1)} = \frac{s(i + 1)}{s(i)}

In diesem Falle heißt w(s) := \frac{s(2)}{s(1)} der Wachstumsfaktor von s. Entsprechend heißt eine Stellenbewertung s: IN^{+} → IN mit wenigstens drei bewerten Stellen ungleichmäßig, wenn es eine bewertete Stelle i ∈ IN^{+} von s gibt, für die auch i − 1 und i + 1 von s bewertet sind, mit:

s(i)^{2} ≠ s(i − 1) · s(i + 1)

In diesem Falle nennen wir solch ein i einen Knick von s, und das kleinste solche i nennen wir den ersten Knick von s. (Beachte, daß für a, b, c ∈ IN^{+} der Ausdruck \frac{a}{b} = \frac{b}{c} gleichwertig ist mit b^{2} = a · c.)

Bemerkung: Es gibt Stellenbewertungen s: IN^{+} → IN mit wenigstens zwei bewerteten Stellen, die weder gleichmäßig noch ungleichmäßig sind.

Es sind dies die Stellenbewertungen, die bis auf die erste und die letzte bewertete Stelle konstant Null sind, wie man sich leicht überlegt. Sie werden bezeichnet mit s_{c,0_{k},d}, wobei c, d, k ∈ IN sowie [c, d ∈ IN^{+} ⇒ k ∈ IN^{+}] und

s_{c,0_{k},d}(1) = c,
s_{c,0_{k},d}(i) = 0 für i ∈ IN^{+}, 1 < i ≤ k + 1,
s_{c,0_{k},d}(k + 2) = d und
s_{c,0_{k},d}(i) nicht definiert für i > k + 2

Dabei schreiben wir abkürzend s_{0_{k+1},d} für s_{0,0_{k},d} und s_{c,0_{k+1}} für s_{c,0_{k},0} sowie WGCSG_{c,0_{k},d} für WGCSG_{s_{c,0_{k},d}} usw.

Es ist s_{0,0_{0},d} = s_{0_{1},d} = s_{0,d} und s_{c,0_{0},0} = s_{c,0_{1}} = s_{c,0}.

Bemerkung: Sei s: IN^{+} → IN eine gleichmäßige Stellenbewertung. Dann gilt für alle i, j ∈ IN^{+}, für die i + j eine bewertete Stelle von s ist:

s(i + j) = (w(s))^{j} · s(i)

Denn \frac{s(k+1)}{s(k)} = w(s) für alle k ∈ IN^{+}, für die auch k + 1 bewertete Stelle von s ist, da s gleichmäßig, also gilt:

s(i) · (w(s))^{j} = s(i) · \frac{s(i + 1)}{s(i)} · \frac{s(i + 2)}{s(i + 1)} · . . . · \frac{s(i + j)}{s(i + j − 1)} = s(i + j)

Für jede gleichmäßige Stellenbewertung s läßt sich jede Grammatik aus WGCSG_{s} in Cremers-Normalform überführen. Für einige gleichmäßige Stellenbewertungen, nämlich solche der Form s(i) = 2^{k·(i−1)} für alle i ∈ IN^{+} mit k ∈ IN^{+}, wurde dies in [Sw93] gezeigt (mit Anwendung von Satz 2.1.2). Der Vollständigkeit halber, da der Beweis vereinfacht und umstrukturiert wurde und weil dieses Ergebnis auf Stellenbewertungen s_{c,0_{k}} sowie etwas modifiziert auf s_{0_{k},d} ausgeweitet wird, soll der Nachweis hier nochmals geführt werden.

Für den Nachweis dieser Ergebnisse wird zunächst gezeigt, daß sich die Ordnung einer schwach wachsend kontextsensitiven Grammatik bezüglich einer geeigneten Stellenbewertung reduzieren läßt.

Satz 2.3.4 : Sei s eine Stellenbewertung mit wenigstens zwei bewerteten Stellen, für die eine der folgenden Bedingungn gilt:

(i) s ist gleichmäßig

(ii) s = s_{c,0_{k}} für ein c ∈ IN^{+} und ein k ∈ IN^{+}

(iii) s = s_{0_{k},c} für ein c ∈ IN^{+} und ein k ∈ IN^{+}

Dann gilt: Zu jeder Grammatik G ∈ WGCSG_{s} der Ordnung l ≥ 3 gibt es eine äquivalente Grammatik der Ordnung l − 1 mit:

in den Fällen (i) und (ii) : G′ ∈ WGCSG_{s} im Falle (iii) : G′ ∈ WGCSG_{s_{0_{k−1},c}} Beweis: Sei zunächst eine gleichmäßige Stellenbewertung s: IN^{+} → IN mit wenigstens drei bewerteten Stellen gegeben. Sei s′: IN^{+} → IN definiert durch s′(i) = s(i + 1) für alle i ∈ IN , also sei auch s′(i) nicht definiert, falls s(i + 1) nicht definiert ist. Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} von der Ordnung l ≥ 3. Sei f: N ∪ T → IN eine Zeichenbewertung für G.

Konstruiere nun eine Grammatik G′ = ⟨N′, T, S′, P′⟩ und dazu eine Zeichenbewertung f′ : N′ ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} durch den folgenden Algorithmus:

1. N′ := N, P′ := ∅

2. f′(A) = f(A) für alle A ∈ N, f′(a) = f(a) für alle a ∈ T

3. wiederhole für jede Regel (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P:

4. Falls m = 2, so setze P′ := P′ ∪ {(α_{1} … α_{n} → β_{1} … β_{m})}

5. Falls 3 ≤ m ≤ l, so sei X ein neues Nichtterminal, X ∉ N′.

6. Definiere die Regeln (R1) α_{1}α_{2} → β_{1}X

(R2) Xα_{3} … α_{n} → β_{2} … β_{m}

Dabei ist n = 2, also α_{3} … α_{n} = ε, oder n = 1, also zusätzlich α_{2} = ε, möglich.

7. Setze P′ := P′ ∪ {(R1), (R2)}

8. Setze f′(X) := \frac{s(1)}{s(2)} · f(α_{1}) + f(α_{2}) − \frac{s(1)}{s(2)} · f(β_{1}) + \frac{1}{2·s(2)}

Es gilt L(G′) = L(G).

Wir zeigen nun G′ ∈ WGCSG_{s′}, dann folgt mit Satz 2.1.4 und Satz 2.1.3, daß G′ ∈ WGCSG_{s}.

Die Regeln aus P′ sind alle kontextsensitiv, und es ist ord(G′) = ord(G) − 1, also sicherlich ord(G′) ≤ max{i ∈ IN^{+} | s′(i) ist definiert }. Weiterhin sind die Regeln aus P′ alle s′-schwach wachsend mit f′, was man wie folgt sieht:

In P′ sind nur Regeln enthalten, die gemäß der Vorschrift aus dem Algorithmus aus Regeln aus P gebildet wurden. Also ist zu zeigen: Durch den Algorithmus werden aus s-schwach wachsenden Regeln s′-schwach wachsende Regeln erzeugt.

Sei also (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P.

Falls m = 2, ist diese Regel auch aus P′, und wegen \frac{s(2)}{s(1)} = \frac{s(3)}{s(2)} gilt:

s(1) · f(α_{1}) + s(2) · f(α_{2}) < s(1) · f(β_{1}) + s(2) · f(β_{2})
⇔  f(α_{1}) + \frac{s(2)}{s(1)} · f(α_{2}) < f(β_{1}) + \frac{s(2)}{s(1)} · f(β_{2})
⇔  f(α_{1}) + \frac{s(3)}{s(2)} · f(α_{2}) < f(β_{1}) + \frac{s(3)}{s(2)} · f(β_{2})
⇔  s(2) · f(α_{1}) + s(3) · f(α_{2}) < s(2) · f(β_{1}) + s(3) · f(β_{2})
⇔  s′(1) · f′(α_{1}) + s′(2) · f′(α_{2}) < s′(1) · f′(β_{1}) + s′(2) · f′(β_{2})

also ist diese Regel s′-schwach wachsend mit f′.

Für 3 ≤ m ≤ l seien (R1) = (α_{1}α_{2} → β_{1}X) und (R2) = (Xα_{3} … α_{n} → β_{2} … β_{n}) die zugehörigen Regeln aus P′. In den folgenden Betrachtungen sei f(ε) = 0.

zu (R1): Für die Bewertung der rechten Seite von (R1) gilt:

s′(1) · f′(β_{1}) + s′(2) · f′(X)

= s(2) · f(β_{1}) + s(3) · (\frac{s(1)}{s(2)} · f(α_{1}) + f(α_{2}) − \frac{s(1)}{s(2)} · f(β_{1}) + \frac{1}{2 · s(2)})

= s(2) · f(β_{1}) + s(2) · f(α_{1}) + s(3) · f(α_{2}) − s(2) · f(β_{1}) + \frac{s(3)}{2 · s(2)}

= s(2) · f(α_{1}) + s(3) · f(α_{2}) + \frac{s(2)}{2 · s(1)}

> s(2) · f(α_{1}) + s(3) · f(α_{2}) = s′(1) · f′(α_{1}) + s′(2) · f′(α_{2})

und das ist die Bewertung der linken Seite von (R1). Also ist (R1) s′-schwach wachsend mit f′.

zu (R2): Es gilt: ∑_{i=1}^{n} s(i) · f(α_{i}) < ∑_{i=1}^{m} s(i) · f(β_{i}), und die Ausdrücke auf beiden Seiten der Ungleichung sind natürliche Zahlen. Daraus folgt:

∑_{i=1}^{n} s(i) · f(α_{i}) + \frac{1}{2} < ∑_{i=1}^{m} s(i) · f(β_{i})

Für die Bewertung der linken Seite von (R2) gilt:

s′(1) · f′(X) + ∑_{i=2}^{n−1} s′(i) · f′(α_{i+1})

= s(2) · f′(X) + ∑_{i=2}^{n−1} s(i + 1) · f(α_{i+1})

= s(2) · (\frac{s(1)}{s(2)} · f(α_{1}) + f(α_{2}) − \frac{s(1)}{s(2)} · f(β_{1}) + \frac{1}{2 · s(2)}) + ∑_{i=3}^{n} s(i) · f(α_{i})

= s(1) · f(α_{1}) + s(2) · f(α_{2}) + ∑_{i=3}^{n} s(i) · f(α_{i}) + \frac{1}{2} − s(1) · f(β_{1})

< ∑_{i=1}^{m} s(i) · f(β_{i}) − s(1) · f(β_{1})

= ∑_{i=2}^{m} s(i) · f(β_{i}) = ∑_{i=1}^{m−1} s(i + 1) · f(β_{i+1})

= ∑_{i=1}^{m−1} s′(i) · f′(β_{i+1})

Und das ist die Bewertung der rechten Seite von (R2). Also ist (R2) s′-schwach wachsend mit f′.

Nach Satz 2.1.5 genügt es, eine Zeichenbewertung mit Werten aus Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} anzugeben, um zu zeigen, daß G′ schwach wachsend kontextsensitiv bezüglich der Stellenbewertung s′ ist, also gilt G′ ∈ WGCSG_{s′}. Wie oben erwähnt folgt daraus G′ ∈ WGCSG_{s}.

Sei nun eine Stellenbewertung s_{c,0_{k}} mit c, k ∈ IN^{+}, k ≥ 2 gegeben. Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{c,0_{k}} von der Ordnung l ≥ 3, sei f: N ∪ T → IN eine Zeichenbewertung für G.

Konstruiere nun eine Grammatik G′ = ⟨N′, T, S′, P′⟩ und dazu eine Zeichenbewertung f′ : N′ ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} wie im obigen Algorithmus mit dem einzigen Unterschied:

Schritt 8 : Setze f′(X) = f(β_{2}) − \frac{1}{2·c}

Es ist L(G′) = L(G) und die Grammatik G′ ist s_{c,0_{k}}-schwach wachsend kontextsensitiv.

Sei nun eine Stellenbewertung s_{0_{k},c} mit c, k ∈ IN^{+}, k ≥ 2 gegeben. Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{0_{k},c} von der Ordnung l ≥ 3, sei f: N ∪ T → IN eine Zeichenbewertung für G. (Aus Definition 1.1.4 folgt l = k + 1, und für alle Regeln (α_{1} … α_{k+1} → β_{1} … β_{k+1}) ∈ P gilt: f(α_{k+1}) < f(β_{k+1}).)

Konstruiere nun eine Grammatik G′ = ⟨N′, T, S′, P′⟩ und dazu eine Zeichenbewertung f′ : N′ ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} wie im obigen Algorithmus mit den einzigen beiden Unterschieden (zur Erinnerung: es kann in P auch Regeln S → β mit |β| < k geben, siehe Definition 1.1.4):

Schritt 6 : Definiere die Regeln

(R1) α_{1} … α_{k−1}α_{k} → β_{1} … β_{k−1}X
(R2) β_{2} … β_{k−1}Xα_{k+1} → β_{2} … β_{k−1}β_{k}β_{k+1}

Dabei ist n ≤ k, also α_{k+1} = ε oder zusätzlich α_{k} = ε usw., möglich. Schritt 8 : Setze f′(X) = f(α_{k}) + 1

Es ist L(G′) = L(G), und die Grammatik G′ ist s_{0_{k−1},c}-schwach wachsend kontextsensitiv. ♣

Bemerkung: Auch wenn man für die Stellenbewertung s Werte aus Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} _{0}^{+} erlaubt, läßt sich der Beweis von Satz 2.3.4 ähnlich führen. Die Menge der möglichen Werte links und rechts in der Bewertung einer Regel ist nämlich dann immer noch diskret, und das kann man in der gleichen Weise ausnutzen wie oben.

Beispiel 2.3.5 : Für eine Grammatik aus WGCSL_{s} bezüglich einer ungleichmäßigen Stellenbewertung s muß die Methode aus dem Beweis von Satz 2.3.4 nicht funktionieren. Sei z.B. s = id. Sei α_{1}α_{2}α_{3} → β_{1}β_{2}β_{3} eine Regel, sei

\begin{matrix}f(α_{1}) = 1, & f(α_{2}) = 1, & f(α_{3}) = 3, \\ f(β_{1}) = 1, & f(β_{2}) = 5, & f(β_{3}) = 1 \end{matrix}

Dann ist

\begin{matrix}1 · f(α_{1}) + 2 · f(α_{2}) + 3 · f(α_{3}) = 1 · 1 + 2 · 1 + 3 · 3 = 12 \\ 1 · f(β_{1}) + 2 · f(β_{2}) + 3 · f(β_{3}) = 1 · 1 + 2 · 5 + 3 · 1 = 14 \end{matrix}

das heißt die Regel kann einer Grammatik aus WGCSG_{id} entstammen.

Für die Regeln

\begin{matrix}(R1) α_{1}α_{2} → β_{1}X \\ (R2) Xα_{3} → β_{2}β_{3} \end{matrix}

die sich nach dem Beweis von Satz 2.3.4 ergeben würden, folgt dann:

• für (R1):

1 · 1 + 2 · 1 < 1 · 1 + 2 · f(X)
⇔  3 < 1 + 2 · f(X)
⇔  1 < f(X)

• für (R2):

1 · f(X) + 2 · 3 < 1 · 5 + 2 · 1
⇔  f(X) + 6 < 7
⇔  f(X) < 1

Das heißt, es läßt sich so kein passender Funktionswert für X finden. Dieses Beispiel stammt von [Bur93].

Wir werden später sehen, daß nicht nur der Beweis von Satz 2.3.4 sich auf ungleichmäßige Stellenbewertungen nicht übertragen läßt, sondern das Problem tiefer liegt. Für gleichmäßige Stellenbewertungen läßt sich Satz 2.3.4 natürlich sukzessive anwenden, was zu folgender Feststellung führt:

Satz 2.3.6 : Sei s eine gleichmäßige Stellenbewertung. Zu jeder Grammatik G ∈ WGCSG_{s} gibt es eine äquivalente Grammatik G′ ∈ WGCSG_{s} in Cremers-Normalform. Es gilt also WGCSL_{s} = WGCSL_{s(1),s(2)}.

Beweis: Sei also s eine gleichmäßige Stellenbewertung, sei G ∈ WGCSG_{s} eine Grammatik von der Ordnung l ≥ 3.

Durch wiederholte Anwendung von Satz 2.3.4 folgt, daß zu G eine äquivalente Grammatik G′ der Ordnung 2 existiert mit G′ ∈ WGCSG_{s}, und mit Satz 2.1.1 und Satz 2.1.2 erhält man aus jeder Grammatik der Ordnung 2 aus WGCSG_{s} eine s-schwach wachsend kontextsensitive Grammatik in Cremers-Normalform aus WGCSG_{s}. ♣

Bemerkung: Eigentlich wird also für eine gleichmäßige Stellenbewertung s die Klasse WGCSL_{s} durch den Wachstumsfaktor w(s) carakterisiert. Daher ist folgende Bezeichnung sinnvoll:

WGCSL_{w(s)} := WGCSL_{s}

Denn WGCSL_{s} = WGCSL_{s′} für alle s′ mit w(s) = w(s′) wegen Satz 2.3.6 und Satz 2.1.4. Das ist auch richtig, wenn man für eine Stellenbewertung Werte aus Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} _{0}^{+} erlaubt.

Für Stellenbewertungen s_{c,0_{k}} und s_{0_{k},c} läßt sich Satz 2.3.4 ebenfalls sukzessive anwenden, und daraus folgt:

Satz 2.3.7 : Seien c, k ∈ IN^{+}. Zu jeder Grammatik G ∈ WGCSG_{c,0_{k}} gibt es eine äquivalente Grammatik G′ ∈ WGCSG_{c,0_{k}} in Cremers-Normalform, und zu jeder Grammatik G ∈ WGCSG_{0_{k},c} gibt es eine äquivalente Grammatik G′ ∈ WGCSG_{0,c}. Es gilt also

WGCSL_{c,0_{k}} = WGCSL_{c,0} = WGCSL_{1,0} und WGCSL_{0_{k},c} = WGCSL_{0,c} = WGCSL_{0,1}

Beweis: Die Behauptungen zu s_{c,0_{k}} folgen aus den Sätzen 2.3.4, 2.1.2, 2.1.1 und 2.1.4, die zu s_{0_{k},c} aus den Sätzen 2.3.4 und 2.1.4. ♣

Die Eigenschaft einer Stellenbewertung, gleichmäßig oder ungleichmäßig zu sein, hat noch weitere Konsequenzen:

1. für gleichmäßige Stellenbewertungen läßt sich die Länge einer Ableitung nach oben beschränken durch das Gewicht des erzeugten Wortes (wobei die Stellenbewertung geeignet fortgesetzt wird), da bei jeder Regelanwendung auch das Gewicht der jeweiligen Satzform anwächst (siehe Kapitel 4.1.2).

2. für ungleichmäßige Stellenbewertungen läßt sich eine solche Abschätzung der Ableitungslänge nicht machen, und zwar weil bei einer natürlichen Fortsetzung der Stellenbewertung das Gewicht der Satzformen bei einer Regelanwendung auch abnehmen kann. Es sind sogar beliebig lange Ableitungen möglich, und es stellt sich heraus, daß die schwach wachsend kontextsensitiven Grammatiken bezüglich einer beliebigen ungleichmäßigen Stellenbewertung bereits die Klasse CSL charakterisieren (siehe Kapitel 3.2).

3. für Stellenbewertungen, die weder gleichmäßig noch ungleichmäßig sind, stellt sich heraus, daß auch die bezüglich einer solchen Stellenbewertung schwach wachsend kontextsensitiven Grammatiken die Klasse CSL charakterisieren (siehe Kapitel 5.1).

Charakterisierung der kontextsensitiven Sprachen

3.1 Linear beschränkte Automaten

Es ist bekannt, daß linear beschränkte Automaten genau die kontextsensitiven Sprachen erkennen ([Ku64]). Diese Tatsache wird in Kapitel 3.2 beim Nachweis der Gleichheit von CSL und WGCSL_{s} mit beliebiger ungleichmäßiger Stellenbewertung s ausgenützt. Da dabei außerdem die Beweistechnik der Simulation eines linear beschränkten Automaten durch eine kontextsensitive Grammatik mehrfach eingesetzt und angepaßt wird, soll hier zur Erinnerung ein Beweis angeführt werden (vgl. [Har78], Lemma 9.5.1 (S. 290) und Lemma 9.5.3 (S. 293)).

Bei der Simulation eines linear beschränkten Automaten M durch eine kontextsensitive Grammatik wird in einer Satzform, welche die jeweils aktuelle Konfiguration repräsentiert, auf drei Spuren, d.h. die Zeichen einer Satzform sind Tripel, folgendes getan:

• auf der ersten Spur steht die Eingabe von M

• auf der zweiten Spur steht der jeweils aktuelle Inhalt des Arbeitsbandes von M

• auf der dritten Spur steht an genau einer Stelle der aktuelle Zustand von M, und zwar an der Position, an der der Schreib-/Lesekopf von M zum betrachteten Zeitpunkt gerade steht, also unterhalb des Zeichens, welches der Schreib-/Lesekopf gerade liest.

Diese Satzform wird mit der Startkonfiguration und einem beliebigen Eingabewort erzeugt, dann der linear beschränkte Automat M simuliert, und falls M akzeptiert, werden die Tripel in die Einträge ihrer ersten Spur umgewandelt, welche dann Terminale sind.

Satz 3.1.1 : Jede Sprache L, zu der es einen linear beschränkten Automaten M gibt mit L(M) = L, liegt in CSL , d.h. es gilt:

NSPACE (n) ⊆ CSL

Beweis: Sei M = (Q, Σ, Γ, □, δ, q_{0}, F) ein linear beschränkter (Einband-) Automat (siehe Seite 13). Es kann o.B.d.A. angenommen werden, daß M nicht stehenbleibt (siehe Seite 13).

Konstruiere eine Grammatik G = ⟨N, Σ, S, P ⟩. Dafür seien Γ′ = {a′ | a ∈ Γ} und Γ′′ = {a′′ | a ∈ Γ} markierte Kopien des Arbeitsalphabets für den linken bzw. rechten Rand.

Für die Menge der Nichtterminale definiere:

N_{BandAnf} = \{[\begin{matrix}x \\ a′ \end{matrix}]| x ∈ Σ, a′ ∈ Γ′\}

N_{Band} = \{[\begin{matrix}x \\ a \end{matrix}]| x ∈ Σ, a ∈ Γ\}

N_{BandEnd} = \{[\begin{matrix}x \\ a′′ \end{matrix}]| x ∈ Σ, a′′ ∈ Γ′\}

N_{Zust}  = \{[\begin{matrix}x \\ a^{∗} \\ q \end{matrix}]| x ∈ Σ, a^{∗} ∈ Γ ∪ Γ′ ∪ Γ′′, q ∈ Q\}

Definiere N durch:

N = {S, X} ∪ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd} ∪ N_{Zust}

Die Regelmenge P bestehe aus den folgenden Regeln:

Dabei seien x, y ∈ Σ, a, b, c, d ∈ Γ, dazu a′, c′ ∈ Γ′ und b′′, d′′ ∈ Γ′′ gerade die jeweiligen markierten Kopien von a, c für den linken und von b, d für den rechten Rand. Es seien p, q, q̃ ∈ Q sowie [a^{∗} = a′ ∧ c^{∗} = c′] ∨ [a^{∗} = a ∧ c^{∗} = c] und [b^{∗} = b ∧ d^{∗} = d] ∨ [b^{∗} = b′′ ∧ d^{∗} = d′′].

Banderzeugung:

S →[\begin{matrix}a \\ a′ \\ q_{0} \end{matrix}]X  X →[\begin{matrix}a \\ a \end{matrix}]X  X →[\begin{matrix}a \\ a′′ \end{matrix}]  S → w für w ∈ L(M), |w| = 1 S → ε falls ε ∈ L(M)

Bewegung nach rechts:

Falls (p, c, R) ∈ δ(q, a), dann enthält P die Regeln:

[\begin{matrix}x \\ a^{∗} \\ q \end{matrix}][\begin{matrix}y \\ b^{∗} \end{matrix}]→[\begin{matrix}x \\ c^{∗} \end{matrix}][\begin{matrix}y \\ b^{∗} \\ p \end{matrix}]

Bewegung am rechten Rand:

Falls (q̃, c, R) ∈ δ(q, a) ∧ (p, □, L) ∈ δ(q̃, □), dann enthält P die Regel:

[\begin{matrix}x \\ a′′ \\ q \end{matrix}]→[\begin{matrix}x \\ c′′ \\ p \end{matrix}]

Bewegung nach links:

Falls (p, d, L) ∈ δ(q, b), dann enthält P die Regeln:

[\begin{matrix}x \\ a^{∗} \end{matrix}][\begin{matrix}y \\ b^{∗} \\ q \end{matrix}]→[\begin{matrix}x \\ a^{∗} \\ p \end{matrix}][\begin{matrix}y \\ d^{∗} \end{matrix}]

Bewegung am linken Rand:

Falls (q̃, c, L) ∈ δ(q, a) ∧ (p, □, R) ∈ δ(q̃, □), dann enthält P die Regel:

[\begin{matrix}x \\ a′ \\ q \end{matrix}]→[\begin{matrix}x \\ c′ \\ p \end{matrix}]

(M bleibt nach Vereinbarung nicht stehen.)

Akzeptieren (nach Vereinbarung (siehe S. 12) hält M rechts neben dem beschriebenen Bandinhalt):

Falls (q_{F} , c, R) ∈ δ(q, a) mit q_{F} ∈ F, enthält P die Regel:

[\begin{matrix}x \\ a′′ \\ q \end{matrix}]→ x

Eingabe in Terminale umwandeln:

[\begin{matrix}x \\ a \end{matrix}]y → xy  [\begin{matrix}x \\ a′ \end{matrix}]y → xy

Diese Grammatik erzeugt genau die Sprache, die M erkennt (nachzulesen in [Har78]). Also gilt: NSPACE (n) ⊆ CSL . ♣

Bei der Simulation einer kontextsensitiven Grammatik durch einen linear beschränkten Automaten wird einfach eine Ableitung nachvollzogen und das Ergebnis mit der Eingabe verglichen.

Satz 3.1.2 : Für jede Sprache L ∈ CSL gibt es einen linear beschränkten Automaten, der L erkennt, d.h. es gilt:

CSL ⊆ NSPACE (n)

Beweis: Sei nun G = ⟨N, T, S, P ⟩ eine kontextsensitive Grammatik. Es wird nun ein linear beschränkter (Einband-) Automat konstruiert, der in der folgenden Weise arbeitet:

M arbeitet auf zwei Spuren, auf der ersten steht die Eingabe, auf der zweiten wird eine Ableitung in G simuliert.

1. M schreibt S unter das erste Eingabezeichen auf die zweite Spur.

2. Wiederhole, bis das Wort auf der zweiten Spur aus T^{∗} ist oder keine Regel mehr angewendet werden kann:

a) wähle ein Teilwort auf der zweiten Spur, das einem α entspricht mit (α → β) ∈ P.

b) ersetze α durch β. Falls |α| < |β|, verschiebe das Teilwort rechts von α um entsprechend viele Zeichen nach rechts. Wird dabei der durch die Eingabe gekennzeichnete Platz überschritten, lehne ab.

3. Falls das Wort auf der zweiten Spur aus T^{∗} ist, vergleiche es mit der Eingabe. gleich: akzeptiere ungleich: lehne ab

Es ist leicht zu sehen, daß diese Konstruktion für jede kontextsensitive Grammatik G durchführbar ist und daß L(G) = L(M) gilt. Also ist CSL ⊆ NSPACE (n). ♣

Zusammen folgt aus Satz 3.1.1 und Satz 3.1.2 also

Satz 3.1.3 : Es gilt: CSL = NSPACE (n).

Zum Zeitaufwand bei der Simulation im Beweis von Satz 3.1.2, der in Kapitel 4 genauer thematisiert wird, läßt sich folgendes aussagen:

Bemerkung: Sei L ∈ CSL , G = ⟨N, T, S, P ⟩ ∈ CSG mit L(G) = L und M der nach dem Beweis von Satz 3.1.2 zu G konstruierte Automat.

Ist w ∈ L von der Länge n und A die Anzahl der Ableitungsschritte einer Ableitung S ⟹^{∗}_{G} w, so arbeitet der im genannten Beweis konstruierte linear beschränkte Automat höchstens O(A · n + n^{2}) Schritte.

Dabei entsteht der Faktor n im Anteil A·n durch das Aufsuchen der Ersetzungsstelle und der Anteil n^{2} durch das Verschieben bei expandierenden Regeln (siehe Punkt 2.b im Algorithmus).

3.2 Die ungleichmäßige Stellenbewertung

Wie schon erwähnt stellt sich heraus, daß für jede ungleichmäßige Stellenbewertung s gilt:

WGCSL_{s} = CSL

Um dies zu beweisen, wird ausgenutzt, daß es für jede ungleichmäßige Stellenbewertung s eine bewertete Stelle j gibt, für die j − 1 und j + 1 ebenfalls von s bewertet werden, mit s(j)^{2} ≠ s(j −1)·s(j +1). Ein solches j haben wir einen Knick von s genannt, und das kleinste solche j den ersten Knick von s (siehe Definition 2.3.3).

Wir unterscheiden vier Fälle für eine ungleichmäßige Stellenbewertung s:

(i) s besitzt einen Knick j mit s(j − 1) > s(j) und s(j) < s(j + 1) (”Talknick“)

(ii) s besitzt einen Knick j mit s(j − 1) < s(j) und s(j) > s(j + 1) (”Gipfelknick“)

(iii) s ist monoton wachsend

(iv) s ist monoton fallend

Jede ungleichmäßige Stellenbewertung gehört zu einem der vier Fälle, dabei sind die Fälle (i) und (ii) nicht disjunkt. In Fall (iii) wollen wir Stellenbewertungen s mit s(1) = 0 ausnehmen, da für diese Stellenbewertungen WGCSL_{0,1} ⊆ WGCSL_{s} gilt und wir die Stellenbewertungen s_{0,1} und s_{1,0} in Kapitel 5.1 betrachten.

In jedem Fall konstruieren wir zu einem linear beschränkten Automaten (der nicht stehenbleibt, siehe S. 13) eine s-schwach wachsend kontextsensitive Grammatik analog zum Beweis von Satz 3.1.1.

Zum ersten Fall:

Der ”Talknick“ in der Stellenbewertung wird folgendermaßen ausgenutzt: Alle Nichtterminale, die einfache Bandfelder repräsentieren, erhalten durch die (entsprechend zu definierende) Zeichenbewertung das gleiche Gewicht, und die Nichtterminale, in denen ein Zustand eingetragen ist, erhalten ein höheres. Eine Regel, die einen Schritt des linear beschränkten Automaten simuliert, wird nun so konstruiert, daß das Nichtterminal mit dem Zustand auf der linken Regelseite genau auf diesem Knick steht. Dadurch, daß der Zustand auf der rechten Regelseite damit rechts oder links von diesem Knick steht, also auf einer höher bewerteten Stelle, wird diese Regel s-schwach wachsend mit der oben genannten Zeichenbewertung.

Durch die Skizze in Abbildung 3.1 (Seite 34) soll das veranschaulicht werden.

Zum Weiterarbeiten müssen also stets rechts und links vom Zustand in der Satzform noch weitere Zeichen stehen: rechts noch wenigstens eines, links, wenn der betrachtete Knick an der Stelle j der Stellenbewertung liegt, noch wenigstens j −1. Daher müssen an den Rändern jeweils mehrere Schritte des Automaten zusammengefaßt werden, denn der Zustand darf in den Satzformen nie auf einem Randzeichen stehen, da, wie wir eben gesehen haben, sich keine schwach wachsende Regel angeben läßt, die den Zustand vom Rand wegbringt.

[figure: Regel aus P:; LBA :; \begin{aligned}[ & p & ] \\ [ & ] \\ & [ & ] \end{aligned}; Zustand p; Zustand q; \begin{aligned}[ & ] \\ [ & q & ] \\ & & [ & ] \end{aligned}; z.B. Bew.; nach links; s:]

Abbildung 3.1: Simulation im ersten Fall (Skizze)

Satz 3.2.1 : Sei s eine ungleichmäßige Stellenbewertung, für einen Knick j von s gelte s(j − 1) > s(j), s(j) < s(j + 1), also sind die Stellen links und rechts vom Knick j höher bewertet als der Knick j selbst. Dann gilt:

CSL ⊆ WGCSL_{s}

Beweis: Sei s mit den Voraussetzungen des Satzes gegeben, sei j wie im Satz definiert.

Sei L ∈ CSL. Sei M = (Q, Σ, Γ, □, δ, q_{0}, F) ein linear beschränkter Automat, der L erkennt (existiert nach Satz 3.1.1).

Konstruiere nun eine kontextsensitive Grammatik G = ⟨N, Σ, S, P ⟩. Dafür seien Γ′ und Γ′′ wie im Beweis von Satz 3.1.1 markierte Kopien des Arbeitsalphabetes Γ für den linken bzw. den rechten Rand.

Für die Menge der Nichtterminale N definiere N_{BandAnf}, N_{Band} und N_{BandEnd} wie im Beweis von Satz 3.1.1, N_{Zust} jedoch durch:

N_{Zust} = \{[\begin{matrix}x \\ a \\ q \end{matrix}]| x ∈ Σ, a ∈ Γ, q ∈ Q\}

da bei der Simulation der Zustand nicht auf einem Randzeichen stehen darf. Damit definiere N durch:

N = {S, X} ∪ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd} ∪ N_{Zust}

Die Regelmenge P bestehe aus den folgenden Regeln:

Dabei seien x_{1}, …, x_{j−1}, x, y, z ∈ Σ, a_{1}, …, a_{j−1}, c_{1}, …, c_{j−1}, a, b, c, d, e, f ∈ Γ, dazu a′_{1}, c′_{1}, a′ ∈ Γ′ und a′′, c′′, f′′ ∈ Γ′′ gerade die jeweiligen markierten Kopien von a_{1}, c_{1}, a für den linken und von a, c, f für den rechten Rand. Es seien p, q, q̃ ∈ Q sowie

α_{∗} ∈ (N_{Band})^{∗} ∪ N_{BandAnf} (N_{Band})^{∗} mit |α_{∗}| = j − 2 (also für j = 2 ist α_{∗} = ε )

Banderzeugung: Falls q_{0}x_{1} … x_{j−1} _{M}^{∗} a_{1} … a_{j−1}q□, dann enthält P die Regel:

S →[\begin{matrix}x_{1} \\ a′_{1} \end{matrix}][\begin{matrix}x_{2} \\ a_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ a_{j−1} \end{matrix}][\begin{matrix}b \\ b \\ q \end{matrix}]X

außerdem die Regeln:

X →[\begin{matrix}a \\ a \end{matrix}]X,  X →[\begin{matrix}a \\ a′′ \end{matrix}]  S → w für w ∈ L(M), |w| ≤ j + 1 S → ε falls ε ∈ L(M)

Bewegung nach rechts: Falls (p, c, R) ∈ δ(q, a), dann enthält P die Regeln:

α_{∗}α_{+}[\begin{matrix}y \\ a \\ q \end{matrix}][\begin{matrix}z \\ b \end{matrix}]→ α_{∗}α_{+}[\begin{matrix}y \\ c \end{matrix}][\begin{matrix}z \\ b \\ p \end{matrix}]

Bewegung am rechten Rand: Falls (q̃, d, R) ∈ δ(q, b) ∧ adq̃c _{M}^{∗} paef, enthält P die folgende Regel:

α_{∗}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b \\ q \end{matrix}][\begin{matrix}z \\ c′′ \end{matrix}]→ α_{∗}[\begin{matrix}x \\ a \\ p \end{matrix}][\begin{matrix}y \\ e \end{matrix}][\begin{matrix}z \\ f′′ \end{matrix}]

Bewegung nach links: Falls (p, d, L) ∈ δ(q, b), enthält P die folgende Regeln:

α_{∗}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b \\ q \end{matrix}]→ α_{∗}[\begin{matrix}x \\ a \\ p \end{matrix}][\begin{matrix}y \\ d \end{matrix}]

Bewegung am linken Rand: Falls (q̃, c, L) ∈ δ(q, a) ∧ a_{1} … a_{j−2}q̃a_{j−1}cb _{M}^{∗} c_{1} … c_{j−1}epb, enthält P die folgende Regel:

[\begin{matrix}x_{1} \\ a′_{1} \end{matrix}][\begin{matrix}x_{2} \\ a_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ a_{j−1} \end{matrix}][\begin{matrix}x \\ a \\ q \end{matrix}][\begin{matrix}y \\ b \end{matrix}]→[\begin{matrix}x_{1} \\ c′_{1} \end{matrix}][\begin{matrix}x_{2} \\ c_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ c_{j−1} \end{matrix}][\begin{matrix}x \\ e \end{matrix}][\begin{matrix}y \\ b \\ p \end{matrix}]

Akzeptieren: Falls qbc _{M}^{∗} deq_{F} □ mit q_{F} ∈ F, enthält P die folgende Regel:

α_{∗}α_{+}[\begin{matrix}y \\ b \\ q \end{matrix}][\begin{matrix}z \\ c′′ \end{matrix}]→ α_{∗}α_{+}yz

Eingabe in Terminale umwandeln:

α_{∗}[\begin{matrix}x \\ a \end{matrix}]y → α_{∗}xy,  [\begin{matrix}x_{1} \\ a′_{1} \end{matrix}][\begin{matrix}x_{2} \\ a_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ a_{j−1} \end{matrix}]y → x_{1}x_{2} … x_{j−1}y

Diese Grammatik ist kontextsensitiv.

Die beschriebene Simulation funktioniert ab einer Länge der Satzform von j + 2, also für Eingabewörter w mit |w| ≥ j + 2. Kürzere Wörter aus L werden direkt erzeugt, und somit erkennt man wie im Beweis von Satz 3.1.1, daß L(G) = L(M) gilt. Außerdem ist ord(G) = j + 1, und s hat mindestens j + 1 bewertete Stellen.

Nun ist noch eine Zeichenbewertung f: N ∪ T → IN für G zu finden.

Definiere f folgendermaßen:

f(S) = 1 f(X) = 1
f(B) = 2 für alle B ∈ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd}
f(Z) = 3 für alle Z ∈ N_{Zust}
f(x) = 4 für alle x ∈ Σ

Damit sieht man durch einfaches Nachrechnen, daß sämtliche Regeln aus P s-schwach wachsend kontextsensitiv mit f sind, also ist G ∈ WGCSG_{s} und damit L ∈ WGCSL_{s}.

♣

Zum zweiten Fall:

Der ”Gipfelknick“ in der Stellenbewertung wird in gleicher Weise ausgenutzt wie der ”Talknick“ im ersten Fall. Da die Stellen rechts und links von diesem Knick nun aber niedriger bewertet sind als dieser Knick selbst, wird nun den Nichtterminalen, in denen ein Zustand eingetragen ist, durch die (entsprechend zu definierende) Zeichenbewertung ein niedrigeres Gewicht zugeordnet als denen, die (einfache) Bandfelder repräsentieren. Eine Regel, die einen Schritt des linear beschränkten Automaten simuliert, wird genauso konstruiert wie im ersten Fall. Indem nun der ”leichtere“ Zustand von diesem höher bewerteten Knick fortwandert, steht auf der rechten Seite der entsprechenden Regel nun auf diesem Knick ein ”schwereres“ Bandnichtterminal statt auf der niedriger bewerteten Stelle daneben. Dadurch wird die Regel s-schwach wachsend mit der oben genannten Zeichenbewertung.

Dazu ebenfalls eine Skizze (Abbildung 3.2).

Für die Randbehandlung gelten die gleichen Bedingungen wie im ersten Fall, es stellt sich also heraus, daß die Grammatik aus dem Beweis von Satz 3.2.1 übernommen werden kann, nur die Zeichenbewertung muß anders definiert werden.

Satz 3.2.2 : Sei s eine ungleichmäßige Stellenbewertung, für einen Knick j von s gelte s(j − 1) < s(j), s(j) > s(j + 1), also sind die Stellen links und rechts vom Knick j niedriger bewertet als der Knick j selbst. Dann gilt:

[figure: Regel aus P:; LBA :; \begin{aligned}[ & p & ] \\ [ & ] \\ & [ & ] \end{aligned}; Zustand p; Zustand q; \begin{aligned}[ & ] \\ [ & q & ] \\ & & [ & ] \end{aligned}; z.B. Bew.; nach links; s:]

Abbildung 3.2: Simulation im zweiten Fall (Skizze)

Beweis: Sei s mit den Voraussetzungen des Satzes gegeben, sei j wie im Satz definiert.

Sei L ∈ CSL . Sei M = (Q, Σ, Γ, B, δ, q_{0}, F) ein linear beschränkter Automat, der L erkennt.

Konstruiere eine Grammatik G = ⟨N, T, S, P ⟩ genauso wie im Beweis von Satz 3.2.1. Also ist G kontextsensitiv, und es gilt: L(G) = L(M) und ord(G) = j + 1.

Definiere nun eine Zeichenbewertung f: N ∪ T → IN wie folgt:

f(S) = 1 f(X) = 1
f(B) = 3 für alle B ∈ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd}
f(Z) = 2 für alle Z ∈ N_{Zust}
f(x) = 4 für alle x ∈ Σ

Wiederum sieht man durch einfaches Nachrechnen, daß sämtliche Regeln aus P s-schwach wachsend kontextsensitiv mit f sind, also ist G ∈ WGCSG_{s} und damit L ∈ WGCSL_{s}. ♣

Jede ungleichmäßige nicht monotone Stellenbewertung besitzt wenigstens einen Knick j, für den der erste oder der zweite Fall eintritt, der also ”Talknick“ oder ”Gipfelknick“ ist. Es bleiben also die monotonen ungleichmäßigen Stellenbewertungen zu betrachten.

Zum dritten Fall:

Bei einer monotonen Stellenbewertung ist der obige Trick mit der Zuordnung eines höheren (oder niedrigeren) Gewichtes zum Zustandsnichtterminal für die Bewegung in beide Richtungen nicht anwendbar. Allerdings funktioniert er für jeweils eine Richtung. Bei einer monoton wachsenden Stellenbewertung wird dem Zustandsnichtterminal für die Bewegung nach rechts ein höheres, für die Bewegung nach links ein niedrigeres Gewicht zugeordnet als den (einfachen) Bandnichtterminalen. Dazu wird also der Zustand zusätzlich mit der zuletzt ausgeführten Bewegungsrichtung markiert.

Beim Richtungswechsel muß auch dieses Gewicht gewechselt werden. Der Wechsel von einem niedrigeren Gewicht zu einem höheren ist in einer schwach wachsenden Grammatik kein Problem. Anders verhält sich der Wechsel von einem höheren zu einem niedrigeren Gewicht: Es stellt sich zwar heraus, daß man dieses Differenzgewicht bei ungleichmäßigen Stellenbewertungen verschwinden lassen kann, doch geht das im allgemeinen nicht an der Stelle des Richtungswechsels. Dieses Differenzgewicht muß also zunächst in einem Zeichen kodiert (wir wählen einen Stern: ⋆) neben der Richtungswechselstelle abgelegt werden, von wo es dann zum Verschluckt-werden nach rechts wandert.

[figure: LBA :; \begin{matrix}[ & p^{L} & ] \\ [ & ⋆ & ] \end{matrix}; Zustand q; \begin{matrix}[ & ] \\ [ & q^{R} & ] \end{matrix}; Richtungs-; wechsel; Zustand p; Regel in P:]

in der Satzform soll danach folgendes passieren:

[ ]…[ ][p^{L}][⋆][ ]…[ ][Verschlucker] ⟶_{wandern} [ ]…[ ][p^{L}][ ]…[ ][⋆][Verschlucker]

⟶

verschlucken

[ ]

…

[ ]

[p^{L}]

[ ]

…

[ ]

[ ]

[Verschlucker]

Abbildung 3.3: Simulation mit Verschlucker

In Abbildung 3.3 soll das veranschaulicht werden. Das Gewicht (also den Stern) nach rechts wandern zu lassen, ist bei einer monoton wachsenden Stellenbewertung kein Problem.

Wie sieht nun aber ein Verschlucker aus ? Zunächst ein Beispiel für eine konkrete Stellenbewertung.

Beispiel 3.2.3 : Betrachte die ungleichmäßige Stellenbewertung id definiert durch id(i) = i für alle i ∈ IN^{+}. Definiere eine Menge N_{Verschl} von Zeichen durch N_{Verschl} = \{R,[\begin{matrix}R \\ ⋆ \end{matrix}], M,[\begin{matrix}M \\ ⋆ \end{matrix}], A, B, V \} und

eine Menge P_{Verschl} von Regeln durch P_{Verschl} = {(R1), (R2), (R3)} mit:

(R1) [\begin{matrix}R \\ ⋆ \end{matrix}]M → R[\begin{matrix}M \\ ⋆ \end{matrix}]  (R2) [\begin{matrix}M \\ ⋆ \end{matrix}]AV → MBA  (R3) BA → AV

Mit diesen Regeln aus P_{Verschl} sind folgende Ableitungsschritte möglich:

[\begin{matrix}R \\ ⋆ \end{matrix}]MAV ⟹_{R1} R[\begin{matrix}M \\ ⋆ \end{matrix}]AV ⟹_{R2} RMBA ⟹_{R3} RMAV

Definiere nun eine Zeichenbewertung f: N_{Verschl} → IN durch:

\begin{matrix}f(R) = 1, & f([\begin{matrix}R \\ ⋆ \end{matrix}]) = 2, & f(M) = 1, & f([\begin{matrix}M \\ ⋆ \end{matrix}]) = 2, \\ f(A) = 1, & f(B) = 8, & f(V) = 5 \end{matrix}

Damit ergeben sich für die Regeln aus P_{Verschl} folgende Bewertungen:

für (R1): : 1 · 2 + 2 · 1 = 4 < 1 · 1 + 2 · 2 = 5 für (R2): : 1 · 2 + 2 · 1 + 3 · 5 = 19 < 1 · 1 + 2 · 8 + 3 · 1 = 20 für (R3): : 1 · 8 + 2 · 1 = 10 < 1 · 1 + 2 · 5 = 11

Das heißt, diese Regeln sind id-schwach wachsend kontextsensitiv mit f. Beim Aufbau dieser Regeln wird ausgenutzt, daß bei der Stellenbewertung id ein Gewicht beim Transport von der ersten zur zweiten Stelle halbiert werden kann (was in R_{2} mit dem ”Gewicht“ 1 des Sterns passiert) und beim Transport von der dritten zur zweiten Stelle nur veranderthalbfacht werden muß (was in R_{2} mit dem ”Gewicht“ f(V) − f(A) = 4 passiert). Dabei sind die Gewichte so gewählt, daß durch die Halbierung des im B angehäuften Gewichtes ⌈\frac{1}{2} · 1⌉ + \frac{3}{2} · 4 = 7 = f(B) − f(A) die Ausgangssituation wieder hergestellt wird. Die Satzform MAV mit der Regelmenge P_{Verschl} verschluckt also ein in den Stern kodiertes Gewicht.

Auch im Falle einer allgemeinen (kurz vor und kurz nach einem Knick) monoton wachsenden Stellenbewertung wollen wir eine solche Satzform mit solchen Regeln einen Verschlucker nennen.

Definition 3.2.4 : Sei s eine ungleichmäßige Stellenbewertung. Für den einen Knick j von s gelte s(j − 1) ≤ s(j) ≤ s(j + 1). Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik, sei f eine Zeichenbewertung für G und seien A_{1}, A_{2} ⊆ N, A_{1}, A_{2} ≠ ∅ gegeben mit f(X) < f(Y) für alle X ∈ A_{1}, Y ∈ A_{2}. Dann heißt V_{s} = (A_{1}, A_{2}, N_{Verschl}, P_{Verschl}) mit

N_{Verschl} = \{M,[\begin{matrix}M \\ ⋆ \end{matrix}], A, B, V \}

und P_{Verschl} definiert durch:

R_{1} = \{ \begin{matrix}\{αY M → αX[\begin{matrix}M \\ ⋆ \end{matrix}]| \begin{matrix}α ∈ (N ∪ T)^{∗}, |α| = j − 1, \\ Y ∈ A_{2}, X ∈ A_{1} \end{matrix} \} & falls s(j − 1) = s(j) \\ \{αY M → αX[\begin{matrix}M \\ ⋆ \end{matrix}]| \begin{matrix}α ∈ (N ∪ T)^{∗}, |α| = j − 2, \\ Y ∈ A_{2}, X ∈ A_{1} \end{matrix} \} & falls s(j − 1) < s(j) \end{matrix}

R_{2} = \{α[\begin{matrix}M \\ ⋆ \end{matrix}]AV → αMBA | α ∈ (N ∪ T)^{∗}, |α| = j − 2\}

R_{3} = {αMBA → αMAV | α ∈ (N ∪ T)^{∗}, |α| = j − 3}

P_{Verschl} = R_{1} ∪ R_{2} ∪ R_{3}

ein Verschlucker zu G und s, falls es eine Zeichenbewertung f′: N ∪ N_{Verschl} ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} gibt mit f′|_{N∪T} = f und sämtliche Regeln aus P_{Verschl} sind s-schwach wachsend mit f′.

Zu bemerken ist dabei, daß die beiden Fälle für R_{1} sowie R_{2} und R_{3} sich durch die Länge des Regelvorspanns α unterscheiden und daß für A_{1} und A_{2} Mengen von Zeichen (statt wie in Beispiel 3.2.3 Zeichen R und [\begin{matrix}R \\ ⋆ \end{matrix}]) erlaubt werden, da dies bei der Simulation eines linear

beschränkten Automaten im Beweis von Satz 3.2.6 benutzt wird.

Die Frage ist nun, ob es zu jeder monoton wachsenden ungleichmäßigen Stellenbewertung s und zu jeder s-schwach wachsend kontextsensitiven Grammatik einen Verschlucker gibt. Es stellt sich heraus, daß die einzige notwendige Voraussetzung für G = ⟨N, T, S, P ⟩ die ist, daß es eine Zeichenbewertung f gibt, die wenigstens zwei Zeichen aus N unterschiedlich bewertet.

Satz 3.2.5 : Sei s eine monoton wachsende ungleichmäßige Stellenbewertung, sei j ein Knick von s, und sei s(j −1) ≤ s(j) ≤ s(j +1). Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik, sei f eine Zeichenbewertung für G. Seien A_{1}, A_{2} ⊆ N nichtleere Teilmengen von N mit f(X) < f(Y) für alle X ∈ A_{1}, Y ∈ A_{2}. Dann gibt es zu G und s einen Verschlucker V_{s} = (A_{1}, A_{2}, N_{Verschl}, P_{Verschl}). Weiterhin gilt: G′ = ⟨N ∪ N_{Verschl}, T, S, P ∪ P_{Verschl}⟩ ist s-schwach wachsend kontextsensitiv, und für jedes Paar von Satzformen (vX, wY) mit v, w ∈ (N ∪ T)^{∗}, X ∈ A_{1}, Y ∈ A_{2} mit

|v|, |w| ≥ \{ \begin{matrix}j − 1 & falls s(j − 1) = s(j) \\ j − 2 & falls s(j − 1) < s(j) \end{matrix} und vX ⟹^{∗}_{G} wY gilt:

vXMAV ⟹^{∗}_{G′} wXMAV

Beweis: Seien also die Voraussetzungen des Satzes erfüllt und die Definitionen darin angenommen. Da die Regeln aus P_{Verschl} kontextsensitiv sind und ihre Ordnungen j + 1 nicht übersteigen, genügt es zu zeigen (wegen Satz 2.1.5):

(i) die Regeln aus P_{Verschl} sind s-schwach wachsend kontextsensitv mit einer Funktion f′: N ∪ N_{Verschl} ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} , für die gilt: f′ |_{N∪T} = f

(ii) für alle Paare von Satzformen (vX, wY) mit v, w ∈ (N ∪ T)^{∗}, X ∈ A_{1}, Y ∈ A_{2} mit

|v|, |w| ≥ \{ \begin{matrix}j − 1 & falls s(j − 1) = s(j) \\ j − 2 & falls s(j − 1) < s(j) \end{matrix} und vX ⟹^{∗}_{G} wY gilt:

vXMAV ⟹^{∗}_{G′} wY MAV

zu (i) : Definiere μ := max{f(Y) | Y ∈ A_{2}} − min{f(X) | X ∈ A_{1}}. Definiere f′: N ∪ N_{Verschl} ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} durch:

\begin{aligned}f′(X) & = f(X) für alle X ∈ N ∪ T \\ f′(M) & = 1,  f′([\begin{matrix}M \\ ⋆ \end{matrix}]) = 1 + μ,  f′(A) = 1 \\ f′(B) & = \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · (s(j − 1) · s(j) · μ + s(j) + s(j + 1)) + 1 \\ f′(V) & = \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · ((s(j − 1))^{2} · μ + s(j − 1) + s(j)) + 1 \end{aligned}

Mit dieser Zeichenbewertung gilt:

s(j) · f′(B) − s(j + 1) · f′(V)
= \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · ( (s(j − 1) · s(j)^{2} − s(j − 1)^{2} · s(j + 1)) · μ

+ s(j)^{2} − s(j + 1) · s(j − 1) + s(j + 1) · s(j) − s(j) · s(j + 1)) + s(j) − s(j + 1)

= s(j − 1) · μ + 1 + s(j) − s(j + 1)

und weiterhin

s(j) · f′(V) − s(j − 1) · f′(B)
= \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · ( (s(j) · s(j − 1)^{2} − s(j − 1)^{2} · s(j)) · μ

+ s(j) · s(j − 1) + s(j − 1) · s(j) + s(j)^{2} − s(j − 1) · s(j + 1)) + s(j) − s(j − 1)

= 1 + s(j) − s(j − 1)

Für die Bewertungen der Regeln aus P_{Verschl} gilt::

für R_{1} : Im ersten Fall:

Da die ersten j −1 Zeichen sich in jeder dieser Regeln aus R_{1} nicht ändern, hängt die Frage, ob diese Regeln s-schwach wachsend kontextsensitv mit f′ sind, nur von der

Bewertung des Regelteils ”Y M → X[\begin{matrix}M \\ ⋆ \end{matrix}]“ mit X ∈ A_{1}, Y ∈ A_{2} ab. Da s monoton

wachsend ist, folgt aus s(j − 1) = s(j), daß s(j) < s(j + 1) (da s ungleichmäßig ist).

Wegen f′(Y) − f′(X) ≤ f′([\begin{matrix}M \\ ⋆ \end{matrix}]) − f′(M) = μ folgt daraus, daß die Regeln aus R_{1}

s-schwach wachsend kontextsensitiv mit f′ sind. Im Zweiten Fall

folgt die Behauptung analog wegen s(j − 1) < s(j). für R_{2} : Da sich die ersten j −2 Zeichen in jeder dieser Regeln nicht ändern, hängt die Frage, ob diese Regeln s-schwach wachsend kontextsensitiv mit f′ sind, nur von der Bewertung des

Regelteils ”[\begin{matrix}M \\ ⋆ \end{matrix}]AV → MBA“ ab. Das heißt es ist zu zeigen:

\begin{matrix}s(j − 1) · f′([\begin{matrix}M \\ ⋆ \end{matrix}]) + s(j) · f′(A) + s(j + 1) · f′(V) \\ < s(j − 1) · f′(M) + s(j) · f′(B) + s(j + 1) · f′(A) \end{matrix}

Wegen s(j)·f′(B)−s(j +1)·f′(V) = s(j −1)·μ+1+s(j)−s(j +1) (s.o.) ist das gleichwertig mit:

s(j − 1) · (f′([\begin{matrix}M \\ ⋆ \end{matrix}]) − f′(M)) + s(j) · 1

< s(j − 1) · μ + 1 + s(j) − s(j + 1) + s(j + 1) · 1

⇔ s(j − 1) · μ < s(j − 1) · μ + 1

Damit sind die Regeln aus R_{2} s-schwach wachsend kontextsensitiv mit f′. für R_{3} : Da sich auch hier die ersten j − 2 Zeichen in keiner der Regeln ändern, hängt die Frage, ob diese Regeln s-schwach wachsend kontextsensitiv mit f′ sind, nur von der Bewertung des Regelteils ”BA → AV “ ab. Das heißt es ist zu zeigen:

s(j − 1) · f′(B) + s(j) · f′(A) < s(j − 1) · f′(A) + s(j) · f′(V)

Wegen s(j) · f′(V) − s(j − 1) · f′(B) = 1 + s(j) − s(j − 1) (s.o.) ist dies gleichwertig mit:

\begin{aligned}& s(j) · 1 < s(j − 1) · 1 + 1 + s(j) − s(j − 1) \\ ⇔ & s(j) < s(j) + 1 \end{aligned}

Also sind auch die Regeln aus R_{3} s-schwach wachsend kontextsensitiv mit f′.

zu (ii) : Sei (vX, wY) ein Paar von Satzformen aus (N ∪ T)^{∗} mit

|v|, |w| ≥ \{ \begin{matrix}j − 1 & falls s(j − 1) = s(j) \\ j − 2 & falls s(j − 1) < s(j) \end{matrix} und vX ⟹^{∗}_{G} wY

Aus der Definition von G′ folgt sofort vX ⟹^{∗}_{G′} wY, und daraus folgt: vXMAV ⟹^{∗}_{G′} wY MAV. Auf die Satzform wY MAV sind (passende) Regeln aus R_{1}, R_{2} und R_{3} nacheinander anwendbar, und daraus folgt die Behauptung.

♣

Vereinbarung: Ist s eine Stellenbewertung, G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} und V_{s} = (A_{1}, A_{2}, N_{Verschl}, P_{Verschl}) ein Verschlucker zu G und s, so spreche man für jede Grammatik G′ = ⟨N′, T′, S′, P′⟩ mit N ∪ N_{Verschl} ⊆ N′, T ⊆ N′ ∨ T ⊆ T′, P ∪ P_{Verschl} ⊆ P′ mit G′ ∈ WGCSL_{s} von V_{s} als von einem Verschlucker in G′.

Ein Verschlucker läßt sich also auch in eine Grammatik einbauen, die einen linear beschränkten Automaten simuliert, und kann dort eigesetzt werden, um die bei jedem Rechts-Links-Richtungswechsel auftretenden Sterne (⋆) wieder zu verschlucken, damit kein (Gewichts-) Stau entsteht.

Gegenüber der Konstruktion in den Sätzen 3.1.1, 3.2.1 und 3.2.2 ändert sich außerdem, daß die Grammatik, um durch das Anhängen des Verschluckers nicht zu lange Wörter zu erzeugen, eigentlich einen linear beschränkten Automaten simuliert, der auf dem halben Platz arbeitet (mit getupelter Eingabe), und dann die Eingabe expandiert, wobei der Verschlucker verschluckt wird. Weiterhin ändert sich, daß die Bedingungen für die Randbehandlung nur noch für den linken Rand aufrechterhalten werden, und auch nur dann, wenn die Stellenbewertung auf einem Anfangsstück konstant ist.

Wie oben erwähnt nehmen wir den Fall s(1) = 0 für eine ungleichmäßige Stellenbewertung s hier aus und verweisen dazu auf Kapitel 5.1.

Die Konstruktion soll jetzt konkret durchgeführt werden.

Satz 3.2.6 : Sei s eine monoton wachsende ungleichmäßige Stellenbewertung mit s(1) ≠ 0. Dann gilt:

Beweis: Sei s mit den Voraussetzungen des Satzes gegeben, sei j der erste Knick von s. Da s monoton wachsend ist, ist s(j − 1) ≤ s(j) ≤ s(j + 1), und wegen s(1) ≠ 0 ist s(i) ≠ 0 für alle von s bewerteten Stellen i. Sei L ∈ CSL . Sei M = (Q, Σ, Γ, □, δ, q_{0}, F) ein linear beschränkter Automat, der L erkennt. Sei M_{2} = (Q_{2}, Σ_{2}, Γ_{2}, □_{2}, δ_{2}, q_{0,2}, F_{2}) der nach Satz 1.2.3 zu M konstruierte lineare Automat, der die Sprache

L_{2} := {w ∈ (Σ^{2})^{∗} ∪ (Σ^{2})^{∗} · Σ^{1}| nat(w) ∈ L}

erkennt. Konstruiere nun eine kontextsensitive Grammatik G_{2} = ⟨N_{2}, Σ_{2} ∪ {•}, S, P_{2}⟩. Dafür seien Γ′_{2} = {a′ | a ∈ Γ_{2}} und Γ′′_{2} = {a′′ | a ∈ Γ_{2}} wie im Beweis von Satz 3.1.1 markierte Kopien des Arbeitsalphabets Γ_{2} für den linken bzw. rechten Rand. Für die Menge N_{2} der Nichtterminale definiere N_{BandAnf}, N_{Band} und N_{BandEnd} zu M_{2} wie im Beweis von Satz 3.1.1 sowie

N_{Zustlinks} = \{[\begin{matrix}x \\ a^{∗} \\ q^{L} \end{matrix}]| x ∈ Σ, a^{∗} ∈ Γ ∪ Γ′, q ∈ Q\}

N_{Zustrechts} = \{[\begin{matrix}x \\ a^{∗} \\ q^{R} \end{matrix}]| x ∈ Σ, a^{∗} ∈ Γ ∪ Γ′′, q ∈ Q\}

N_{Gewicht} = \{[\begin{matrix}x \\ a^{∗} \\ ⋆ \end{matrix}]| x ∈ Σ, a^{∗} ∈ Γ ∪ Γ′′\}

N_{Verschl} = \{M,[\begin{matrix}M \\ ⋆ \end{matrix}], A, B, V \}

Es wird also festgelegt, daß der Zustand auf dem linken Rand immer mit einer Linksbewegung und auf dem rechten Rand immer mit einer Rechtsbewegung markiert wird. Die Menge der Nichtterminale definiere durch:

N_{2} = {S, X, Y } ∪ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd} ∪ N_{Zustlinks} ∪ N_{Zustrechts}
∪ N_{Gewicht} ∪ N_{Verschl}

Die Regelmenge P_{2} bestehe aus den folgenden Regeln:

Dabei seien x, y, z ∈ Σ_{2}, a, b, c, d ∈ Γ_{2}, dazu a′, c′ ∈ Γ′_{2} und a′′, b′′, c′′ ∈ Γ′′_{2} gerade die jeweiligen markierten Kopien von a, c für den linken und von a, b, c für den rechten Rand. Es seien H ∈ {L, R}, p, q, q̃ ∈ Q_{2} sowie [b^{∗} = b ∧ d^{∗} = d] ∨ [b^{∗} = b′′ ∧ d^{∗} = d′′] und außerdem

α_{∗}, α_{c} ∈ (N_{Band})^{∗} ∪ N_{BandAnf} (N_{Band})^{∗}
α_{e} ∈ (N_{Band})^{∗} N_{BandEnd}
mit |α_{∗}| = |α_{e}| = j − 2 (also für j = 2 ist α_{∗} = α_{e} = ε ),
|α_{c}| = j − 1, falls s(1) = s(2), α_{c} = ε sonst

Banderzeugung: Falls s(1) < s(2) :

S →[\begin{matrix}a \\ a′ \\ q_{0,2} \end{matrix}]X

Falls s(1) = s(2) und also s bis zum ersten Knick konstant: Falls q_{0,2}x_{1} … x_{j−1} _{M}^{∗} a_{1} … a_{j−1}q□, dann enthält P_{2} die Regel:

S →[\begin{matrix}x_{1} \\ a′_{1} \end{matrix}][\begin{matrix}x_{2} \\ a_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ a_{j−1} \end{matrix}][\begin{matrix}b \\ b \\ q \end{matrix}]X

und außerdem enthält P_{2} in beiden Fällen die Regeln:

\begin{matrix}X →[\begin{matrix}a \\ a \end{matrix}]X, X →[\begin{matrix}a \\ a′′ \end{matrix}]Y \\ Y → MAV \end{matrix}

Bewegung nach rechts: Falls (p, c, R) ∈ δ_{2}(q, a), so enthält P_{2} die folgenden Regeln:

α_{c}[\begin{matrix}x \\ a \\ q^{H} \end{matrix} ][\begin{matrix}y \\ b^{∗} \end{matrix}]→ α_{c}[\begin{matrix}x \\ c \end{matrix}][\begin{matrix}y \\ b^{∗} \\ p^{R} \end{matrix}]

Bewegung am rechten Rand: Falls (q̃, c, R) ∈ δ_{2}(q, a) und (p, □, L) ∈ δ_{2}(q̃, □), dann enthält P_{2} die Regel:

[\begin{matrix}x \\ a′′ \\ q^{R} \end{matrix}]→[\begin{matrix}x \\ c′′ \\ p^{R} \end{matrix}]

Bewegung nach links: Falls (p, d, L) ∈ δ_{2}(q, b), so enthält P_{2} die folgenden Regeln:

α_{c}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b \\ q^{L} \end{matrix}]→ α_{c}[\begin{matrix}x \\ a \\ p^{L} \end{matrix}][\begin{matrix}y \\ d \end{matrix}], α_{c}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b^{∗} \\ q^{R} \end{matrix}]→ α_{c}[\begin{matrix}x \\ a \\ p^{L} \end{matrix}][\begin{matrix}y \\ d^{∗} \\ ⋆ \end{matrix}]

Bewegung am linken Rand: Falls s(1) < s(2): Falls (q̃, c, L) ∈ δ(q, a) und (p, □, R) ∈ δ_{2}(q̃, □), dann enthält P_{2} die Regel:

[\begin{matrix}x \\ a′ \\ q^{L} \end{matrix}]→[\begin{matrix}x \\ c′ \\ p^{L} \end{matrix}]

Falls s(1) = s(2) und also s bis zum ersten Knick konstant: Falls (q̃, c, L) ∈ δ(q, a) ∧ a_{1} … a_{j−2}q̃a_{j−1}cb _{M}^{∗} c_{1} … c_{j−1}epb, enthält P_{2} die folgende Regel:

[\begin{matrix}x_{1} \\ a′_{1} \end{matrix}][\begin{matrix}x_{2} \\ a_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ a_{j−1} \end{matrix}][\begin{matrix}x \\ a \\ q \end{matrix}][\begin{matrix}y \\ b \end{matrix}]→[\begin{matrix}x_{1} \\ c′_{1} \end{matrix}][\begin{matrix}x_{2} \\ c_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ c_{j−1} \end{matrix}][\begin{matrix}x \\ e \end{matrix}][\begin{matrix}y \\ b \\ p \end{matrix}]

Gewichtswanderung:

α_{c}[\begin{matrix}x \\ a \\ ⋆ \end{matrix}][\begin{matrix}y \\ b^{∗} \end{matrix}]→ α_{c}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b^{∗} \\ ⋆ \end{matrix}],

Gewichte ”verschlucken”:

(R1) = \{ \begin{matrix}α_{∗}α_{+}[\begin{matrix}y \\ b′′ \\ ⋆ \end{matrix}]M → α_{∗}α_{+}[\begin{matrix}y \\ b′′ \end{matrix}][\begin{matrix}M \\ ⋆ \end{matrix}] & falls s(j − 1) = s(j) \\ α_{∗}[\begin{matrix}y \\ b′′ \\ ⋆ \end{matrix}]M → α_{∗}[\begin{matrix}y \\ b′′ \end{matrix}][\begin{matrix}M \\ ⋆ \end{matrix}] & falls s(j − 1) < s(j) \end{matrix}

(R2) = α_{e}[\begin{matrix}M \\ ⋆ \end{matrix}]AV → α_{e}MBA

(R3) = α_{c}BA → α_{c}AV

Akzeptieren: Falls (q_{F} , c, R) ∈ δ_{2}(q, a) mit q_{F} ∈ F_{2}, enthält P_{2} die Regel:

[\begin{matrix}x \\ a′′ \\ q^{R} \end{matrix}]→ x

Eingabe in Terminale umwandeln:

\begin{matrix}[\begin{matrix}x \\ a \end{matrix}]y → xy,  [\begin{matrix}x \\ a′ \end{matrix}]y → xy \\ xM → x•, •AV → • • • \end{matrix}

Diese Grammatik ist kontextsensitiv. Es ist ord(G_{2}) = j + 1. Definiere eine Zeichenbewertung f′: N_{2} ∪ Σ_{2} → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} durch:

f′(S) = 1,  f′(X) = 1,  f′(Y) = 1
f′(X_{B}) = 3 für alle X_{B} ∈ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd}
f′(Z_{L}) = 2 für alle Z_{L} ∈ N_{Zustlinks}
f′(Z_{R}) = 4 für alle Z_{R} ∈ N_{Zustrechts}
f′(X_{G}) = 6 für alle X_{G} ∈ N_{Gewicht}

f′(M) = 1,  f′([\begin{matrix}M \\ ⋆ \end{matrix}]) = 4
f′(A) = 1
f′(B) = \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · (s(j − 1) · s(j) · 3 + s(j) + s(j + 1)) + 1
f′(V) = \frac{1}{s(j)^{2}−s(j−1)·s(j+1)} · (s(j − 1)^{2} · 3 + s(j − 1) + s(j)) + 1
f′(x) = 4 für alle x ∈ Σ_{2}
f′(•) = f′(V) + 1

Man sieht durch einfaches Nachrechnen, daß sämtliche Regeln aus P_{2}, in denen keine Zeichen aus N_{Verschl} vorkommen, entweder s-schwach wachsend mit f′ oder Kettenregeln mit gleichem Gewicht rechts und links sind.

Für die letzten beiden Regeln aus der Umwandlung in Terminale gilt: Wegen f′(•) > f′(V) > f′(A) > f′(M) und s(1) ≠ 0, s(2) ≠ 0 (s.o.) sind auch diese Regeln s-schwach wachsend mit f′. Die Funktionswerte von f′ für die Zeichen aus N_{Verschl} wurden gemäß dem Beweis von Satz 3.2.5 erklärt (mit μ = 3), daher erkennt man, daß auch die Regeln der Formen (R1) − (R3) s-schwach wachsend mit f′ sind, also ist (wegen Satz 2.1.2) L(G_{2}) ∈ WGCSL_{s}. Sei nun G′_{2} ∈ WGCSG_{s} die nach dem Beweis von Satz 2.1.2 zu G_{2} gebildete äquivalente Grammatik ohne Kettenregeln; f′ ist nach Satz 2.1.2 Zeichenbewertung für G′_{2}. Weiterhin ist V_{s} = (A_{1}, A_{2}, N_{Verschl}, P_{Verschl}) mit

R_{1} bestehend aus den Regeln (R1), R_{2} bestehend aus den Regeln (R2), R_{3} bestehend aus den Regeln (R3) und P_{Verschl} = R_{1} ∪ R_{2} ∪ R_{3} sowie

A_{1} = N_{BandEnd}, A_{2} = \{[\begin{matrix}x \\ a′′ \\ ⋆ \end{matrix}]| x ∈ Σ, a′′ ∈ Γ′′\}

und N_{Verschl} wie oben erklärt

ein Verschlucker in G′_{2}. Ohne die Regeln aus P_{Verschl} kann man in G_{2} (und damit in G′_{2}) aus einer Satzform v ∈ (N_{2} \ (N_{Verschl} ∪ N_{Gewicht}))^{∗}, die eine Konfiguration K von M_{2} darstellt, eine Satzform w ∈ (N_{2} \ (N_{Verschl} ∪ N_{Gewicht}))^{∗} N_{Gewicht} ableiten, die eine Konfiguration K′ von M_{2} darstellt, für welche gilt:

K _{M_{2}}^{∗} K′ und auf dem Rechenweg von K nach K′ wurde ein Rechts-Links-Richtungswechsel ausgeführt.

(Falls s(1) < s(2), ist dazu die Mindestlänge von v (und auch u) 3, sonst ist sie j + 2.) Nun läßt sich Satz 3.2.5 anwenden (auf G′_{2}) und das in den Stern (⋆) kodierte Gewicht im letzten Zeichen von w verschlucken, falls w hinreichend lang ist. Diese hinreichende Länge ist nach Satz 3.2.5 (dabei entspricht das letzte Zeichen von w dem X bzw. dem Y aus dem genannten Satz): falls s(1) < s(2) : j − 1, sonst: j.

Das Ganze läßt sich sukzessive wiederholen, und es wird einsichtig, daß mit

l = \{ \begin{matrix}j − 1, & falls s(1) < s(2) \\ j + 2, & sonst \end{matrix}

gilt:

L(G_{2}) = L(G′_{2}) = {w ∈ (Σ_{2} ∪ {•})^{∗} | w = w̃ • • • mit w̃ ∈ L_{2} ∧ |w̃| ≥ l }

Nun erweitern wir G_{2} zu einer Grammatik G mit L(G) = L.

Konstruiere also G = ⟨N, Σ, S, P ⟩ durch:

N := N_{2} ∪ Σ_{2}, P := P_{2} ∪ P_{Schluß}

wobei N_{2}, Σ_{2}, S, P_{2} aus der obigen Grammatik G_{2} stammen und P_{Schluß} aus den folgenden Regeln besteht:

S → w, w ∈ L, |w| < max{6, 2 · l}
(a, b)• → ab, (a, b) → ab, (a) → a für alle a, b ∈ Σ, also alle (a, b), (a) ∈ Σ_{2}
und falls s(1) < s(2) : a• → •a für alle a ∈ Σ
und falls s(1) = s(2) : x_{1} … x_{j−1}a• → x_{1} … x_{j−1} • a
für alle x_{1}, …, x_{j−1} ∈ Σ_{2} ∪ Σ, a ∈ Σ

Diese Grammatik vollzieht zunächst die Wirkungsweise von G_{2} nach und erzeugt dann aus deren Ergebnis, einem Wort w ∈ L_{2} mit |w| ≥ l, das Wort nat(w) ∈ L. Dabei werden für |nat(w)| ≥ 6 die Punkte (•) eliminiert. Wörter w ∈ L mit |w| < 2 · l oder |w| < 6 werden direkt erzeugt. Also gilt L(G) = L.

Mit der Funktion f: N ∪ Σ → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} definiert durch:

f(Z) = f′(Z) für alle Z ∈ N ∪ Σ_{2} ∪ {•}
f(x) = f′(•) + 1 für alle x ∈ Σ

und Satz 2.1.2 sieht man: L = L(G) ∈ WGCSL_{s}. ♣

Zum vierten Fall:

Bei einer monoton fallenden ungleichmäßigen Stellenbewertung funktioniert die Simulation eines linear beschränkten Automaten im Prinzip analog: Für die Bewegung nach rechts wird dem Zustandsnichtterminal ein niedrigeres, für die Bewegung nach links dagegen ein höheres Gewicht zugeordnet als den einfachen Bandnichtterminalen. Das Differenzgewicht, das beim Richtungswechsel (diesmal von einer Links- zu einer Rechts-Bewegung) abgelegt wird, wandert nach links, wo es verschluckt wird.

Wie sieht nun ein Verschlucker bei einer monoton fallenden Stellenbewertung aus ?

Man sollte meinen, man bräuchte nur die Regeln eines Verschluckers für eine monoton wachsende Stellenbewertung zu spiegeln.

Dazu wiederum zunächst ein Beispiel:

Beispiel 3.2.7 : Betrachte die ungleichmäßige Stellenbewertung īd_{3} definiert durch īd_{3}(1) = 3, īd_{3}(2) = 2, īd_{3}(3) = 1, īd_{3}(i) sei nicht definiert für alle i ≥ 4. īd_{3} ist also sozusagen eine Transposition von id (siehe Beispiel 3.2.3) begrenzt auf drei Stellen. Definiere eine Menge N_{Verschl} von Zeichen wie in Beispiel 3.2.3 und eine Menge P_{Verschl} von Regeln durch P_{Verschl} = {(R1), (R2), (R3)} mit:

(R1) M[\begin{matrix}R \\ ⋆ \end{matrix}]→[\begin{matrix}M \\ ⋆ \end{matrix}]R  (R2) V A[\begin{matrix}M \\ ⋆ \end{matrix}]→ ABM  (R3) AB → V A

also mit gerade den Spiegelungen der Regeln aus Beispiel 3.2.3. Dann folgt für eine Zeichenbewertung f: N_{Verschl} → IN , mit der alle Regeln aus P_{Verschl} s-schwach wachsend sind und

für die f(R) < f([\begin{matrix}R \\ ⋆ \end{matrix}]) gilt:

aus (R1) : {2 · (f([\begin{matrix}R \\ ⋆ \end{matrix}]) − f(R)) < 3 · (f([\begin{matrix}M \\ ⋆ \end{matrix}]) − f(M)) \atop ⇒ f([\begin{matrix}M \\ ⋆ \end{matrix}]) − f(M) > 0  (1)}

aus (R2) : 3 · f(V) + 2 · f(A) + 1 · f([\begin{matrix}M \\ ⋆ \end{matrix}]) < 3 · f(A) + 2 · f(B) + 1 · f(M) ; ⇔ f([\begin{matrix}M \\ ⋆ \end{matrix}]) − f(M) + 3 · f(V) < 2 · f(B) + f(A) ; ⇒_{mit(1)} 3 · f(V) < 2 · f(B) + f(A)  (2)

aus (R3) : 3 · f(A) + 2 · f(B) < 3 · f(V) + 2 · f(A)

⇔ 2 · f(B) + f(A) < 3 · f(V)

und das ist ein Widerspruch zu (2).

Das heißt eine solche Zeichenbewertung existiert gar nicht. Wenn sich aus den Regeln die gleichen Ungleichungen ergeben würden wie in Beispiel 3.2.3, dann würde die Konstruktion funktionieren. Um das zu erreichen, braucht man nur an die gegenüber Beispiel 3.2.3 gespiegelte Regel (R3) vorne ein dummy-Symbol D anzufügen, das nicht verändert wird und durch das die maßgeblichen Regelteile um eine Stelle verschoben werden.

Definiere also N_{Verschl} = \{D, R,[\begin{matrix}R \\ ⋆ \end{matrix}], M,[\begin{matrix}M \\ ⋆ \end{matrix}], A, B, V \} und P_{Verschl} = \{(R1), (R2), (R3)\} mit

(R1) und (R2) wie oben und

(R3) DAB → DV A

Mit diesen Regeln aus P_{Verschl} sind folgende Ableitungsschritte möglich:

DV AM[\begin{matrix}R \\ ⋆ \end{matrix}] ⟹_{R1} DV A[\begin{matrix}M \\ ⋆ \end{matrix}]R ⟹_{R2} DABMR ⟹_{R3} DV AMR

Definiere nun eine Zeichenbewertung f: N_{Verschl} → IN durch:

\begin{matrix}f(R) = 1, & f([\begin{matrix}R \\ ⋆ \end{matrix}]) = 2, & f(M) = 1, & f([\begin{matrix}M \\ ⋆ \end{matrix}]) = 2, \\ f(A) = 1, & f(B) = 8, & f(V) = 5 \end{matrix}

Damit ergeben sich für die Regeln aus P_{Verschl} folgende Bewertungen:

für (R1) : 3 · 1 + 2 · 2 = 7 < 3 · 2 + 2 · 1 = 8 für (R2) : 3 · 5 + 2 · 1 + 1 · 2 = 19 < 3 · 1 + 2 · 8 + 1 · 1 = 20 für (R3) : 3 · 1 + 2 · 1 + 1 · 8 = 13 < 3 · 1 + 2 · 5 + 1 · 1 = 14

Das heißt, diese Regeln sind īd_{3}-schwach wachsend kontextsensitiv mit f. Für den Aufbau dieser Regeln wird also die Ungleichmäßigkeit von īd_{3} in derselben Weise ausgenutzt wie die von id in Beispiel 3.2.3. Die Satzform V AM mit der Regelmenge P_{Verschl} verschluckt also ein in den Stern kodiertes Gewicht.

Genauso wie im Falle (kurz vor und kurz nach einem Knick) monoton wachsender ungleichmäßiger Stellenbewertungen wollen wir auch für (kurz vor und kurz nach einem Knick) monoton fallende Stellenbewertungen Verschlucker erklären. Gegenüber Definition 3.2.4 ändert sich außer der Transposition der maßgeblichen Regelteile, daß in R_{1} der Regelvorspann eventuell die Satzform des Verschluckers enthält und in R_{2} und R_{3} aus dummy-Symbolen besteht. Definition 3.2.8 : Sei s eine ungleichmäßige Stellenbewertung, sei j ein Knick von s, und sei s(j − 1) ≥ s(j) ≥ s(j + 1). Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik, sei f eine Zeichenbewertung für G und seien A_{1}, A_{2} ⊆ N, A_{1}, A_{2} ≠ ∅ gegeben mit f(X) < f(Y) für alle X ∈ A_{1}, Y ∈ A_{2}. Dann heißt V_{s} = (A_{1}, A_{2}, N_{Verschl}, P_{Verschl}) mit

N_{Verschl} = \{D, M,[\begin{matrix}M \\ ⋆ \end{matrix}], A, B, V \}

bestehend aus neuen Symbolen und P_{Verschl} definiert durch:

R_{1} = \begin{cases}\{MY →[\begin{matrix}M \\ ⋆ \end{matrix}]X | Y ∈ A_{2}, X ∈ A_{1}\} & falls j = 2 und s(1) < s(2) \\ \{AMY → A[\begin{matrix}M \\ ⋆ \end{matrix}]X | Y ∈ A_{2}, X ∈ A_{1}\} & falls j = 2 und s(1) = s(2) oder j = 3 und s(2) < s(3) \\ \{V AMY → V A[\begin{matrix}M \\ ⋆ \end{matrix}]X | Y ∈ A_{2}, X ∈ A_{1}\} & falls j = 3 und s(2) = s(3) oder j = 4 und s(3) < s(4) \\ \{D^{j−3}V AMY → D^{j−3}V A[\begin{matrix}M \\ ⋆ \end{matrix}]X | Y ∈ A_{2}, X ∈ A_{1}\} & falls j ≥ 4 und s(j − 1) = s(j) \\ \{D^{j−4}V AMY → D^{j−4}V A[\begin{matrix}M \\ ⋆ \end{matrix}]X | Y ∈ A_{2}, X ∈ A_{1}\} & falls j ≥ 5 und s(j − 1) < s(j) \end{cases}

R_{2} = \{D^{j−2}V A[\begin{matrix}M \\ ⋆ \end{matrix}]→ D^{j−2}ABM\}

R_{3} = {D^{j−1}BA → D^{j−1}AV }

P_{Verschl} = R_{1} ∪ R_{2} ∪ R_{3}

ein Verschlucker zu G und s, falls es eine Zeichenbewertung f′: N ∪ N_{Verschl} ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} gibt mit: f′|_{N∪T} = f und sämtliche Regeln aus P_{Verschl} sind s-schwach wachsend mit f′.

Genauso wie im Falle monoton wachsender ungleichmäßiger Stellenbewertungen stellt sich heraus, daß es zu jeder monoton fallenden Stellenbewertung s und zu jeder s-schwach wachsend kontextsensitiven Grammatik G = ⟨N, T, S, P ⟩, für die es eine Zeichenbewertung f gibt, die wenigstens zwei Zeichen aus N unterschiedlich bewertet, einen Verschlucker gibt.

Satz 3.2.9 : Sei s eine monoton fallende ungleichmäßige Stellenbewertung, sei j ein Knick von s, und sei s(j − 1) ≥ s(j) ≥ s(j + 1). Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik, sei f eine Zeichenbewertung für G. Seien A_{1}, A_{2} ⊆ N nichtleere Teilmengen von N mit f(X) < f(Y) für alle X ∈ A_{1}, Y ∈ A_{2}. Dann gibt es zu G und s einen Verschlucker V_{s} = (A_{1}, A_{2}, N_{Verschl}, P_{Verschl}). Weiterhin gilt: G′ = ⟨N ∪ N_{Verschl}, T, S, P ∪ P_{Verschl}⟩ ist s-schwach wachsend kontextsensitiv, und für jedes Paar von Satzforman (Xv, Y w) aus (N ∪ T)^{∗} mit Xv ⟹^{∗}_{G} Y w gilt:

D^{j−1}V AMXv ⟹^{∗}_{G′} D^{j−1}V AMXw

Beweis: analog zum Beweis von Satz 3.2.5; die Zeichenbewertung f′ wird genauso wie im Satz 3.2.5 definiert mit zusätzlich f′(D) = 1. ♣

Im obigen Satz ist die Voraussetzung einer Mindestlänge für die Satzformen v und w nicht nötig, da sie hier nicht den ”Vorspann“ der Regeln aus R_{1}, R_{2} und R_{3} bereitstellen müssen.

Bezüglich des Sprachgebrauchs von ”V_{s} ist Verschlucker in G“ wird die gleiche Vereinbarung getroffen wie für monoton wachsende Stellenbewertungen (siehe S. 42).

Solch ein Verschlucker läßt sich genauso wie im Falle einer monoton wachsenden Stellenbewertung in eine Grammatik einbauen, die einen linear beschränkten Automaten simuliert.

Satz 3.2.10 : Sei s eine ungleichmäßige monoton fallende Stellenbewertung. Dann gilt:

CSL ⊆ WGCSL_{s}

Beweis: Sei s mit den Voraussetzungen des Satzes gegeben, sei j der erste Knick von s.

Sei L ∈ CSL . Sei M = (Q, Σ, Γ, □, δ, q_{0}, F) ein linear beschränkter Automat, der L erkennt.

Sei M_{2} = (Q_{2}, Σ_{2}, Γ_{2}, □_{2}, δ_{2}, q_{0,2}, F_{2}) wie im Beweis von Satz 3.2.6 der nach Satz 1.2.3 zu M konstruierte Automat, der die Sprache

L_{2} = {w ∈ (Σ^{2})^{∗} ∪ (Σ^{2})^{∗} · Σ^{1}| nat(w) ∈ L}

erkennt.

Konstruiere nun (analog zum Beweis von Satz 3.2.6) eine kontextsensitive Grammatik G_{2} = ⟨N_{2}, Σ_{2} ∪ {•}, S, P_{2}⟩. Dabei seien Γ′_{2} und Γ′′_{2} wieder markierte Kopien des Arbeitsalphabetes Γ_{2}.

Für die Menge N_{2} der Nichtterminale definiere N_{BandAnf}, N_{Band}, N_{BandEnd}, N_{Zustlinks}, N_{Zustrechts} und N_{Gewicht} wie im Beweis von Satz 3.2.6, es wird also wieder festgelegt, daß am rechten Rand der Zustand stets mit R markiert wird. Definiere

N_{Verschl} = \{D, M,[\begin{matrix}M \\ ⋆ \end{matrix}], A, B, V \}

und damit definiere N_{2} durch

N_{2} = {S, S′, X, Y, Ỹ } ∪ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd} ∪ N_{Zustlinks} ∪ N_{Zustrechts}

∪ N_{Gewicht} ∪ N_{Verschl}

Die Regelmenge P_{2} bestehe aus den folgenden Regeln:

Dabei seien x, y, z ∈ Σ_{2}, a, b, c, d ∈ Γ_{2}, dazu a′, c′ ∈ Γ′_{2} und a′′, b′′, c′′ ∈ Γ′′_{2} gerade die markierten Kopien von a, c für den linken und von a, b, c für den rechten Rand. Es seien H ∈ {L, R}, p, q, q̃ ∈ Q_{2} sowie [b^{∗} = b ∧ d^{∗} = d] ∨ [b^{∗} = b′′ ∧ d^{∗} = d′′] und außerdem

α_{c} ∈ (N_{Band})^{∗} ∪ N_{BandAnf} (N_{Band})^{∗}
mit |α_{c}| = j − 1, falls s(1) = s(2), α_{c} = ε sonst

Banderzeugung:

Falls s(1) < s(2) :

S′ →[\begin{matrix}a \\ a′ \\ q_{0,2} \end{matrix}]X

Falls s(1) = s(2) und also s bis zum ersten Knick konstant: Falls q_{0,2}x_{1} … x_{j−1} _{M}^{∗} a_{1} … a_{j−1}q□, dann enthält P_{2} die Regel:

S′ →[\begin{matrix}x_{1} \\ a′_{1} \end{matrix}][\begin{matrix}x_{2} \\ a_{2} \end{matrix}]…[\begin{matrix}x_{j−1} \\ a_{j−1} \end{matrix}][\begin{matrix}b \\ b \\ q \end{matrix}]X

und außerdem enthält P_{2} in beiden Fällen die Regeln:

S → Y S′

X →[\begin{matrix}a \\ a \end{matrix}]X, X →[\begin{matrix}a \\ a′′ \end{matrix}]

Y → Ỹ AM,  Ỹ → D^{j−1}V

Bewegung nach rechts:

Falls (p, c, R) ∈ δ_{2}(q, a), enthält P_{2} die folgenden Regeln:

α_{c}[\begin{matrix}x \\ a \\ q^{R} \end{matrix}][\begin{matrix}y \\ b^{∗} \end{matrix}]→ α_{c}[\begin{matrix}x \\ c \end{matrix}][\begin{matrix}y \\ b^{∗} \\ p^{R} \end{matrix}], α_{c}[\begin{matrix}x \\ a \\ q^{L} \end{matrix}][\begin{matrix}y \\ b^{∗} \end{matrix}]→ α_{c}[\begin{matrix}x \\ c \\ ⋆ \end{matrix}][\begin{matrix}y \\ b^{∗} \\ p^{R} \end{matrix}]

Bewegung am rechten Rand:

wie im Beweis von Satz 3.2.6 Bewegung nach links: Falls (p, d, L) ∈ δ_{2}(q, b), enthält P_{2} die folgende Regel (wobei b^{∗} ∈ Γ′′_{2} ⇒ H = R gefordert wird):

α_{c}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b^{∗} \\ q^{H} \end{matrix} ]→ α_{c}[\begin{matrix}x \\ a \\ p^{L} \end{matrix}][\begin{matrix}y \\ d^{∗} \end{matrix}]

Bewegung am linken Rand: wie im Beweis von Satz 3.2.6 Gewichtswanderung:

α_{c}[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b \\ ⋆ \end{matrix}]→ α_{c}[\begin{matrix}x \\ a \\ ⋆ \end{matrix}][\begin{matrix}y \\ b \end{matrix}]

Gewichte ”verschlucken“: definiere die Regeln wie in Definition 3.2.8 Akzeptieren: Falls (q_{F} , c, R) ∈ δ_{2}(q, a) mit q_{F} ∈ F, so enthält P die Regel:

[\begin{matrix}x \\ a′′ \\ q^{R} \end{matrix}]→ x

Eingabe in Terminale umwandeln:

\begin{matrix}[\begin{matrix}x \\ a \end{matrix}]y → xy,  [\begin{matrix}x \\ a′ \end{matrix}]y → xy \\ Mx → •x,  A• → ••,  V • → ••,  D• → •• \end{matrix}

Definiere eine Zeichenbewertung f′: N_{2} ∪ Σ_{2} → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} genauso wie im Beweis von Satz 3.2.6 mit zusätzlich f′(D) = 1. Wie dort folgt L(G_{2}) ∈ WGCSL_{s}, und analog wie im genannten Beweis folgt mit

l = \{ \begin{matrix}3, & falls s(1) < s(2) \\ j + 2, & sonst \end{matrix}

daß gilt:

L(G_{2}) = {w ∈ (Σ_{2} ∪ {•})^{∗} | w = •^{j+2}w̃ mit w̃ ∈ L_{2} ∧ |w̃| ≥ l}

Nun konstruiere eine Grammatik G = ⟨N, Σ, S, P ⟩ durch:

N := N_{2} ∪ Σ_{2}, P := P_{2} ∪ P_{Schluß}

wobei N_{2}, Σ_{2}, S, P_{2} aus der obigen Grammatik G_{2} stammen und P_{Schluß} aus den folgenden Regeln besteht:

S → w, w ∈ L, |w| < 2 · (j + 2)
•(a, b) → ab, (a, b) → ab, (a) → a für alle a, b ∈ Σ, also alle (a, b), (a) ∈ Σ_{2}
und falls s(1) < s(2) : •a → a• für alle a ∈ Σ
und falls s(1) = s(2) : x_{1} … x_{j−1} • a → x_{1} … x_{j−1}a•
für alle x_{1}, …, x_{j−1} ∈ {•} ∪ Σ, a ∈ Σ

Diese Grammatik vollzieht zunächst die Wirkungsweise von G_{2} nach und erzeugt dann aus deren Ergebnis, einem Wort w ∈ L_{2} mit |w| ≥ l, das Wort nat(w) ∈ L. Dabei werden für |nat(w)| ≥ 2 · (j + 2) die Punkte (•) eliminiert. Wörter w ∈ L mit |w| < 2 · (j + 2) werden direkt erzeugt. (Es ist j ≥ 2, also 2 · (j + 2) ≥ 8 > 3.)

Also gilt L(G) = L.

Mit der Funktion f: N ∪ Σ → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} definiert wie im angegebenen Beweis (also wie f′ und zusätzlich f(a) = f′(•) + 1 für alle a ∈ Σ) sieht man L = L(G) ∈ WGCSL_{s}. ♣

Die am Anfang dieses Kapitels vorgestellten vier Fälle sind nun also abgearbeitet, wobei wir wie angekündigt im dritten Fall Stellenbewertungen s mit s(1) = 0 ausgenommen haben, die in Kapitel 5.1 behandelt werden. Wegen der zentralen Bedeutung des folgenden Satzes schließen wir schon die Aussage von Satz 5.1.3 mit ein, den wir mit den Methoden aus dem nächsten Kapitel sehr einfach beweisen können.

Satz 3.2.11 : Für jede ungleichmäßige Stellenbewertung s gilt:

WGCSL_{s} = CSL

Beweis: Sei s eine ungleichmäßige Stellenbewertung.

WGCSL_{s} ⊆ CSL folgt aus der Definition s-schwach wachsend kontextsensitiver Grammatiken.

Sei j ein Knick von s.

Laut Definition 2.3.3 ist dann weder s(j − 1) = 0 = s(j) noch s(j) = 0 = s(j + 1). Daraus folgt aber, falls s nicht monoton ist, daß entweder s(j − 1) > s(j) ∧ s(j) < s(j + 1) oder s(j − 1) < s(j) ∧ s(j) > s(j + 1).

Damit folgt die Behauptung, falls s(1) ≠ 0, aus den Sätzen 3.2.1, 3.2.2, 3.2.6 und 3.2.10.

Falls s(1) = 0, folgt die Behauptung aus WGCSG_{0_{k},c} ⊆ WGCSG_{s} für ein c ∈ IN^{+} und ein k ∈ IN^{+} (wegen Satz 2.1.3) und WGCSL_{0,1} = WGCSL_{0_{k},c} (wegen Satz 2.3.7) und Satz 5.1.3.

♣ 54 CHARAKTERISIERUNG DER KONTEXTSENSITIVEN SPRACHEN

Gleichmäßige Stellenbewertung

4.1 Effiziente Simulation einer Grammatik

4.1.1 Verbundene Grammatiken

Zwei aufeinanderfolgende Ableitungsschritte heißen verbunden, falls der zweiten Ableitungsschritt wenigstens ein Symbol, das der erste produziert hat, manipuliert. In einer Grammatik heißt eine Ableitung verbunden (siehe Definition 4.1.3), wenn in ihr je zwei aufeinanderfolgende Ableitungsschritte verbunden sind. Eine Grammatik soll verbunden heißen, wenn in ihr nur verbundene Ableitungen möglich sind (vgl. [Gla64], [Boo69], [Bun93]).

Bei der Simulation einer verbundenen Ableitung durch eine Turingmaschine kann die Turingmaschine direkt Schritt für Schritt die Ableitung simulieren, während sie bei nicht verbundenen Ableitungsschritten erst mit dem Kopf zur Ersetzungsstelle laufen müßte. Das heißt, bei der Abschätzung der Rechenzeit entfällt der in der Bemerkung auf S. 32 genannte Faktor n.

Für eine formale Definition der Eigenschaft der Verbundenheit sind Ableitungsgraphen zur Darstellung von Ableitungen ein nützliches Hilfsmittel (siehe [Lo70], vgl. dazu [DW86] oder auch [BL92], [Ni92]).

Definition 4.1.1 : Mit jeder Ableitung in G = ⟨N, Σ, S, P ⟩ wird ein planarer azyklischer Graph assoziiert, genannt der Ableitungsgraph. Die Knoten in einem solchen Graphen sind markiert mit den zugehörigen Symbolen und Regeln, die in der Ableitung verwendet werden. Die Markierung (engl.: label) eines Knotens v wird mit l(v) bezeichnet. 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} ⟹_{G} α_{i} mit α_{i−1} = wαw′, α_{i} = wβw′ und (α → β) ∈ P,

also α_{i−1} = wαw′ ⟹_{G} 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.

Nun muß noch erklärt werden, was ein Vorgänger bzw. Nachfolger eines Knotens in einem Graphen ist.

Definition 4.1.2 : Sei D = (V, E) ein gerichteter Graph (z.B. ein Ableitungsgraph). Sei u ∈ V ein Knoten des Graphen D. Dann ist die Menge aller Vorgänger von u erklärt durch:

V G(u) = {v ∈ V | (v, u) ∈ E}

und die Menge der Nachfolger von u ist erklärt durch:

NF (u) = {v ∈ V | (u, v) ∈ E}

Bemerkung: In einem Ableitungsgraphen D = (V, E) zu einer Ableitung in einer Grammatik G = ⟨N, T, S, P ⟩ gilt für jeden Knoten u ∈ V:

l(u) ∈ T ⇒ NF (u) = ∅
l(u) ∈ P ⇒ {l(v) | v ∈ V G(u)} ∪ {l(v) | v ∈ NF (u)} ⊆ N ∪ T
und ∃A ∈ N : A ∈ {l(v) | v ∈ V G(u)}
l(u) ∈ N ⇒ |NF (u)| = |V G(u)| = 1, und für v ∈ NF (u) ∪ V G(u) gilt: l(v) ∈ P

Falls S in keiner Regel aus P auf der rechten Seite auftaucht, gilt auch

l(u) = S ⇔ V G(u) = ∅

sonst gilt nur

V G(u) = ∅ ⇒ l(u) = S

und es existiert genau ein Knoten in V, der keinen Vorgängerknoten besitzt. Dieser soll Startknoten des Ableitungsgraphen D genannt werden.

Definition 4.1.3 : Sei G = ⟨N, T, S, P ⟩ eine Grammatik. Sei w_{0} = S ⟹ w_{1} ⟹ … ⟹ w_{t} eine Ableitung in G, sei r_{i} die im Schritt w_{i−1} ⟹ w_{i} angewandte Regel aus P für i = 1, …, t. Sei D = (V, E) der zur Ableitung w_{0} = S ⟹ w_{1} ⟹ … ⟹ w_{t} gehörende Ableitungsgraph. Seien v^{1}, v^{2}, …, v^{t} ∈ V mit l(v^{i}) = r_{i} die mit den Regeln markierten Knoten. Die Ableitung w_{0} ⟹ … ⟹ w_{t} heißt verbunden (engl.: connected), falls für jedes i = 1, …, t − 1 gilt:

NF (v^{i}) ∩ V G(v^{i+1}) ≠ ∅

Die Grammatik G heißt verbunden, falls es in ihr nur verbundene Ableitungen gibt.

Bemerkung: In einem Ableitungsgraphen D zu einer verbundenen Ableitung gibt es einen Pfad von dem Startknoten von D durch alle mit Produktionen markierten Knoten von D.

Gladkij hat bewiesen, daß alle Grammatiken (sowohl solche ohne Einschränkungen als auch kontextsensitve) in verbundene gleichwertige Grammatiken vom gleichen Typ umgewandelt werden können ([Gla64]). Unter Verwendung des Beweises von Book in [Boo69] wurde in [Bun93] gezeigt, daß dies auch für quasi wachsend kontextsensitive Grammatiken gilt. Hier soll nun gezeigt werden, daß dies auch für schwach wachsend kontextsensitive Grammatiken bezüglich einer nichtkonstanten Stellenbewertung richtig ist.

Dazu wird zunächst eine geeignete Normalform eingeführt.

Definition 4.1.4 : Eine kontextsensitive Grammatik G = ⟨N, T, S, P ⟩ heißt in verbundener Cremers-Normalform, wenn sämtliche Regeln aus P von einer der folgenden Formen sind:

AB → CD,  A → CD,  AB → aD,  A → a

wobei A, B, C, D ∈ N, a ∈ T.

Dabei wurden die Regeln der dritten Form so definiert, damit die Wörter von links nach rechts erzeugt werden.

Satz 4.1.5 : Sei s eine Stellenbewertung mit zwei bewerteten Stellen und 0 ≠ s(1) < s(2). Zu jeder Grammatik G ∈ WGCSG_{s} existiert dann eine verbundene Grammatik G′ ∈ W GCSL_{s} in verbundener Cremers-Normalform mit L(G′) = L(G). Außerdem ist die Ableitungslänge für ein Wort w in G′ gegenüber der in G höchstens verdoppelt.

Beweis: Sei also s eine Stellenbewertung mit zwei bewerteten Stellen und 0 ≠ s(1) < s(2). Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s}, o.B.d.A. in Cremers-Normalform (wegen Satz 2.3.6). Sei f eine Zeichenbewertung für G.

Definiere nun eine Grammatik G′ = ⟨N′, T, Ŝ, P′⟩ durch:

N′ = N ∪ {Â | A ∈ N}

also die alte Nichtterminalmenge und zusätzlich zu jedem Nichtterminal eine Kopie mit einem Dach ( ˆ ) und die folgenden Regeln:

\begin{aligned}P_{1} & = \{ \begin{matrix}ÂB → ĈD, ÂB → CD̂, \\ AB̂ → ĈD, AB̂ → CD̂ \end{matrix} | A, B, C, D ∈ N, (AB → CD) ∈ P \} \\ P_{2} & = \{Â → ĈD, Â → CD̂ | A, C, D ∈ N, (A → CD) ∈ P \} \\ P_{3} & = \{Â → a, ÂX → aX̂ | A, X ∈ N, a ∈ T, (A → a) ∈ P \} \\ P_{4} & = \{ÂB → AB̂ | A, B ∈ N\} \\ P & = P_{1} ∪ P_{2} ∪ P_{3} ∪ P_{4} \end{aligned}

Nach [Boo69] ist L(G′) = L(G), und G′ ist eine verbundene Grammatik in verbundener Cremers-Normalform. Definiere nun eine Zeichenbewertung f′: N′ ∪ T → IN für G′ durch:

f′(A) = s(2)^{2} · f(A)  für alle A ∈ N
f′(Â) = s(2)^{2} · f(A) + s(2) für alle A ∈ N
f′(a) = s(2)^{2} · f(a)  für alle a ∈ T

Jede Regel aus P wächst mit f um mindestens 1. Der Faktor s(2)^{2} in der Definition von f′ bewirkt, daß diese ”Wachstumsrate“ auf wenigstens s(2)^{2} ansteigt. Der Summand s(2), der bei den mit einem Dach markierten Nichtterminalen hinzukommt, läßt sich also noch gut unterbringen. Dazu betrachte die 3. Regel aus P_{2}: Es ist

\begin{matrix}s(1) · f(A) + s(2) · f(B) + 1 ≤ s(1) · f(C) + s(2) · f(D) \\ ⇒ s(1) · s(2)^{2} · f(A) + s(2)^{3} · f(B) + s(2)^{2} ≤ s(1) · s(2)^{2} · f(C) + s(2)^{3} · f(D) \end{matrix}

Es gilt also für die linke Seite dieser Regel:

s(1) · f′(A) + s(2) · f′(B̂) = s(1) · s(2)^{2} · f(A) + s(2) · s(2)^{2} · f(B) + s(2) · s(2)
≤ s(1) · s(2)^{2} · f(C) + s(2) · s(2)^{2} · f(D)
< s(1) · s(2)^{2} · f(C) + s(1) · s(2) + s(2) · s(2)^{2} · f(D)
= s(1) · f′(Ĉ) + s(2) · f′(D)

Bei allen anderen Regeln aus P′ folgt ebenso, daß sie s-schwach wachsend mit f′ sind, und damit folgt: G′ ∈ WGCSG_{s}. Die zweite Behauptung gilt nach [Boo69]. ♣

Man kann diese Beweisidee auch auf WGCSG_{s} mit zwei bewerteten Stellen und s(1) > s(2) übertragen, indem man in P_{4} das Dach statt nach rechts nach links wandern läßt (muß dann allerdings in der verbundenen Cremers-Normalform die 3. Form von Regeln so erklären, daß Wörter von rechts nach links erzeugt werden). (Im Falle s(2) = 0 liefert hier Satz 2.3.7 die Cremers-Normalform.)

Im Falle einer Stellenbewertung mit zwei bewerteten Stellen und s(1) = 0 läßt sich nach Anwendung von Satz 2.1.2 der Algorithmus aus dem Beweis von Satz 2.1.1 anwenden, um zu einer Grammatik aus WGCSG_{s} eine äquivalente in Cremers-Normalform zu erhalten. Um nun den Beweis von Satz 4.1.5 zu übertragen, muß man die 3. Form von Regeln in der verbundenen Cremers-Normalform so abändern, daß auch zwei Terminale gleichzeitig erzeut werden dürfen.

Außerdem läßt sich die Richtung des Wanderns des Daches in P_{4} auch durch Einführen einer zweiten Klasse von Nichtterminalen, die dann rechts vom Dach in der Satzform stehen und anders bewertet werden als ihre ”normalen“ Pendants, ändern, siehe [Bun93].

Weiterhin kann man diese Beweisidee auch auf Grammatiken höherer Ordnung übertragen und erhält damit auch verbundene Grammatiken für WGCSL_{s} mit Stellenbewertungen, bei denen eine Cremers-Normalform nicht bekannt ist.

4.1.2 Effiziente Simulation

In Satz 2.3.6 wurde gezeigt, daß für jede gleichmäßige Stellenbewertung s gilt:

WGCSL_{s} = WGCSL_{s(1),s(2)}

Es kann also ohne Beschränkung der Allgemeinheit angenommen werden, daß s eine Stellenbewertung mit nur zwei bewerteten Stellen ist. Es kann sogar angenommen werden, daß s monoton wachsend ist:

Satz 4.1.6 : Sei s eine gleichmäßige Stellenbewertung. Dann gilt

WGCSL_{s(1),s(2)} = WGCSL_{s(2),s(1)}

und damit gilt auch

WGCSL_{w(s)} = WGCSL_{\frac{1}{w(s)}}

Beweis: Sei also s eine gleichmäßige Stellenbewertung. Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik, o.B.d.A. sei G in Cremers-Normalform (Satz 2.3.6). G enthält also nur Regeln der Formen

AB → CD,  A → CD,  A → a

mit A, B, C, D ∈ N, a ∈ T. Sei f eine Zeichenbewertung für G.

Konstruiere nun eine Grammatik G′ = ⟨N′, T, S, P′⟩, die die Sprache L(G)^{T} erkennt und in WGCSG_{s(2),s(1)} liegt, definiere dazu s′ := s_{s(2),s(1)}.

Dabei ist die Idee folgende:

Bei den längenerhaltenden Regeln ist das Transponieren einer Regel kein Problem. Bei den expandierenden Regeln wird an eines der erzeugten Nichtterminale ein kodiertes Gewicht angehängt, durch das die transponierte Regel s′-schwach wachsend wird. Dieses Gewicht bleibt bei weiteren Regelanwendungen einfach hängen, es werden also entsprechende Kopien der anderen Regeln nötig. Ebenso bleibt dieses Gewicht bei weiteren expandierenden Regeln einfach hängen, das neue wird an das andere Nichtterminal gehängt. Da neue Zusatzgewichte nur bei expandierenden Regeln entstehen und sie sonst nur ”am selben Fleck“ liegen bleiben, stören sie nicht weiter und können bei der Umwandlung der Nichtterminale in Terminale eliminiert werden. Es stellt sich heraus, daß von den vier möglichen aus einer Regel der Form AB → CD sich ergebenden Regeln zwei niemals in einer Ableitung anwendbar sein können und also nur die beiden anderen in die Regelmenge P′ aufgenommen zu werden brauchen.

Die Grammatik G′ = ⟨N′, T, S, P′⟩ sieht also wie folgt aus:

N′ = N ∪ \{[\begin{matrix}X \\ • \end{matrix}]| X ∈ N\}

und P′ definiert durch:

P_{1} = \{B[\begin{matrix}A \\ • \end{matrix}]→ D[\begin{matrix}C \\ • \end{matrix}], [\begin{matrix}B \\ • \end{matrix}][\begin{matrix}A \\ • \end{matrix}]→[\begin{matrix}D \\ • \end{matrix}][\begin{matrix}C \\ • \end{matrix}]| A, B, C, D ∈ N, (AB → CD) ∈ P \}

P_{2} = \{A → D[\begin{matrix}C \\ • \end{matrix}], [\begin{matrix}A \\ • \end{matrix}]→[\begin{matrix}D \\ • \end{matrix}][\begin{matrix}C \\ • \end{matrix}]| A, C, D ∈ N, (A → CD) ∈ P \}

P_{3} = \{A → a, [\begin{matrix}A \\ • \end{matrix}]→ a | A ∈ N, a ∈ T, (A → a) ∈ P \}

P′ = P_{1} ∪ P_{2} ∪ P_{3}

Es gilt L(G′) = L(G)^{T}. Außerden ist G′ kontextsensitiv und von der Ordnung 2.

Definiere eine Zeichenbewertung f′: N′ ∪ T → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} durch (dazu sei m := max{f(X) | X ∈ N}):

f′(X) = f(X) für alle X ∈ N
f′([\begin{matrix}X \\ • \end{matrix}]) = f(X) + \frac{s(2)−s(1)}{s(1)} · m für alle X ∈ N
f(a) = m + \frac{s(2)−s(1)}{s(1)} · m + 1 für alle a ∈ T

Bedenke, daß s als gleichmäßige Stellenbewertung per Definition nullstellenfrei ist. Die Regeln aus P_{1} und P_{3} sind trivialerweise s′-schwach wachsend mit f′. Betrachte nun die erste Regel aus P_{2}:

Es gilt:

s(1) · f(A) < s(1) · f(C) + s(2) · f(D) (∗)

Für die Bewertung der genannten Regel gilt:

s′(1) · f′(A) < s′(1) · f′(D) + s′(2) · f′([\begin{matrix}C \\ • \end{matrix}])

⇔ s(2) · f(A) < s(2) · f(D) + s(1) · (f(C) + \frac{s(2)−s(1)}{s(1)} · m)

⇔ s(1) · f(A) + (s(2) − s(1)) · f(A) < s(1) · f(C) + s(2) · f(D) + (s(2) − s(1)) · m

und wegen m ≥ f(A) ist dies wegen (∗) richtig.

Also ist die erste Regel aus P_{2} s′-schwach wachsend mit f′, für die zweite Regel aus P_{2} folgt dies analog.

Also ist (wegen Satz 2.1.5) G′ ∈ WGCSG_{s′} = WGCSG_{s(2),s(1)}. Daraus folgt: L(G)^{T} ∈ WGCSL_{s(2),s(1)}, und wegen Satz 2.2.2 folgt daraus

L(G) ∈ WGCSL_{s(2),s(1)}

Der Beweis ist symmetrisch in s und s′, also gilt:

WGCSL_{s(1),s(2)} = WGCSL_{s(2),s(1)}

Wegen Satz 2.1.4 und w(s_{s(2),s(1)}) = \frac{1}{w(s_{s(1),s(2)})} folgt damit auch

WGCSL_{w(s)} = WGCSL_{\frac{1}{w(s)}}
♣

Soll nun eine schwach wachsend kontextsensitive Sprache bezüglich einer gleichmäßigen Stellenbewertung durch einen linear beschränkten Automaten simuliert werden, so liegt es nahe, den Algorithmus aus Kapitel 3.1 zu verwenden und Satz 4.1.5 auszunutzen. Um für den simulierenden linear beschränkten Automaten eine Zeitschranke angeben zu können, braucht man also nur noch die Ableitungslänge in einer schwach wachsend kontextsensitiven Grammatik bezüglich einer gleichmäßigen Stellenbewertung abzuschätzen.

Ausschlaggebend hilfreich dabei ist, daß bei jeder Regelanwendung in einer solchen Grammatik auch die Bewertung der entsprechenden Satzformen anwächst, wobei die Stellenbewertung in sinnvoller Weise auf IN^{+} fortgesetzt wird, wie am Ende von Kapitel 2.3 angedeutet wurde. Bei ungleichmäßigen Stellenbewertungen ist das ja nicht der Fall, wie durch den Einsatz von Verschluckern in Kapitel 3.2 einsichtig geworden ist. Umgekehrt kann es eben deswegen für eine gleichmäßige Stellenbewertung keinen Verschlucker geben.

Satz 4.1.7 : Sei s eine gleichmäßige monoton wachsende Stellenbewertung. Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik, seien

u = u_{1} … u_{r}, v = v_{1} … v_{s} ∈ (N ∪ T)^{∗} Satzformen mit u ⟹_{G} v, sei f: N ∪ T → IN eine

Zeichenbewertung für G. Dann gilt:

∑_{i=1}^{r} (w(s))^{i−1} · f(u_{i}) + 1 ≤ ∑_{i=1}^{s} (w(s))^{i−1} · f(v_{i})

Beweis: Seien die Voraussetzungen des Satzes erfüllt und die Definitionen darin gültig. Sei (α_{1} … α_{n} → β_{1} … β_{m}) ∈ P die Regel, durch deren Anwendung u in v übergeht. Dann gilt: ∃j ∈ IN^{+} mit u = u_{1} … u_{j}α_{1} … α_{n}u_{j+n+1} … u_{r} und v = v_{1} … v_{j}β_{1} … β_{m}v_{j+m+1} … v_{s} sowie s = r + m − n, also gilt auch: u_{1} … u_{j} = v_{1} … v_{j} und u_{j+n+1} … u_{r} = v_{j+m+1} … v_{s}. Es gilt für alle bewerteten Stellen i ∈ IN von s:

s(i) = s(1) · (w(s))^{i−1}

(vgl. Bemerkung nach Definition 2.3.3). Es gilt:

∑_{i=1}^{n} s(i) · f(α_{i}) + 1 ≤ ∑_{i=1}^{m} s(i) · f(β_{i})

⇔ ∑_{i=1}^{n} s(1) · (w(s))^{i−1} · f(α_{i}) + 1 ≤ ∑_{i=1}^{m} s(1) · (w(s))^{i−1} · f(β_{i})

⇔ (w(s))^{j} · ∑_{i=1}^{n} (w(s))^{i−1} · f(α_{i}) + (w(s))^{j} ≤ (w(s))^{j} · ∑_{i=1}^{m} (w(s))^{i−1} · f(β_{i})

⇔ ∑_{i=j+1}^{j+n} (w(s))^{i−1} · f(α_{i}) + (w(s))^{j} ≤ ∑_{i=j+1}^{j+m} (w(s))^{i−1} · f(β_{i})

Daraus folgt mit:

\begin{matrix}∑_{i=j+n+1}^{r} (w(s))^{i−1} · f(u_{i}) \\ ≤ (w(s))^{m−n} · ∑_{i=j+n+1}^{r} (w(s))^{i−1} · f(u_{i}) = ∑_{i=j+m+1}^{s} (w(s))^{i−1} · f(v_{i}) \end{matrix}

(da s monoton wachsend, ist w(s) ≥ 1) und

∑_{i=1}^{j} (w(s))^{i−1} · f(u_{i}) = ∑_{i=1}^{j} (w(s))^{i−1} · f(v_{i})

wegen [w(s) ≥ 1 ⇒ ∀j ∈ IN^{+} : (w(s))^{j} ≥ 1] die Behauptung. ♣ Also kann man die Ableitunglänge für ein Wort w in einer Grammatik G durch die Bewertung diese Wortes abschätzen. Dazu ist es nützlich zu wissen, wie groß die Funktionswerte einer Zeichenbewertung höchstens werden müssen. Dazu wird der Begriff der minimalen Zeichenbewertung eingeführt.

Definition 4.1.8 : Sei s eine Stellenbewertung. Eine Zeichenbewertung f für eine s-schwach wachsend kontextsensitive Grammatik G = ⟨N, T, S, P ⟩ heißt minimal, wenn gilt:

Es existiert keine Zeichenbewertung f′ für G mit

[∀A ∈ N ∪ T : f′(A) ≤ f(A)] ∧ [∃A ∈ N ∪ T : f′(A) < f(A)]

Diese Definition besagt lediglich, daß für f keine ”offensichtlich zu großen“ Werte gewählt wurden, nimmt aber keine Rücksicht darauf, daß sehr große Funktionswerte eventuell verringert werden können, indem andere, kleinere, erhöht werden.

Da zu einer s-schwach wachsend kontextsensitiven Grammatik per Definition immer eine Zeichenbewertung existiert und die Bedingung in der Definition 4.1.8 entscheidbar ist, existiert auch zu jeder Grammatik eine minimale Zeichenbewertung. Eindeutig ist diese nicht. Die größten Funktionswerte sind in der Regel bei den Terminalen zu erwarten.

Eine Abschätzung der Funktionswerte einer minimalen Zeichenbewertung wird für Stellenbewertungen der Form s(i) = 2^{k·(i−1)} für alle i ∈ IN in [Sw93] angegeben; der Beweis ist unabhängig von dieser speziellen Wahl des Wachstumsfaktors und daher auf andere gleichmäßige streng monoton wachsende Stellenbewertungen übertragbar. Also gilt:

Satz 4.1.9 : [Sw93] Sei s eine gleichmäßige streng monoton wachsende Stellenbewertung. Für eine minimale Zeichenbewertung einer s-schwach wachsend kontextsensitiven Grammatik G = ⟨N, T, S, P ⟩ der Ordnung l gilt:

(i) min{f(X) | X ∈ N ∪ T } = 1

(ii) max{f(X) | X ∈ N ∪ T } ≤ (w(s))^{l·|N∪T |}

Beweis: siehe Satz 8 in [Sw93] mit w(s) statt 2^{k}. ♣

Nunmehr können wir also die Ableitungslänge abschätzen:

Satz 4.1.10 : Sei s eine gleichmäßige streng monoton wachsende Stellenbewertung. Sei G = ⟨N, T, S, P ⟩ eine s-schwach wachsend kontextsensitive Grammatik von der Ordnung l, sei w ∈ L(G). Dann ist die Länge einer Ableitung S ⟹^{∗}_{G} w nicht länger als

(w(s))^{|w|} · \frac{(w(s))^{l·|N∪T |}}{w(s) − 1}

Beweis: Sei also s eine gleichmäßige streng monoton wachsende Stellenbewertung. Sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} von der Ordnung l, und sei w ∈ L(G). Sei f eine minimale Zeichenbewertung für G. Sei eine Ableitung von w = w_{1} … w_{|w|} in G gegeben, sei A die Anzahl ihrer Schritte.

Aus Satz 4.1.7 folgt:

A ≤ ∑_{i=1}^{|w|} (w(s))^{i−1} · f(w_{i}) ≤ max{f(a) | a ∈ T } · ∑_{i=1}^{|w|} (w(s))^{i−1}

Mit Satz 4.1.9 folgt daraus (da w(s) > 1):

A ≤ (w(s))^{l·|N∪T |} · \frac{(w(s))^{|w|} − 1}{w(s) − 1}

♣

Jetzt wollen wir also die Rechenzeit eines linear beschränkten Automaten, der eine schwach wachsend kontextsensitive Grammatik bezüglich einer gleichmäßigen Stellenbewertung simuliert, abschätzen.

Satz 4.1.11 : Sei s eine gleichmäßige nichtkonstante Stellenbewertung. Sei w = max\{w(s), \frac{1}{w(s)}\}. Dann gilt:

WGCSL_{s} ⊆ T –NSPACE-TIME (n, O(w^{n}))

Beweis: Sei also s eine gleichmäßige nichtkonstante Stellenbewertung. Wegen Satz 2.3.6 und Satz 4.1.6 kann o.B.d.A. angenommen werden, daß s genau zwei Stellen bewertet und s(1) < s(2) gilt und also auch w = w(s) ist. Sei L ∈ WGCSL_{s}, sei G = ⟨N, T, S, P ⟩ ∈ WGCSG_{s} eine Grammatik in Cremers-Normalform, die L erzeugt.

Nach Satz 4.1.10 ist die Ableitungslänge für ein Wort w ∈ L in G nicht länger als

\frac{w^{2·|N∪T |}}{w − 1} · w^{|w|}

Nach Satz 4.1.5 ist es möglich, aus G eine äquivalente verbundene Grammatik G′ zu gewinnen, in der die Ableitungslänge für jedes erzeugbare Wort gegenüber der in G höchstens verdoppelt ist.

Ein linear beschränkter Automat, der G′ gemäß dem Algorithmus in Satz 3.1.2 simuliert, benötigt also zum Erkennen von w ∈ L höchstens c · 2 · \frac{w^{2·|N∪T |}}{w−1} · w^{|w|} + c · |w|^{2} Schritte (mit geeignetem c ∈ IN , vgl. Bemerkung auf S. 32) und arbeitet also in der Zeit O(w^{n}). ♣

4.2 Zähler

Wie schon erwähnt ist es bei einer gleichmäßigen Stellenbewertung nicht möglich, einen Verschlucker wie in Kapitel 3.2 zu konstruieren (folgt aus Satz 4.1.7). Will man nun also einen (zeitbeschränkten) linear beschränkten Automaten durch eine schwach wachsend kontextsensitive Grammatik bezüglich einer gleichmäßigen Stellenbewertung ähnlich wie in Kapitel 3.2 im Falle einer monotonen ungleichmäßigen Stellenbewertung simulieren, stellt sich das Problem, wo die bei jedem zweiten Richtungswechsel freiwerdenden Gewichte hingepackt werden sollen. Zunächst stellt sich also die Frage, wie man auf einer möglichst kurzen Satzform möglichst viele Gewichte, die nach und nach von einer Seite aus hineingegeben werden, verteilen kann. Wegen Satz 2.3.6 und Satz 4.1.6 genügt es, diese Frage für (streng) monoton wachsende Stellenbewertungen zu beantworten. So eine Satzform läßt sich auch interpretieren als eine Zahl, die stets um 1 erhöht wird, deshalb wird sie zusammen mit den für die Gewichtsverteilung zuständigen Regeln als Zähler bezeichnet.

Definition 4.2.1 : Sei s eine gleichmäßige streng monoton wachsende Stellenbewertung. Ein Zähler bezüglich der Stellenbewertung s oder kurz ein s-Zähler ist ein Quadrupel Z = (A, N, z, R) bestehend aus:

• einer endlichen Menge A von wenigstens zwei Zeichen

• einer endlichen nichtleeren Zeichenmenge N

• einer Anfangssatzform z ∈ N^{∗}

• einer Menge R von Regeln, d.h. eine endliche Teilmenge von A · N^{∗} × A · N^{∗} ∪ N^{∗} × N^{∗}, für die außerdem folgendes gilt:

(α → β) ∈ R ⇒ \begin{matrix}|α| = |β| \\ ∧ [(α = Xw, β = Y v mit X, Y ∈ A, w, v ∈ N^{∗}) ⇒ X ≠ Y] \end{matrix}

für das folgendes richtig ist:

Es existiert eine Funktion f: A ∪ N → IN mit:

• alle Regeln aus R sind s-schwach wachsend mit f

• es existieren X, Y ∈ A mit f(X) ≠ f(Y)

• für alle (α → β) ∈ R mit α = Xw, β = Y v mit X, Y ∈ A, w, v ∈ N^{∗} gilt: f(X) > f(Y)

f heißt Zeichenbewertung für Z.

Wie bei s-schwach wachsend kontextsensitiven Grammatiken genügt es auch hier, eine Zeichenbewertung mit Werten aus Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} zu finden (siehe Satz 2.1.5).

Definition 4.2.2 : Sei s eine gleichmäßige streng monoton wachsende Stellenbewertung. Sei Z = (A, N, z, R) ein s-Zähler, sei f eine Zeichenbewertung für Z. Die Breite von Z ist definiert durch die Länge der Anfangssatzform |z|. Die Menge ρ(Z, f) von Inkrementregeln für Z mit f ist definiert durch:

ρ(Z, f) = {(X → Y) | X, Y ∈ A, f(X) < f(Y)}

Und die Kapazität K(Z) von Z ist erklärt durch:

K_{Z} = max_{f Zeichbew für Z} \{i ∈ IN | \begin{matrix}∃M ∈ A ∃z̃ ∈ N^{∗} ∃k ∈ IN : (r_{1}, …, r_{k}) ∈ (R ∪ ρ(Z, f))^{k} \\ ist eine Folge von Regeln mit Mz ⟹_{r_{1}} … ⟹_{r_{k}} Mz̃ \\ und mit |\{j ∈ \{1, …, k\} | r_{j} ∈ ρ(Z, f)\}| = i \end{matrix} \}

das heißt, als Kapazität eines Zählers wird festgelegt, wie oft eine Inkrementregel angewendet und das dabei erzeugte Gewicht verarbeitet werden kann, wobei, nebenbei bemerkt, das ”Sammeln“ von Gewichten vor dem Verarbeiten erlaubt ist (d.h. das Anwenden mehrerer Inkrementregeln direkt hintereinander).

Da die Menge A endlich und jede der anzuwendenden Regeln längenerhaltend ist, existiert das Maximum in der Definition der Kapazität eines Zählers in jedem Fall. Zu jedem Zähler Z und jedem c ∈ IN^{+} gibt es (durch die Möglichkeit des ”Sammelns“ von Gewichten) einen Zähler Z′ mit K_{Z′} = c · K_{Z}.

Da wir solche Zähler bei der Simulation linear beschränkter Automaten einsetzen und also auch für beliebige Wortlängen bereitstellen wollen, ist es sinnvoll, Zähler gleicher Bauart mit verschiedenen Breiten zusammenzufassen.

Definition 4.2.3 : Sei s eine streng monoton wachsende gleichmäßige Stellenbewertung. Eine Sequenz von s-Zählern oder s-Zählersequenz ist eine Folge Z = (Z_{i})_{i∈IN^{+}} von Zählern Z_{i} = (A, N, z_{i}, R), für die gilt:

für jedes |z_{i}| = i und i ∈ IN^{+} ist z_{i+1} = z_{i}v mit v ∈ N

Das heißt, die einzelnen Zähler unterscheiden sich nur in ihrer Breite, und für jedes n ∈ IN^{+} ist ein Zähler der Breite n in der Sequenz vertreten. Daher schreiben wir Z = (A, N, (z_{i})_{i∈IN^{+}}, R) für die s-Zählersequenz Z = (Z_{i})_{i∈IN^{+}}. Sei j ∈ IN^{+}. Sei f eine Zeichenbewertung für Z_{j}. Dann ist f Zeichenbewertung für jedes Z_{i}, i ∈ IN^{+}. Wir sagen, f ist Zeichenbewertung für die s-Zählersequenz Z. Für die Menge ρ(Z_{j}, f) der Inkrementregeln für Z_{j} mit f gilt: ρ(Z_{j}, f) = ρ(Z_{i}, f) für alle i ∈ IN^{+}. Wir definieren also die Menge der Inkrementregeln der s-Zählersequenz Z mit f durch: ρ(Z, f) = ρ(Z_{j}, f). Die Kapazität K_{Z} der s-Zählersequenz ist eine Funktion erklärt durch:

K_{Z}: IN^{+} → IN^{+}, K_{Z}(i) = K_{Z_{i}}

sie ordnet also jedem Index i die Kapazität des s-Zählers Z_{i} aus der Sequenz Z zu. Für eine s-Zählersequenz Z = (A, N, (z_{i})_{i∈IN^{+}}, R) ist das i-te Glied der s-Zählersequenz Z erklärt durch Z_{i} = (A, N, z_{i}, R).

Beispiel 4.2.4 : Sei s eine streng monoton wachsende geichmäßige Stellenbewertung. Sei Z = (A, N, (z_{n})_{n∈IN^{+}}, R) gegeben durch:

A = \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N = \{[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}], …,[\begin{matrix}X \\ k \end{matrix}]\} für ein k ∈ IN^{+}

z_{n} =[\begin{matrix}X \\ 0 \end{matrix}]^{n} für jedes n ∈ IN^{+}

und R bestehend aus den Regeln:

\begin{matrix}[\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→ M[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}] \\ [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]→ M[\begin{matrix}X \\ 2 \end{matrix}], & [\begin{matrix}X \\ 2 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]→[\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}] \\ ⋮ & ⋮ \\ [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ k − 1 \end{matrix}]→ M[\begin{matrix}X \\ k \end{matrix}], & [\begin{matrix}X \\ k \end{matrix}][\begin{matrix}X \\ k − 1 \end{matrix}]→[\begin{matrix}X \\ k − 1 \end{matrix}][\begin{matrix}X \\ k \end{matrix}] \end{matrix}

Definiere eine Zeichenbewertung f: A ∪ N → IN durch:

\begin{matrix}f(M) = 1, & f([\begin{matrix}M \\ # \end{matrix}]) = 2 \\ f([\begin{matrix}M \\ 0 \end{matrix}]) = 1, & f([\begin{matrix}M \\ i \end{matrix}]) = i + 1 für i = 1, …, k \end{matrix}

Damit sieht man, daß Z ein s-Zählersequenz ist.

Wie groß ist nun die Kapazität dieser Zählersequenz ?

Es ist ρ(Z, f) = \{(M →[\begin{matrix}M \\ # \end{matrix}])\} für alle Zeichenbewertungen f für Z. Sei n ∈ IN^{+} gegeben,

sei Z_{n} das n-te Glied der s-Zählersequenz Z. Die Inkrementregel kann in Z_{n} n mal angewendet

werden, bis die Satzform im Zähler Z_{n} voller [\begin{matrix}X \\ 1 \end{matrix}]steht, wiederum n mal, bis sie voller [\begin{matrix}X \\ 2 \end{matrix}]

steht und so fort, also insgesamt k · n mal. Die Kapazität von Z_{n} ist also K(Z_{n}) = k · n. Die der Zählersequenz Z also K_{Z}(n) = k · n. (Man kann natürlich auch ungeschickter ableiten.)

Dieser Zähler ist recht trivial: Es wird einfach gestapelt, wobei eine Ebene nach der anderen aufgeschichtet wird. Der Zähler im folgenden Beispiel arbeitet etwas geschickter.

Beispiel 4.2.5 : Sei k ∈ IN^{+}, sei s eine streng monoton wachsende Stellenbewertung. Es gibt eine s-Zählersequenz, deren Kapazität in O(n^{k}) \ O(n^{k−1}) liegt. Definiere Z = (A, N, (z_{n})_{n∈IN^{+}}, R) durch:

A = \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N = \{[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}], …,[\begin{matrix}X \\ k \end{matrix}]\} für das genannte k ∈ IN

z_{n} =[\begin{matrix}X \\ 0 \end{matrix}]^{n} für jedes n ∈ IN^{+}

und R bestehend aus den folgenden Regeln:

\begin{matrix}[\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→ M[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}] \\ [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]→ M[\begin{matrix}X \\ 2 \end{matrix}], & [\begin{matrix}X \\ 2 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}] \\ [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}]→ M[\begin{matrix}X \\ 3 \end{matrix}], & [\begin{matrix}X \\ 3 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 3 \end{matrix}] \\ ⋮ & ⋮ \\ [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ (k − 1) \end{matrix}]→ M[\begin{matrix}X \\ k \end{matrix}] & [\begin{matrix}X \\ k \end{matrix}][\begin{matrix}X \\ (k − 1) \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ k \end{matrix}] \end{matrix}

Definiere eine Zeichenbewertung f: A ∪ N → Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} durch:

\begin{matrix}f(M) = 1, & f([\begin{matrix}M \\ # \end{matrix}]) = 2 \\ f([\begin{matrix}X \\ 0 \end{matrix}]) = 1, & f([\begin{matrix}X \\ i \end{matrix}]) = (w(s))^{i} für i = 1, …, k \end{matrix}

Damit sieht man, daß Z eine s-Zählersequenz ist. Wie groß ist nun die Kapazität dieser Zählersequenz ?

Es ist ρ(Z, f) = \{(M →[\begin{matrix}M \\ # \end{matrix}])\} für alle Zeichenbewertungen f für Z. Zusammen mit dieser

Regel sind in Z für jede Anfangssatzform z_{n} folgende Ableitungsschritte möglich:

Mz_{n} = M[\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 1 \end{matrix}]…[\begin{matrix}X \\ 1 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 2 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]…[\begin{matrix}X \\ 1 \end{matrix}]

⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 1 \end{matrix}]…[\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}][\begin{matrix}X \\ 2 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 2 \end{matrix}]…[\begin{matrix}X \\ 2 \end{matrix}]

⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 3 \end{matrix}]⟹^{∗} … ⟹^{∗} M[\begin{matrix}X \\ k \end{matrix}]…[\begin{matrix}X \\ k \end{matrix}]

Die Kapazität ist also:

K_{Z}(n) = ∑_{i_{k}=1}^{n} ∑_{i_{k−1}=1}^{i_{k}} … ∑_{i_{2}=1}^{i_{3}} ∑_{i_{1}}^{i_{2}} i_{1} = ∑_{i_{k}=1}^{n} ∑_{i_{k−1}=1}^{i_{k}} … ∑_{i_{2}=1}^{i_{3}} \frac{(i_{2} + 1) · i_{2}}{2}

≥ \frac{1}{2} ∑_{i_{k}=1}^{n} ∑_{i_{k−1}=1}^{i_{k}} … ∑_{i_{2}=1}^{i_{3}} i_{2}^{2}

∈ O(n^{k}) \ O(n^{k−1})

Mit dieser Zählersequenz, die im folgenden Polynomialzähler genannt werden soll, kann man schon einiges anfangen, genauer gesagt, kann man mit seiner Hilfe jeden linear beschränkten Automaten, der in Polynomialzeit arbeitet, simulieren (siehe Kapitel 5.2). Doch man kann die Zählersequenz noch weiter verbessern, so daß man auch (in Abhängigkeit vom Index n) exponentielle Werte erhält. Bei der Untersuchung solcher Zähler konzentrieren wir uns auf Stellenbewertungen s mit s(1) = 1.

Das Naheliegendste wäre, jede Anfangssatzform und alle daraus abgeleiteten Satzformen konsequent als Zahl zu betracheten, in der jede Ziffer durch ein Zeichen dargestellt wird. Die Regeln vollziehen dann die Vorgehensweise des arithmetischen Addierens nach. Dabei wird die Zahl in der Satzform gegenüber der Zifferndarstellung spiegelverkehrt dargestellt.

Zunächst ein Beispiel:

Beispiel 4.2.6 : Sei s_{2} die durch s_{2}(i) = 2^{i−1} für alle i ∈ IN^{+} gegebene Stellenbewertung. Definiere Z = (A, N, (z_{n})_{n∈IN^{+}}, R) durch:

A = \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N = \{[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}],[\begin{matrix}X \\ U \end{matrix}]\} ,

Z =[\begin{matrix}X \\ 0 \end{matrix}]^{n} für jedes n ∈ IN

und R bestehend aus den Regeln:

\begin{matrix}(1) [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→ M[\begin{matrix}X \\ 1 \end{matrix}] & (3) [\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}] \\ (2) [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]→ M[\begin{matrix}X \\ U \end{matrix}] & (4) [\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ U \end{matrix}] \end{matrix}

Zusammen mit der Regel M → [\begin{matrix}M \\ # \end{matrix}]sind in Z für jede Anfangssatzform z_{n} folgende Ablei-

tungsschritte möglich:

Mz_{n} = M[\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]

⟹^{∗} M[\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]

⟹^{∗} M[\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} M[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]…[\begin{matrix}X \\ 0 \end{matrix}]⟹^{∗} …

… ⟹^{∗} M[\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ U \end{matrix}]…[\begin{matrix}X \\ U \end{matrix}]

Das scheint also eine hübsche Zählersequenz mit der Kapazität

2 · ∑_{i=1}^{n} 2^{i−1} = ∑_{i=1}^{n} 2^{i} = 2^{n+1} − 2 ≥ 2^{n}

zu sein. Sei nun f: A ∪ N → IN eine Zeichenbewertung. Dann folgt:

aus der Regel (3)  : {1 · f([\begin{matrix}X \\ U \end{matrix}]) + 2 · f([\begin{matrix}X \\ 0 \end{matrix}]) < 1 · f([\begin{matrix}X \\ 0 \end{matrix}]) + 2 · f([\begin{matrix}X \\ 1 \end{matrix}]) \atop ⇒ f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 1 \end{matrix}]) < f([\begin{matrix}X \\ 1 \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}])}

und aus der Regel (4) : {1 · f([\begin{matrix}X \\ U \end{matrix}]) + 2 · f([\begin{matrix}X \\ 1 \end{matrix}]) < 1 · f([\begin{matrix}X \\ 0 \end{matrix}]) + 2 · f([\begin{matrix}X \\ U \end{matrix}]) \atop ⇒ f([\begin{matrix}X \\ 1 \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]) < f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 1 \end{matrix}])}

Beides kann nicht gleichzeitig erfüllt sein, also gibt es keine Zeichenbewertung, mit der alle Regeln aus R s_{2}-schwach wachsend sind.

Daraus folgt, daß Z keine s_{2}-Zählersequenz ist.

Das hängt damit zusammen, daß die Anzahl der darstellbaren Ziffern einschließlich des Übertrags beschränkt ist durch den Wachstumsfaktor der betrachteten Stellenbewertung (siehe Satz 4.2.10). Erhöht man diesen (wählt also eine andere Stellenbewertung), läßt sich auch die Basis der Zahlendarstellung erhöhen.

Beispiel 4.2.7 : Sei s_{3} die durch s_{3} = 3^{i−1} für alle i ∈ IN^{+} gegebene Stellenbewertung. Sei Z wie in Beispiel 4.2.6 definiert. Definiere eine Zeichenbewertung f: A ∪ N → IN^{+} durch:

\begin{matrix}f(M) = 1, & f([\begin{matrix}M \\ # \end{matrix}]) = 2, \\ f([\begin{matrix}X \\ 0 \end{matrix}]) = 1, & f([\begin{matrix}X \\ 1 \end{matrix}]) = 2, & f([\begin{matrix}X \\ U \end{matrix}]) = 3 \end{matrix}

Alle Regeln aus R sind s_{3}-schwach wachsend mit f. Also ist Z eine s_{3}-Zählersequenz mit der Kapazität K_{Z}(n) ≥ 2^{n} (s.o.).

Das läßt sich verallgemeinern, aber man kann noch etwas weiter gehen, indem man jede Ziffer der Zahlendarstellung statt durch ein Zeichen durch mehrere darstellt. Dadurch erhöht sich die Anzahl der darstellbaren Ziffern, bleibt aber begrenzt in Abhängigkeit vom Wachstumsfaktor (siehe Satz 4.2.10).

Beispiel 4.2.8 : Sei s_{2} die durch s_{2}(i) = 2^{i−1} für alle i ∈ IN gegebene Stellenbewertung. Es gibt eine s_{2}-Zählersequenz mit einer Kapazität K_{Z}(n) ≥ 3^{⌊^{\frac{n}{2}}⌋} für n ≥ 2. Definiere eine Zählersequenz Z = (A, N, (z_{n})_{n∈IN^{+}}, R) durch:

A = \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N = \{D,[\begin{matrix}M \\ 0 \end{matrix}],[\begin{matrix}M \\ 1 \end{matrix}],[\begin{matrix}M \\ 2 \end{matrix}],[\begin{matrix}M \\ U \end{matrix}]\} ,

z_{n} = (D[\begin{matrix}X \\ 0 \end{matrix}])^{⌊^{\frac{n}{2}}⌋} für gerades n ∈ IN^{+} z_{n} = (D[\begin{matrix}X \\ 0 \end{matrix}])^{⌊^{\frac{n}{2}}⌋}D für ungerades n ∈ IN^{+}

und R bestehend aus den folgenden Regeln:

\begin{matrix}[\begin{matrix}M \\ # \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]→ MD[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}M \\ # \end{matrix}]D[\begin{matrix}X \\ 1 \end{matrix}]→ MD[\begin{matrix}X \\ 2 \end{matrix}], & [\begin{matrix}M \\ # \end{matrix}]D[\begin{matrix}X \\ 2 \end{matrix}]→ MD[\begin{matrix}X \\ U \end{matrix}] \\ [\begin{matrix}X \\ U \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D[\begin{matrix}X \\ 1 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D[\begin{matrix}X \\ 2 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D[\begin{matrix}X \\ 2 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D[\begin{matrix}X \\ U \end{matrix}] \end{matrix}

Definiere eine Zeichenbewertung f: A ∪ N → IN durch:

\begin{matrix}f(M) = 1, & f([\begin{matrix}M \\ # \end{matrix}]) = 16, & f(D) = 1 \\ f([\begin{matrix}X \\ 0 \end{matrix}]) = 1, & f([\begin{matrix}X \\ 1 \end{matrix}]) = 6, & f([\begin{matrix}X \\ 2 \end{matrix}]) = 11, & f([\begin{matrix}X \\ U \end{matrix}]) = 16 \end{matrix}

Damit sieht man, daß Z eine s_{2}-Zählersequenz ist.

Es ist ρ(Z, f) = \{(M →[\begin{matrix}M \\ # \end{matrix}])\} für alle Zeichenbewertungen f für Z. In Z sind für jede

Anfangssatzform z_{n} folgende Ableitungsschritte möglich (dabei sei δ = D für n ungerade, δ = ε für n gerade):

Mz_{n} = MD[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ 0 \end{matrix}]δ ⟹^{∗} MD[\begin{matrix}X \\ 1 \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ 0 \end{matrix}]δ ⟹^{∗} MD[\begin{matrix}X \\ 2 \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ 0 \end{matrix}]δ

⟹^{∗} MD[\begin{matrix}X \\ U \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ 0 \end{matrix}]δ ⟹^{∗} MD[\begin{matrix}X \\ 0 \end{matrix}]D[\begin{matrix}X \\ 1 \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ 0 \end{matrix}]δ

⟹^{∗} MD[\begin{matrix}X \\ 0 \end{matrix}]D[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ U \end{matrix}]δ ⟹^{∗} MD[\begin{matrix}X \\ 0 \end{matrix}]… D[\begin{matrix}X \\ 0 \end{matrix}]D[\begin{matrix}X \\ U \end{matrix}]D[\begin{matrix}X \\ U \end{matrix}]δ

⟹^{∗} MD[\begin{matrix}X \\ U \end{matrix}]… D[\begin{matrix}X \\ U \end{matrix}]δ

Die Satzformteile D[\begin{matrix}X \\ 0 \end{matrix}], D[\begin{matrix}X \\ 1 \end{matrix}], D[\begin{matrix}X \\ 2 \end{matrix}] und D[\begin{matrix}X \\ U \end{matrix}] stellen also die Ziffern 0, 1, 2 und den

Übertrag der 3-adischen Zahlendarstellung dar.

Die Kapazität von Z ist also für jeden Index n die im 3-adischen System durch 1^{⌊^{\frac{n}{2}}⌋}0 dargestellte Zahl (die Satzform ist voll Überträge, die für die Zahlendarstellung aufgelöst wurden). Das ist:

\begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ i=1 \end{matrix} 3^{i} = 3 · ∑_{i=0}^{⌊\frac{n}{2}⌋−1} 3^{i} = 3 · \frac{3^{⌊^{\frac{n}{2}}⌋} − 1}{3 − 1} ≥ 3^{⌊^{\frac{n}{2}}⌋} für n ≥ 2

Diese Technik läßt sich für andere Stellenbewertungen und größere ”Ziffernbreiten“ verallgemeinern. Das wollen wir nun tun, wobei wir zunächst bei Stellenbewertungen s mit s(1) = 1 bleiben.

Satz 4.2.9 : Sei b ∈ IN , b ≥ 2, sei s_{b} dazu die durch s_{b}(i) = b^{i−1} für alle i ∈ IN^{+} definierte Stellenbewertung. Sei l ∈ IN und b^{l} ≠ 2. Dann gibt es eine s_{b}-Zählersequenz Z, die abhängig vom Index n eine Kapazität

K_{Z}(n) ≥ (b^{l} − 1)^{⌊^{\frac{n}{l}}⌋} für n ≥ l

besitzt.

Beweis: Sei also b ∈ IN , b ≥ 2 gegeben, s_{b} dazu durch s_{b}(i) = b^{i−1} für alle i ∈ IN definiert. Sei l ∈ IN mit l > 1 im Falle b = 2.

Definiere eine Zählersequenz Z = (A, N, (z_{n})_{n∈IN^{+}}, R) durch:

\begin{matrix}A = \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N = \{D,[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}],[\begin{matrix}X \\ 2 \end{matrix}], …,[\begin{matrix}X \\ b^{l} − 2 \end{matrix}],[\begin{matrix}X \\ U \end{matrix}]\} \\ z_{n} = (D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}])^{⌊^{\frac{n}{l}} ⌋} D^{n mod l} \end{matrix}

und R bestehend aus den folgenden Regeln (für i = 1, …, b^{l} − 3):

\begin{matrix}(R1) & [\begin{matrix}M \\ # \end{matrix}]D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}]→ MD^{l−1}[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ 1 \end{matrix}] \\ (R2) & [\begin{matrix}M \\ # \end{matrix}]D^{l−1}[\begin{matrix}X \\ i \end{matrix}]→ MD^{l−1}[\begin{matrix}M \\ i + 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ i \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}M \\ i + 1 \end{matrix}] \\ (R3) & [\begin{matrix}M \\ # \end{matrix}]D^{l−1}[\begin{matrix}X \\ b^{l} − 2 \end{matrix}]→ MD^{l−1}[\begin{matrix}X \\ U \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ b^{l} − 2 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ U \end{matrix}] \end{matrix}

Dazu definiere eine Zeichenbewertung f: A ∪ N → IN durch:

f(M) = 1,  f([\begin{matrix}M \\ # \end{matrix}]) = b^{l},  f([\begin{matrix}X \\ 0 \end{matrix}]) = 1,  f([\begin{matrix}X \\ U \end{matrix}]) = b^{l},

f(D) = 1, f([\begin{matrix}X \\ i \end{matrix}]) = i + 1, für alle i = 1, …, b^{l} − 2

Dann gilt für die Bewertungen der Regeln aus R:

(Dabei sei d := b · 1 + b^{2} · 1 + … + b^{l} · 1 = ∑_{j=1}^{l} b^{j}.)

zu (R1) : (beide Regeln haben die gleiche Bewertung) Es gilt:

1 · b^{l} + d + b^{l} · 1 < 1 + d + b^{l} · 2

Also sind die Regeln (R1) s_{b}-schwach wachsend kontextsensitiv mit f. zu (R2) : (für gleiches i ergeben sich jeweils gleiche Bewertungen) Sei i ∈ {1, …, b^{l} − 3}. Es gilt:

b^{l} + d + b^{l} · (i + 1) = d + b^{l} · (i + 2) < 1 + d + b^{l} · (i + 2)

Also sind auch die Regeln (R2) s_{b}-schwach wachsend kontextsensitiv mit f. zu (R3) : (beide Regeln haben die gleiche Bewertung) Es gilt:

b^{l} + d + b^{l} · (b^{l} − 1) = d + b^{2·l} < 1 + d + b^{2·l}

Also sind auch die Regeln (R3) s_{b}-schwach wachsend kontextsensitiv mit f.

Also ist Z eine s_{b}-Zählersequenz.

Es ist ρ(Z, f) = \{(M →[\begin{matrix}M \\ # \end{matrix}])\} für alle Zeichenbewertungen f für Z. In Z wird sozusagen

in (b^{l} − 1)-adischer Darstellung gezählt, wobei jede Ziffer l Stellen in Anspruch nimmt. Die Kapazität von Z ist also für jeden Index n ≥ l die im (b^{l} − 1)-adischen System durch 1^{⌊^{\frac{n}{l}}⌋}0 dargestellte Zahl (die Satzform ist voller Überträge, die für die Zahlendarstellung aufgelöst wurden). Das ist (wegen b^{l} ≠ 2)

\begin{matrix}⌊ & \frac{n}{l} & ⌋ \\ ∑ \\ j=1 \end{matrix}(b^{l} − 1)^{j} = (b^{l} − 1) · ∑_{j=0}^{⌊\frac{n}{l}⌋−1}(b^{l} − 1)^{j}

= (b^{l} − 1) · \frac{(b^{l} − 1)^{⌊^{\frac{n}{l}}⌋} − 1}{(b^{l} − 1) − 1} ≥ (b^{l} − 1)^{⌊^{\frac{n}{l}}⌋} für n ≥ l

Also ist die Kapazität K_{Z}(n) ≥ (b^{l} − 1)^{⌊^{\frac{n}{l}}⌋} für n ≥ l. ♣

Es wird vermutet, daß diese Zählersequenz aus Satz 4.2.9 optimal ist in dem Sinne, daß es (zu einem festen b ∈ IN , b ≥ 2) keine s_{b}-Zählersequenz gibt, deren Kapazität nicht mehr in O ((b^{l} − 1)^{⌈^{\frac{n}{l}}⌉}) liegt für jedes l ∈ IN .

Wir wollen zumindest nachweisen, daß die Zählersequenz aus Satz 4.2.9 für ihre Technik optimal ist.

Satz 4.2.10 : Sei b ∈ IN , b ≥ 2, sei s_{b} dazu die durch s_{b}(i) = b^{i−1} für alle i ∈ IN^{+} definierte Stellenbewertung. Sei l ∈ IN und b^{l} ≠ 2. Sei Z = (A, N, (z_{n})_{n∈IN^{+}}, R) gegeben mit:

A ⊇ \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N ⊇ \{D,[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}],[\begin{matrix}X \\ 2 \end{matrix}], …,[\begin{matrix}X \\ b^{l} − 2 \end{matrix}],[\begin{matrix}X \\ b^{l} − 1 \end{matrix}],[\begin{matrix}X \\ U \end{matrix}]\}

und R enthalte die folgenden Regeln:

\begin{matrix}(R1) & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ 1 \end{matrix}] \\ (R2) & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ i \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ i + 1 \end{matrix}] für i = 1, …, b^{l} − 2 \\ (R3) & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ b^{l} − 1 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ U \end{matrix}] \end{matrix}

Das heißt, die Basis der Z zugrundeliegenden Zahlendarstellung ist wenigstens b^{l}. Dann ist kein Z_{n} aus der Sequenz Z ein s_{b}-Zähler.

Beweis: Seien die Voraussetzungen des Satzes erfüllt und die Definitionen darin gültig. Sei n ∈ IN^{+}, sei Z_{n} das n-te Glied der Sequenz Z.

Annahme: Es gibt eine Zeichenbewertung f: A ∪ N → IN für Z_{n} mit f([\begin{matrix}M \\ # \end{matrix}]) > f(M).

Dann folgt:

aus (R1) : f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]) < b^{l} · (f([\begin{matrix}X \\ 1 \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]))

aus (R2) : f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]) < b^{l} · (f([\begin{matrix}X \\ i + 1 \end{matrix}]) − f([\begin{matrix}X \\ i \end{matrix}])) für i = 1, …, b^{l} − 2.

aus (R3) : f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]) < b^{l} · (f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ b^{l} − 1 \end{matrix}]))

Definiere f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]) =: μ. Es ist also

μ = f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}]) = f([\begin{matrix}X \\ U \end{matrix}]) − f([\begin{matrix}X \\ b^{l} − 1 \end{matrix}]) + f([\begin{matrix}X \\ b^{l} − 1 \end{matrix}]) − + … + f([\begin{matrix}X \\ 1 \end{matrix}]) − f([\begin{matrix}X \\ 0 \end{matrix}])

> \underbrace{\frac{1}{b^{l}} · μ + \frac{1}{b^{l}} · μ + … + \frac{1}{b^{l}} · μ}_{b^{l} mal} = b^{l} · \frac{1}{b^{l}} · μ = μ

und das ist unmöglich.

Also gibt es eine solche Zeichenbewertung f nicht, also ist Z_{n} kein s_{b}-Zähler. ♣

Man kann Satz 4.2.9 (und auch Satz 4.2.10) für Stellenbewertungen mit gebrochenen Wachstumsfaktoren verallgemeinern, wobei die vorgestellte Methode voraussetzt, daß einschließlich des Übertrags wenigstens 3 Ziffern darstellbar sind. Es gilt also:

Satz 4.2.11 : Sei s eine gleichmäßige streng monoton wachsende Stellenbewertung, sei l ∈ IN und s mit mindestens l + 1 bewerteten Stellen. Außerdem gelte (w(s))^{l} ≥ 3. Dann gibt es eine s-Zählersequenz Z, die abhängig vom Index n eine Kapazität

K_{Z}(n) ≥ (⌊(w(s))^{l} − 1⌋)^{⌊^{\frac{n}{l}}⌋} für n ≥ l

besitzt.

4.3 Simulation zeitbeschränkter linearer Automaten

Die in Satz 4.2.9 vorgestellten Zähler werden nun in der Simulation eines linear beschränkten Automaten statt der in Kap. 3.2 verwendeten Verschlucker eingesetzt. Aus der Kapazität einer Zählersequenz ergeben sich Zeitschranken für die mit Hilfe dieser Zählersequenz simulierbaren linear beschränkten Automaten.

Satz 4.3.1 : Sei b ∈ IN^{+}, b ≥ 2, sei q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} mit 0 < q < 1.

Dann gilt:

T –NSPACE-TIME (n, O(b^{q·n})) ⊆ WGCSL_{b}

Beweis: Sei also b ∈ IN^{+}, b ≥ 2, sei auch q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} beliebig mit 0 < q < 1 gegeben. Sei s_{b} die durch s_{b}(i) = b^{i−1} für alle i ∈ IN^{+} definierte Stellenbewertung. Sei L ∈ T –NSPACE-TIME (n, O(b^{q·n})). Sei M = (Q, Σ, Γ, □, δ, q_{0}, F) ein linear beschränkter Automat, der L in der Zeit t · b^{q·n} mit einem t ∈ IN erkennt.

Es gibt ein k ∈ IN , so daß \frac{k}{k−1} · q < 1.

Für dieses k gibt es wiederum ein l ∈ IN , so daß b^{l} > b^{l·q· \frac{k}{k−1}} + 1 gilt, und das ist gleichwertig mit (b^{l} − 1)^{\frac{k−1}{k} · \frac{1}{l}} > b^{q}. Halte dieses k und dieses l nun für die Konstruktion fest.

Sei M_{k} = (Q_{k}, Σ_{k}, Γ_{k}, □_{k}, δ_{k}, q_{0,k}, F_{k}) der nach Satz 1.2.3 zu M konstruierte lineare Automat, der die Sprache

L_{k} := {w ∈ (Σ^{k})^{∗} · Σ^{≤k} | nat(w) ∈ L}

erkennt. M_{k} arbeitet (”absolut“ gesehen) nicht länger als M und benötigt dabei den Platz ⌈\frac{n}{k}⌉ für n = |nat(w)|, w ∈ L_{k}.

Konstruiere nun eine Grammatik G_{k} = ⟨N_{k}, Σ_{k} ∪ {•}, S, P_{k}⟩. Dafür seien Γ′_{k} = {a′ | a ∈ Γ_{k}} und Γ′′_{k} = {a′′ | a ∈ Γ_{k}} wie in den Beweisen aus Kapitel 3.2 markierte Kopien des Arbeitsalphabetes Γ_{k} für den linken bzw. den rechten Rand. Sei r := t · (b^{l} − 1).

Für die Menge der Nichtterminale definiere N_{BandAnf} und N_{Band} zu M_{k} wie im Beweis von Satz 3.1.1 (vgl. Beweis von Satz 3.2.6) sowie

N_{BandEnd} = \{[\begin{matrix}x \\ a′′ \\ ⋆_{i} \end{matrix}]| x ∈ Σ_{k}, a′′ ∈ Γ′′_{k}, i ∈ \{0, 1, …, r\}\}

N_{Zustlinks} = \{[\begin{matrix}x \\ a^{∗} \\ q^{L} \end{matrix}]| x ∈ Σ_{k}, a^{∗} ∈ Γ_{k} ∪ Γ′_{k}, q ∈ Q_{k}\}

N_{Zustrechts} = \{[\begin{matrix}x \\ a \\ q^{R} \end{matrix}]| x ∈ Σ_{k}, a^{∗} ∈ Γ_{k}, q ∈ Q_{k}\}

N_{ZustEnd} = \{[\begin{matrix}x \\ a′′ \\ q^{R} \\ ⋆_{i} \end{matrix}]| x ∈ Σ_{k}, a′′ ∈ Γ′′_{k}, q ∈ Q_{k}, i ∈ \{0, 1, …, r\}\}

N_{Gewicht} = \{[\begin{matrix}x \\ a \\ ⋆ \end{matrix}]| x ∈ Σ_{k}, a ∈ Γ_{k}\}

N_{Zähler} = \{D,[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}],[\begin{matrix}X \\ 2 \end{matrix}], …,[\begin{matrix}X \\ b^{l} − 2 \end{matrix}],[\begin{matrix}X \\ U \end{matrix}]\}

Es wird also festgelegt, daß der Zustand auf dem linken Rand immer mit einer Linksbewegung und auf dem rechten Rand immer mit einer Rechtsbewegung markiert wird.

Definiere also die Nichtterminalmenge N_{k} durch:

N_{k} = {S, B, C} ∪ N_{BandAnf} ∪ N_{Band} ∪ N_{BandEnd} ∪ N_{Zustlinks} ∪ N_{Zustrechts} ∪ N_{ZustEnd}
∪ N_{Gewicht} ∪ N_{Zähler}

Die Regelmenge P_{k} bestehe aus den folgenden Regeln:

Dabei seien x, y, z ∈ Σ_{k}, a, b, c, d ∈ Γ_{k}, dazu a′, c′ ∈ Γ′_{k} und a′′, b′′, c′′ ∈ Γ′′_{k} gerade die jeweiligen markierten Kopien von a, c für den linken und von a, b, c für den rechten Rand. Es seien H ∈ {L, R}, p, q, q̃ ∈ Q_{k} sowie [a^{∗} = a′ ∧ c^{∗} = c′] ∨ [a^{∗} = a ∧ c^{∗} = c] und [b^{∗} = b ∧ d^{∗} = d] ∨ [b^{∗} = b′′ ∧ d^{∗} = d′′].

Banderzeugung:

S →[\begin{matrix}a \\ a′ \\ q_{0,k}^{L} \end{matrix}]BC, B →[\begin{matrix}a \\ a \end{matrix}]B, B →[\begin{matrix}a \\ a′′ \\ ⋆_{0} \end{matrix}]

Zählererzeugung:

C → D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}]C, C → D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}], C → D^{j} für j = 1, …, l − 1

Bewegung nach rechts: Falls (p, c, R) ∈ δ_{k}(q, a), so enthält P_{k} die folgenden Regeln (dabei sei i ∈ {0, …, r − 1}, und es wird gefordert: a^{∗} ∈ Γ′_{k} ⇒ H = L):

[\begin{matrix}x \\ a^{∗} \\ q^{H} \end{matrix} ][\begin{matrix}y \\ b \end{matrix}]→[\begin{matrix}x \\ c^{∗} \end{matrix}][\begin{matrix}y \\ b \\ p^{R} \end{matrix}],  [\begin{matrix}x \\ a^{∗} \\ q^{H} \end{matrix} ][\begin{matrix}y \\ b′′ \\ ⋆_{i} \end{matrix}]→[\begin{matrix}x \\ c^{∗} \end{matrix}][\begin{matrix}y \\ b′′ \\ p^{R} \\ ⋆_{i} \end{matrix}]

Bewegung am rechten Rand: Falls (q̃, x, R) ∈ δ_{k}(q, a) und (p, □, L) ∈ δ_{k}(q̃, □), dann enthält P_{k} die Regel (dabei sei i ∈ {0, …, r − 1}):

[\begin{matrix}x \\ a′′ \\ q^{R} \\ ⋆_{i} \end{matrix}]→[\begin{matrix}x \\ c′′ \\ p^{R} \\ ⋆_{i} \end{matrix}]

Bewegung nach links: Falls (p, d, L) ∈ δ_{k}(q, b), so enthält P_{k} die folgenden Regeln (dabei sei i ∈ {0, …, r − 1}):

[\begin{matrix}x \\ a^{∗} \end{matrix}][\begin{matrix}y \\ b \\ q^{L} \end{matrix}]→[\begin{matrix}x \\ a^{∗} \\ p^{L} \end{matrix}][\begin{matrix}y \\ d \end{matrix}],  [\begin{matrix}x \\ a^{∗} \end{matrix}][\begin{matrix}y \\ b \\ q^{R} \end{matrix}]→[\begin{matrix}x \\ a^{∗} \\ p^{L} \end{matrix}][\begin{matrix}y \\ d \\ ⋆ \end{matrix}],  [\begin{matrix}x \\ a^{∗} \end{matrix}][\begin{matrix}y \\ b′′ \\ q^{R} \\ ⋆_{i} \end{matrix}]→[\begin{matrix}x \\ a^{∗} \\ p^{L} \end{matrix}][\begin{matrix}y \\ d′′ \\ ⋆_{i+1} \end{matrix}]

Bewegung am linken Rand: Falls (q̃, c, L) ∈ δ_{k}(q, a) ∧ (p, □, R) ∈ δ_{k}(q̃, □), so enthält P_{k} Regel:

[\begin{matrix}x \\ a′ \\ q^{L} \end{matrix}]→[\begin{matrix}x \\ c′ \\ p^{L} \end{matrix}]

Gewichtswanderung (mit Sammeln) (dabei sei i ∈ {0, …, r − 1}):

[\begin{matrix}x \\ a \\ ⋆ \end{matrix}][\begin{matrix}y \\ b \end{matrix}]→[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b \\ ⋆ \end{matrix}],  [\begin{matrix}x \\ a \\ ⋆ \end{matrix}][\begin{matrix}y \\ b′′ \\ ⋆_{i} \end{matrix}]→[\begin{matrix}x \\ a \end{matrix}][\begin{matrix}y \\ b′′ \\ ⋆_{i+1} \end{matrix}]

Gewichte ”zählen“ (dabei sei j ∈ {1, …, b^{l} − 3}):

\begin{matrix}(R1) & [\begin{matrix}y \\ b′′ \\ ⋆_{r} \end{matrix}]D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}y \\ b′′ \\ ⋆_{0} \end{matrix}]D^{l−1}[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ 1 \end{matrix}] \\ (R2) & [\begin{matrix}y \\ b′′ \\ ∗_{r} \end{matrix}]D^{l−1}[\begin{matrix}X \\ j \end{matrix}]→[\begin{matrix}y \\ b′′ \\ ⋆_{0} \end{matrix}]D^{l−1}[\begin{matrix}X \\ j + 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ j \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ j + 1 \end{matrix}] \\ (R3) & [\begin{matrix}y \\ b′′ \\ ⋆_{r} \end{matrix}]D^{l−1}[\begin{matrix}X \\ b^{l} − 2 \end{matrix}]→[\begin{matrix}y \\ b′′ \\ ⋆_{0} \end{matrix}]D^{l−1}[\begin{matrix}X \\ U \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}]D^{l−1}[\begin{matrix}X \\ b^{l} − 2 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}]D^{l−1}[\begin{matrix}X \\ U \end{matrix}] \end{matrix}

Akzeptieren:

Falls (q_{F} , c, R) ∈ δ_{k}(q, a) mit q_{F} ∈ F_{k}, so enthält P_{k} die Regel (dabei sei i ∈ {0, 1, …, r}):

[\begin{matrix}x \\ a \\ q^{R} \\ ⋆_{i} \end{matrix}]→ x

Eingabe in Terminale umwandeln:

[\begin{matrix}x \\ a \end{matrix}]y → xy,  [\begin{matrix}x \\ a′ \end{matrix}]y → xy

und für jedes Y ∈ N_{Zähler}:

xY → x•, •Y → ••

Der durch Kapitel 3.2 geübte Leser erkennt sofort, daß aus w ∈ L(G_{k}) folgt: w = w̃•^{m} mit w̃ ∈ L_{k}, m ∈ IN .

In dieser Grammatik G_{k} wird eine durch Z = (A, N, (z_{m})_{m∈IN^{+}}, R) mit

A = N_{BandEnd},  N = N_{Zähler},  z_{n} = (D^{l−1}[\begin{matrix}X \\ 0 \end{matrix}])^{⌊^{\frac{m}{l}}⌋}D^{m mod l},
R = {(R1), (R2), (R3)}

definierte Zählersequenz realisiert, die gemäß Satz 4.2.9 konstruiert ist. Sie hat also in Abhängigkeit vom Index m eine Kapazität von wenigstens r · (b^{l} − 1)^{⌊^{\frac{m}{l}}⌋}.

Sei nun w ∈ L_{k} und n = |nat(w)|. Für n ≥ \frac{k·l}{k−1} ist ⌊\frac{k−1}{k} · n⌋ ≥ l. Für m ≥ ⌊\frac{k−1}{k} · n⌋ folgt

also für die Kapazität von Z (wegen ⌊\frac{⌊\frac{k−1}{k} ·n⌋}{l}⌋ = ⌊\frac{k−1}{k} · \frac{n}{l}⌋ ):

K_{Z}(m) ≥ r · (b^{l} − 1)^{⌊^{\frac{m}{l}}⌋}
≥ r · (b^{l} − 1)^{⌊\frac{k−1}{k} · \frac{n}{l}⌋} ≥ t · (b^{l} − 1) · (b^{l} − 1)^{⌊\frac{k−1}{k} · \frac{n}{l}⌋}
≥ t · (b^{l} − 1)^{⌈\frac{k−1}{k} · \frac{n}{l}⌉} > t · b^{q·n}

Das heißt, die Arbeit von M_{k} kann, falls M_{k} akzeptiert und w ∈ L_{k} hinreichend lang ist, also |nat(w)| ≥ \frac{k·l}{k−1}, bis zum Schluß simuliert werden, und daraus folgt:

L(G_{k}) ⊇ \{w ∈ (Σ_{k})^{∗} \{•\}^{∗} | \begin{matrix}w = w̃•^{m}, w̃ ∈ L_{k}, \\ |nat(w̃)| ≥ \frac{k·l}{k−1}, m ≥ ⌊\frac{k−1}{k} · |nat(w̃)|⌋ \end{matrix} \} (♢)

(Die Gleichheit beider Mengen kann nur deshalb nicht gefolgert werden, weil es möglich ist, daß einige Wörter in kürzerer als der abgeschätzten Zeit erkannt werden können und demzufolge auch durch die Grammatik mit einem kleineren Überhang von Punkten (•) erzeugt werden können.)

Bevor wir nun die Grammatik G_{k} zu einer Grammatik G mit L(G) = L erweitern, soll noch gezeigt werden, daß G_{k} die Voraussetzungen von Satz 2.1.2 erfüllt und somit L(G_{k}) ∈ WGCSL_{b} gilt.

Dazu definiere eine Zeichenbewertung f′: N_{k} ∪ Σ_{k} → IN durch:

f′(S) = f(B) = f(C) = 1
f′(X) = 3 für alle X ∈ N_{BandAnf} ∪ N_{Band}
f′(Z_{R}) = 4 für alle Z_{R} ∈ N_{Zustrechts}
f′(Z_{L}) = 2 für alle Z_{L} ∈ N_{Zustlinks}
f′(B_{G}) = 5 für alle B_{G} ∈ N_{Gewicht}
f′([\begin{matrix}x \\ a′′ \\ ⋆_{i} \end{matrix}]) = (r + 1) + i · \frac{(r+1)·(b^{l}−1)}{r} für alle i = 0, …, r

f′([\begin{matrix}x \\ a′′ \\ q^{R} \\ ⋆_{i} \end{matrix}]) = 1 + (r + 1) + i · \frac{(r+1)·(b^{l}−1)}{r} für alle i = 0, …, r

f′(D) = (r + 1)
f′([\begin{matrix}X \\ U \end{matrix}]) = (r + 1) · b^{l},

f′([\begin{matrix}X \\ j \end{matrix}]) = (r + 1) · (j + 1) für alle j = 0, 1, …, b^{l} − 2
f(x) = 4 für alle x ∈ Σ_{k}
f(•)  = (r + 1) · b^{l} + 1

Man sieht durch einfaches Nachrechnen (wie in Satz 3.2.6), daß sämtliche Regeln aus P_{k}, in denen keine Zeichen aus N_{Zähler} vorkommen, s_{b}-schwach wachsend mit f′ oder (nur die Regeln zur Bewegung am rechten bzw. linken Rand) Kettenregeln mit gleichem Gewicht rechts und links sind, wobei \frac{(r+1)·(b^{l}−1)}{r} ≥ 2 (wegen b^{l} > 3) zu bedenken hilfreich ist.

Die Funktionswerte für die Zeichen aus N_{Zähler} sind gegenüber denen im Beweis von Satz

4.2.9 definierten um den Faktor (r + 1) vergrößert (identifiziere dabei die [\begin{matrix}y \\ b′′ \\ ⋆_{d} \end{matrix}]mit [\begin{matrix}M \\ # \end{matrix}]und

die [\begin{matrix}y \\ b′′ \\ ⋆_{0} \end{matrix}]mit M), woraus folgt, daß auch die Regeln (R1), (R2), (R3) s_{b}-schwach wachsend

mit f′ sind. Wegen f′(•) > max{f′(X) | X ∈ N_{Zähler}} sind auch die restlichen Regeln s_{b}-schwach wachsend mit f′.

Damit erfüllt G_{k} die Voraussetzungen von Satz 2.1.2.

Nun konstruiere eine Grammatik G = ⟨N, Σ, S, P ⟩ durch:

N := N_{k} ∪ Σ_{k}, P = P_{k} ∪ P_{Schluß}

wobei N_{k}, Σ_{k}, S und P_{k} aus der obigen Grammatik G_{k} stammen und P_{Schluß} aus den folgenden Regeln besteht:

S → w, w ∈ L, |w| < \frac{k·l}{k−1}
für alle (a_{1}, …, a_{k}) ∈ Σ_{k}, a ∈ Σ : {(a_{1}, …, a_{k})•^{k−1} → a_{1} … a_{k} \atop a• → •a}
und für alle (b_{1}, …, b_{r}) ∈ Σ_{k}, r ≤ k : {(b_{1}, …, b_{r})•^{r−1} → b_{1} … b_{r} \atop (b_{1}, …, b_{r}) → b_{1} … b_{r}}

Diese Grammatik G vollzieht zunächst die Wirkungsweise von G_{k} nach.

Falls auf diese Weise eine Satzform der Form

w̃ •^{m} mit w̃ ∈ L_{k}, m ≤ (k − 1) · ⌊\frac{|nat(w̃)|}{k}⌋

erzeugt wurde, kann in G daraus das entsprechende Wort nat(w̃) ∈ L abgeleitet werden. Wegen

(k − 1) · ⌊\frac{n}{k}⌋ ≥ ⌊\frac{k − 1}{k} · n⌋ für alle n ∈ IN

folgt aus (♢) (Seite 77), daß für jedes Wort w̃ ∈ L_{k} mit |nat(w̃)| ≥ \frac{k·l}{k−1} gilt:

w̃ •^{m} ∈ L(G_{k}) mit m = (k − 1) · ⌊\frac{|nat(w̃)|}{k}⌋

und daraus folgt:

w = nat(w̃) ∈ L(G)

Da es für jedes Wort w ∈ L, |w| ≥ \frac{k·l}{k−1} ein Wort w̃ ∈ L_{k} gibt mit nat(w̃) = w und alle Wörter w ∈ L mit |w| < \frac{k·l}{k−1} in G direkt erzeugt werden, gilt:

L ⊆ L(G)

Da jedes Wort aus L(G_{k}) von der Form w̃{•}^{+}, w̃ ∈ L_{k} ist und der Punkt (•) in G kein Terminal ist, gilt auch L(G) = L.

Definiere nun eine Zeichenbewertung f: N ∪ T → IN^{+} durch:

f(X) = f′(X) für alle X ∈ N_{k} ∪ Σ_{k}
f(x) = f′(•) + 1 für alle x ∈ T

Damit sieht man: G erfüllt (wie G_{k}) die Voraussetzungen von Satz 2.1.2, und damit folgt L ∈ WGCSL_{b}. ♣

Man kann also einen linear beschränkten Automaten, der ”fast“ in der Zeit O (b^{n}) arbeitet, durch eine Grammatik aus WGCSG_{s_{b}} simulieren. Dabei bedeute ”fast“, daß ein q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} , 0 < q < 1 existiert mit: Der linear beschränkte Automat arbeitet in der Zeit O (b^{q·n}).

Entsprechendes zu Satz 4.3.1 läßt sich auch für Stellenbewertungen mit gebrochenem Wachstumsfaktor zeigen, also gilt:

Satz 4.3.2 : Sei s eine gleichmäßige Stellenbewertung mit w(s) > 1 (also streng monoton wachsend), sei q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} mit 0 < q < 1. Dann gilt:

T –NSPACE-TIME (n, O (w(s)^{q·n})) ⊆ WGCSL_{s}

Beweis: Analog zum Beweis von Satz 4.3.1. Man verwende dabei die Zählersequenz aus Satz 4.2.11, an die Stelle von b setze w(s). Wähle l_{1} gemäß dem Beweis von Satz 4.3.1, l_{2} so, daß (w(s))^{l_{2}} ≥ 3 und setzte l = max{l_{1}, l_{2}}. Die Grammatik G_{k} und die Funktion f′ werden wie im genannten Beweis konstruiert und erfüllen ebenso die Voraussetzungen von Satz 2.1.2. Dabei ist hilfreich zu bedenken, daß

\frac{(r+1)·((w(s))^{l}−1)}{r} ≥ 2 wegen (w(s))^{l} ≥ 3 auch hier gilt.

Die Behauptung folgt dann ebenso wie im Beweis von Satz 4.3.1. ♣

Das ungemütliche q in der Zeitschranke des linear beschränkten Automaten ließe sich auch dann nicht beseitigen, wenn man für eine streng monoton wachsende Stellenbewertung s eine s-Zählersequenz kennte mit der Kapazität K_{Z}(n) = w(s)^{n} (bei Index n); in diesem Fall könnte man lediglich die Variable l aus dem Beweis von Satz 4.3.1 von vorneherein festlegen.

Wenn man eine s-Zählersequenz fände mit der Kapazität K_{Z}(n) = w(s)^{p·n} mit p > 1, p ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} , dann könnte man das q in der Zeitschranke des linear beschränkten Automaten wegbekommen.

Bemerkung: Sei s eine streng monoton wachsende Stellenbewertung. Falls es eine Zählersequenz Z gibt mit einer Kapazität K_{Z}(m) ≥ w(s)^{p·m} mit p ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} , p > 1 für jedes hinreichend große m, so folgt daraus:

T –NSPACE-TIME (n, O(w(s)^{n})) ⊆ WGCSL_{w(s)}

Begründung:

Seien die Voraussetzungen und Benennungen der Bemerkung gegeben. Dann gibt es ein k ∈ IN mit \frac{k−1}{k} · p > 1. Simuliere einen linear beschränkten Automaten M, der in der Zeit t · w(s)^{n} arbeitet, wie im Beweis von Satz 4.3.1 mit der neuen Zählersequenz (mit ”Sammeln von r ≥ t · w(s)^{p} Gewichten).

Für n ≥ \frac{k·l}{k−1} ist dann für m ≥ ⌊\frac{k−1}{k} · n⌋:

K_{Z}(m) ≥ r · w(s)^{p·m}
≥ r · w(s)^{p·⌊\frac{k−1}{k} ·n⌋} ≥ t · w(s)^{p·⌈\frac{k−1}{k} ·n⌉}
≥ t · w(s)^{p· \frac{k−1}{k} ·n} > t · w(s)^{n}

Das heißt, die auf diese Weise konstruierte Grammatik erzeugt genau die Sprache L(M).

Die Lücke zwischen Satz 4.3.1 und der Umkehrung von Satz 4.1.11 läßt sich also nicht ohne weiteres schließen.

Konsequenzen und abschließende Bemerkungen

Wir haben in den vergangenen Kapiteln schwach wachsend kontextsensitive Grammatiken bezüglich verschiedener Stellenbewertungen betrachtet.

Bevor wir uns einen abschließenden Überblick verschaffen (Kapitel 5.2), wenden wir uns noch den Stellenbewertungen mit Nullstellen zu, insbesondere denen, die nicht gleichzeitig ungleichmäßig sind. Dabei werden wir die Techniken aus Kapitel 4 einsetzen.

5.1 Die Stellenbewertung mit Nullstellen

Wie sich herausstellt, charakterisieren die schwach wachsend kontextsensitiven Grammatiken bezüglich Stellenbewertungen mit Nullstellen die Klasse CSL .

Für Stellenbewertungen s mit Nullstellen, die gleichzeitig ungleichmäßig sind, folgt aus Satz 3.2.11, daß WGCSL_{s} = CSL gilt. Dabei wird der Beweis von Satz 3.2.11 durch Satz 5.1.3 vollständig.

Gleichmäßige Stellenbewertungen sind per Definition nullstellenfrei. Nach der Bemerkung auf Seite 23 ist jede Stellenbewertung, die weder gleichmäßig noch ungleichmäßig ist und wenigstens zwei Stellen bewertet, bis auf die erste und die letzte bewertete Stelle konstant 0. Für diese Stellenbewertungen gilt:

Satz 5.1.1 : Für Stellenbewertungen s_{c,0_{k},d}, s_{c,0_{k}} und s_{0_{k},d} mit c, d, k ∈ IN^{+} gilt:

(i) WGCSG_{c,0_{k}} ⊆ WGCSG_{c,0_{k},d}

(ii) WGCSL_{1,0} = WGCSL_{c,0_{k}}

(iii) WGCSL_{0,1} = WGCSL_{0_{k},d}

Beweis: Die Behauptung (i) folgt aus Satz 2.1.3, die Behauptungen (ii) und (iii) aus Satz 2.3.7 und Satz 2.1.4. ♣

Um nachzuweisen, daß für jede Stellenbewertung s mit Nullstellen WGCSL_{s} = CSL gilt, genügt es also zu zeigen, daß

WGCSL_{0,1} = CSL und WGCSL_{1,0} = CSL

Bemerkung: Der Satz 4.1.6 läßt sich nicht ohne weiteres auf s_{0,1} und s_{1,0} übertragen. Betrachte dazu die Regeln

(1) A → BC (2) C → DE

Sei

f(A) = 2,  f(B) = 1,  f(C) = 2,  f(D) = 1,  f(E) = 1

Damit sind diese Regeln s_{0,1}-schwach wachsend und könnten also einer s_{0,1}-schwach wachsend kontextsensitiven Grammatik entstammen. Aber bezüglich s_{1,0} sind diese Regeln nicht schwach wachsend mit f, auch nicht die Regeln A → CB, C → ED, die gegenüber den obigen gespiegelt sind. Folgt man der Konstruktion aus dem Beweis von Satz 4.1.6, so erhält man aus (1) die Regel A →[\begin{matrix}C \\ • \end{matrix}]B mit f([\begin{matrix}C \\ • \end{matrix}]) > f(A). In der benötigten Kopie von (2) läßt sich nun das erneute Zusatzgewicht (auch (2) ist eine expandierende Regel) nicht mehr so ablegen, daß die Regel jedenfalls s_{1,0}-schwach wachsend mit f wird und keine neuen Regelkopien benötigt werden.

Wir werden also diese beiden Fälle einzeln verfolgen.

Betrachte zunächst die Stellenbewertung s_{0,1}. Analog zu den Exponentialzählern in Satz 4.2.9 lassen sich auch hier Exponentialzähler konstruieren, dabei ist hier die Basis der Zahlendarstellung, die einer Zählersequenz zugrunde liegt, unbeschränkt. Außerdem ist die ”Verbreiterung“ jeder Ziffer der Zahlendarstellung auf mehrere Zeichen der Satzform hier nicht nötig. Es gilt also:

Satz 5.1.2 : Sei b ∈ IN , b ≥ 2. Dann gibt es eine s_{0,1}-Zählersequenz Z, die eine Kapazität

K_{Z}(n) ≥ b^{n}

besitzt.

Beweis: Sei also b ∈ IN , b ≥ 2 gegeben. Definiere eine Zählersequenz durch Z = (A, N, (z_{n})_{n∈IN^{+}}, R) durch:

\begin{matrix}A = \{M,[\begin{matrix}M \\ # \end{matrix}]\} , N = \{[\begin{matrix}X \\ 0 \end{matrix}],[\begin{matrix}X \\ 1 \end{matrix}],[\begin{matrix}X \\ 2 \end{matrix}], …,[\begin{matrix}X \\ b − 1 \end{matrix}],[\begin{matrix}X \\ U \end{matrix}]\} \\ z_{n} =[\begin{matrix}X \\ 0 \end{matrix}]^{n} \end{matrix}

und R bestehend aus den folgenden Regeln (für i = 1, …, b − 2):

\begin{matrix}(R1) & [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→ M[\begin{matrix}X \\ 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ 0 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ 1 \end{matrix}] \\ (R2) & [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ i \end{matrix}]→ M[\begin{matrix}M \\ i + 1 \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ i \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}M \\ i + 1 \end{matrix}] \\ (R3) & [\begin{matrix}M \\ # \end{matrix}][\begin{matrix}X \\ b − 1 \end{matrix}]→ M[\begin{matrix}X \\ U \end{matrix}], & [\begin{matrix}X \\ U \end{matrix}][\begin{matrix}X \\ b − 1 \end{matrix}]→[\begin{matrix}X \\ 0 \end{matrix}][\begin{matrix}X \\ U \end{matrix}] \end{matrix}

Dazu definiere eine Zeichenbewertung f: A ∪ N → IN durch:

\begin{matrix}f(M) = 1,  f([\begin{matrix}M \\ # \end{matrix}]) = b + 1,  f([\begin{matrix}X \\ 0 \end{matrix}]) = 1,  f([\begin{matrix}X \\ U \end{matrix}]) = b + 1, \\ f([\begin{matrix}X \\ i \end{matrix}]) = i + 1, für alle i = 1, …, b − 1 \end{matrix}

Dann gilt für die Bewertungen der Regeln aus R:

zu (R1) : (beide Regeln haben die gleiche Bewertung) Es gilt:

0 · (b + 1) + 1 · 1 < 0 · 1 + 1 · 2

zu (R2) : (für gleiches i ergeben sich jeweils gleiche Bewertungen) Sei i ∈ {1, …, b − 2}. Es gilt:

0 · (b + 1) + 1 · (i + 1) < 0 · 1 + 1 · (i + 2)

zu (R3) : (beide Regeln haben die gleiche Bewertung) Es gilt:

0 · (b + 1) + 1 · b < 0 · 1 + 1 · (b + 1)

Also sind sämtliche Regeln in R s_{0,1}-schwach wachsend mit f. Also ist Z eine s_{0,1}-Zählerse-quenz. In Z wird in b-adischer Darstellung gezählt, wobei jede Ziffer nur eine Stelle in Anspruch nimmt. Die Kapazität von Z ist also für den Index n ∈ IN^{+} die im b-adischen System durch 1^{n}0 dargestellte Zahl (die Satzform ist voller Überträge, die für die Zahlendarstellung aufgelöst wurden). Das ist (wegen b ≥ 2):

∑_{j=1}^{n} b^{j} = b · ∑_{j=0}^{n−1} b^{j} = b · \frac{b^{n} − 1}{b − 1} ≥ b^{n}

also ist die Kapazität K_{Z}(n) ≥ b^{n}. ♣

Diese Zählersequenz ist genauso konstruiert wie die in Satz 4.2.9 und läßt sich auch genauso einsetzen, um einen linear beschränkten Automaten durch eine s_{0,1}-schwach wachsend kontextsensitive Grammatik zu simulieren. Da die Basis der Zahlendarstellung beliebig aus IN , aber wenigstens 2, gewählt werden kann, kann jeder linear beschränkte Automat, der in Exponentialzeit arbeitet, simuliert werden.

Satz 5.1.3 : Es gilt:

WGCSL_{0,1} = CSL

Beweisidee:

Sei L ∈ CSL . Dann gibt es nach Satz 3.1.3 und der Bemerkung auf S. 14 unten einen linear beschränkten Automaten M, der L in der Zeit 2^{c·n} mit einem c ∈ IN^{+} erkennt.

Wähle nun b ∈ IN^{+}, b ≥ 2 und k ∈ IN^{+} so, daß b^{\frac{k−1}{k}} ≥ 2^{c}. Konstruiere nun Grammatiken G_{k} und (daraus) G analog zum Beweis von Satz 4.3.1 mit diesem b statt b, dem so gewählten k und l = 1 sowie der Zählersequenz aus Satz 5.1.2. Die Ordnung der Regeln wird dabei analog zum Beweis von Satz 2.3.4 auf 2 reduziert. Dann folgt wie in dem genannten Beweis, wobei Satz 2.1.2 zusätzlich mit Blick auf die letzte Banderzeugungsregel und die letzte Zählererzeugungsregel zur Anwendung kommt:

L = L(G) ∈ WGCSL_{0,1}

Nun zur Stellenbewertung s_{1,0}:

Um eine s_{1,0}-Zählersequenz mit der gleichen Kapazität wie die in Satz 5.1.2 zu erhalten, braucht man nur die dort angegebenen Regeln und Anfangssatzformen zu spiegeln, da die Regeln alle längenerhaltend und von der Ordnung 2 sind. Dazu werden Zähler Z = (A, N, z, R) für streng monoton fallende Stellenbewertungen analog zu Definition 4.2.1 definiert, indem für die Regeln aus R verlangt wird: R ⊆ N^{∗} · A × N^{∗} · A ∪ N^{∗} × N^{∗}, die restlichen Bedingungen analog. Die Menge der Inkrementregeln und Zählersequenzen werden nun genauso wie für streng monoton wachsende Stellenbewertungen erklärt, die Kapazität von Zählern und Zählersequenzen analog (”zM ⟹^{∗} z̃M“ statt ”Mz ⟹^{∗} Mz̃“). Damit gilt also:

Satz 5.1.4 : Sei b ∈ IN , b ≥ 2. Dann gibt es eine s_{1,0}-Zählersequenz, die eine Kapazität

K_{Z}(n) ≥ b^{n}

besitzt.

Auch diese Zählersequenz läßt sich einsetzen, um einen linear beschränkten Automaten durch eine s_{1,0}-schwach wachsend kontextsensitive Grammatik zu simulieren.

Im Beweis von Satz 3.2.6 wurde eine Grammatik konstruiert, die einen linear beschränkten Automaten simuliert und in der ein beim Richtungswechsel freiwerdendes Gewicht, in einen Stern (⋆) kodiert, nach rechts wandert, wo es durch einen Verschlucker verschluckt wird. Aus dieser Grammatik wurde im Beweis von Satz 4.3.1 eine mit einer Zählersequenz nach Satz 4.2.9 statt des Verschluckers konstruiert. Oben, in Satz 5.1.3, wurde nun diese Zählersequenz durch die aus Satz 5.1.2 ersetzt.

Im Beweis von Satz 3.2.10 wurde nun eine Grammatik konstruiert, die einen linear beschränkten Automaten simuliert und in der ein beim Richtungswechsel freiwerdendes Gewicht, in einen Stern (⋆) kodiert, nach links wandert, wo es dann verschluckt wird. Aus dieser Grammatik läßt sich nun ganz analog eine Grammatik mit der Zählersequenz aus Satz 5.1.4 statt des Verschluckers konstruieren. Wie für s_{0,1} läßt sich auch hier die so konstruierte Grammatik nach Satz 2.3.7 zu einer der Ordnung 2 umbauen.

Mit dieser Konstruktion läßt sich analog zum Fall für s_{0,1} beweisen:

Satz 5.1.5 : Es gilt:

WGCSL_{1,0} = CSL

Insgesamt gilt also:

Satz 5.1.6 : Sei s eine Stellenbewertung mit Nullstellen. Dann gilt:

WGCSL_{s} = CSL

Beweis: folgt aus den Sätzen 5.1.3, 5.1.5 und 5.1.1 sowie Satz 3.2.11. ♣

5.2 Charakterisierung der exponentiellen Zeithierarchie von CSL

Nachdem wir in den vergangenen Kapiteln verschiedene Stellenbewertungen betrachtet, strukturiert und untersucht haben, wollen wir uns einen Überblick über die bezüglich unterschiedlicher Stellenbewertungen schwach wachsend kontextsensitiven Sprachen verschaffen. In Kapitel 2.1, Bemerkung auf S. 18, haben wir gesehen, daß für alle konstanten Stellenbewertungen C mit wenigstens 2 bewerteten Stellen gilt:

WGCSG_{s} = QGCSG , also WGCSL_{s} = GCSL

In Kapitel 3.2, Satz 3.2.11 haben wir gesehen, daß für alle ungleichmäßigen Stellenbewertungen s gilt:

WGCSL_{s} = CSL

Weiterhin haben wir in Kapitel 5.1 in Satz 5.1.6 gesehen, daß für alle Stellenbewertungen s mit Nullstellen gilt:

WGCSL_{s} = CSL

Für eine beliebige gleichmäßige nichtkonstante Stellenbewertung s haben wir in Kapitel 2.3 gesehen, daß die Klasse der s-schwach wachsend kontextsensitiven Sprachen eigentlich durch den Wachstumsfaktor w(s) charakterisiert wird (S. 27), und in Kapitel 4 in den Sätzen 4.1.6, 4.1.11 und 4.3.2 wurde insgesamt gezeigt:

Satz 5.2.1 : Sei s eine gleichmäßige nichtkonstante Stellenbewertung. Falls w(s) < 1, definiere w := \frac{1}{w(s)}, sonst definiere w := w(s). Es gilt für jedes q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+}, 0 < q < 1:

WGCSL_{w} = WGCSL_{w(s)}

und

T –NSPACE-TIME (n, O (w^{q·n})) ⊆ WGCSL_{w} ⊆ T –NSPACE-TIME (n, O (w^{n}))

Es ist

⋃_{0<q<1} T –NSPACE-TIME (n, O (w^{q·n})) ≠ T –NSPACE-TIME (n, O (w^{n}))

da auf der linken Seite der Rand der Menge auf der rechten Seite fehlt. Es folgt allerdings aus Satz 5.2.1 (also aus den Sätzen 4.1.11 und 4.3.2):

Satz 5.2.2 : Seien v, w ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+} mit v > w > 1. Mit q ∈ Q^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.} ^{+}, \frac{log(w)}{log(v)} < q < 1 folgt:

WGCSL_{w} ⊆ T –NSPACE-TIME (n, O (w^{n})) ⊆ T –NSPACE-TIME (n, O (v^{q·n})) ⊆ WGCSL_{v}

Graphisch dargestellt ist dies in Abbildung 5.1.

[figure: T –NSPACE-TIME (n, O(v^{n})); für \frac{log(w)}{log(v)} < q < 1; T –NSPACE-TIME (n, O(v^{q·n})); T –NSPACE-TIME (n, O(w^{n})); WGCSL_{v}; WGCSL_{w}]

Abbildung 5.1: Beziehungen für Wachstumsfaktoren v > w > 1

Man kann im Beweis von Satz 4.3.1 statt des verwendeten Exponentialzählers auch den in Beispiel 4.2.5 vorgestellten Polynomialzähler einsetzen, der für jede gleichmäßige streng monoton wachsende Stellenbewertung erklärt ist. Damit folgt (wiederum mit Blick auf Satz 4.1.6):

Satz 5.2.3 : Für jede gleichmäßige nichtkonstante Stellenbewertung s gilt:

T –NSPACE-TIME (n, pol) ⊆ WGCSL_{s}

Damit gelten insgesamt die in Abbildung 5.2 (S. 87) dargestellten Beziehungen, wobei wir den Blick der Übersichtlichkeit wegen auf einige markante Klassen konzentriert haben.

Die schwach wachsend kontextsensitiven Grammatiken bezüglich gleichmäßiger Stellenbewertungen bilden also eine Hierarchie, die die exponentielle Zeithierarchie für linear beschränkte Automaten, und damit die für kontextsensitive Sprachen, charakterisiert.

Des weiteren kann man mit Hilfe der in Kapitel 4.2 vorgestellten Zähler und der Konstruktionsidee aus dem Beweis von Satz 4.3.1 zeigen, daß gilt:

Satz 5.2.4 : Sei s eine gleichmäßige nichtkonstante Stellenbewertung. Der Abschluß von WGCSL_{s} unter inversen Homomorphismen [ k-beschränkten Homomorphismen] ist CSL .

Beweisidee:

Sei L ∈ CSL , und sei M ein linear beschränkter Automat, der L in der Zeit t · 2^{c·n} erkennt. Sei Σ das Eingabealphabet.

Konstruiere analog zum Beweis von Satz 4.3.1 eine s-schwach wachsend kontextsensitive Grammatik G, die M simuliert und eine Zählersequenz wie ebendort realisiert.

5.2  Charakterisierung der exponentiellen Zeithierarchie von CSL  87

[figure: .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; CSL = WGCSL_{s} , s unglm Stellenbew oder; Stellenbew mit Nullst; T –NSPACE-TIME (n, O(2^{k·n})); WGCSL_{2^{k}} = WGCSL_{\frac{1}{2^{k}}}; T –NSPACE-TIME (n, O(2^{q·k·n})); für \frac{k−1}{k} < q < 1; T –NSPACE-TIME (n, O(2^{(k−1)·n})); WGCSL_{2^{k−1}} = WGCSL_{\frac{1}{2^{k−1}}}; WGCSL_{2^{2}} = WGCSL_{\frac{1}{4}}; WGCSL_{2} = WGCSL_{\frac{1}{2}}; WGCSL_{2,3}; WGCSL_{3,4}; T –NSPACE-TIME (n, O(2^{2·n})); T –NSPACE-TIME (n, O(2^{q·2·n})); für \frac{1}{2} < q < 1; T –NSPACE-TIME (n, O(2^{n})); T –NSPACE-TIME (n, O(2^{q·n})); für 0 < q < 1; WGCSL_{j,j+1}; T –NSPACE-TIME (n, pol); GCSL = WGCSL_{C}, C konst Stellenbew]

Abbildung 5.2: Die exponentielle Zeithierarchie von CSL und die Hierarche der schwach wachsend kontextsensitiven Sprachen Für ein Eingabewort der Länge n hat diese Zählersequenz für einen Index m ≥ \frac{l·c}{log(w(s)−1)} · n,

wobei l so gewählt wird, daß w(s)^{l} ≥ 3, und wieder r = t·(w(s)^{l} − 1) gesetzt wird, wenigstens die Kapazität

K_{Z}(m) ≥ r · (w(s)^{l} − 1)^{⌊^{\frac{m}{l}}⌋} ≥ t · (w(s)^{l} − 1) · (w(s)^{l} − 1)^{⌊\frac{l·c}{l·log(w(s)^{l}−1)} ·n⌋}
≥ t · 2^{log(w(s)^{l}−1)·⌈\frac{c}{log(w(s)^{l}−1)} ·n⌉} ≥ t · 2^{c·n}

das heißt, M wird, falls sie das Eingabewort akzeptiert, bis zum Schluß simuliert.

Analog zur Expansion der Tupel auf Teilwörter im Beweis von Satz 4.3.1 wird nun jedes

Eingabezeichen a ∈ Σ von M zu a⋄^{⌈\frac{l·c}{log(w(s)^{l}−1)}⌉} expandiert.

Definiere nun einen Homomorphismus h: Σ^{∗} → (Σ ∪ \{⋄\})^{∗} durch h(a) = a⋄^{⌈\frac{l·c}{log(w(s)^{l}−1)}⌉} für alle a ∈ Σ.

[ einen Homorphismus h: (Σ ∪ {⋄})^{∗} → Σ^{∗} durch h(a) = a für alle a ∈ Σ, h(⋄) = ε. ]

Dann ist h(L) = L(G).

[ Dann ist h k-beschränkt für L(G) und h(L(G)) = L mit k = ⌈\frac{l·c}{log(w(s)^{l}−1)}⌉. ]

Dabei ist es wichtig zu beachten, daß s nichtkonstant ist, nicht nur, weil die angesprochene Zählersequenz sonst nicht erklärt ist, sondern weil GCSL abgeschlossen unter inversen Homomorphismen ist [BL92] (und damit auch unter k-beschränkten Homomorphismen, [GGH69]).

Es ergeben sich also folgende Zusammenhänge für den Abschluß von WGCSL_{s} unter inversen Homomorphismen für gleichmäßige Stellenbewertungen s, die Überführbarkeit einer beliebigen Grammatik aus WGCSG_{s} in Cremers-Normalform für ungleichmäßige Stellenbewertung s und die exponentielle Zeithierarchie von CSL :

Satz 5.2.5 : Sei w > 1, sei s eine gleichmäßige Stellenbewertung mit w(s) = w. Folgende Aussagen sind äquivalent:

a) WGCSL_{w} = CSL

b) WGCSL_{w} ist abgeschlossen unter inversen Homomorphismen

c) Für alle ungleichmäßigen Stellenbewertungen s̃ gilt:

(∗) Zu jeder Grammatik G ∈ WGCSGs̃ existiert eine Grammatik G′ ∈ WGCSG_{s} mit L(G′) = L(G) in Cremers-Normalform

d) Für eine ungleichmäßige Stellenbewertung s̃ gilt (∗).

Außerdem folgt aus a):

e) T –NSPACE-TIME (n, O(w^{n})) = T –NSPACE (n)

und daraus folgt:

f) WGCSL_{v} = CSL für alle v > w Beweis:

a) ⇔ b) : folgt aus Satz 5.2.4

a) ⇒ c) : folgt aus Satz 3.2.11 und Satz 2.3.6

c) ⇒ d) : ist trivial

d) ⇒ a) : folgt aus Satz 3.2.11

a) ⇒ e) : folgt aus Satz 4.1.11 und Satz 3.1.3

e) ⇒ f) : folgt aus Satz 5.2.2

♣

5.3 Kontextsensitiv versus Nichtverkürzend

In Kapitel 1.1 wurde kurz gestreift, daß kontextsensitive Grammatiken üblicherweise definiert werden durch:

Definition 5.3.1 : Eine Grammatik G = ⟨N, T, S, P ⟩ heißt kontextsensitiv, falls für jede Regel (α → β) ⊂ P gilt:

α = wXz, β = wY Z mit w, y, z ∈ (N ∪ T)^{∗}, X ∈ N, y ≠ ε

oder (α → β) = (S → ε), und falls (S → ε) ∈ P, so taucht S in keiner Regel aus P auf der rechten Seite auf.

Wenn man diese Definition der von schwach wachsend kontextsensitiven Grammatiken zugrunde legt, hat das zur Folge, daß man Sprachen aus GCSL erhält. Anders ausgedrückt:

Satz 5.3.2 : Sei s eine Stellenbewertung. Sei G = ⟨N, T, S, P ⟩ gemäß Definition 5.3.1 kontextsensitiv. Dann gilt: Erfüllt G die Bedingungen (ii) und (iii) aud Definition 1.1.4, so folgt L(G) ∈ GCSL .

Beweisidee:

Ohne Beschränkung der Allgemeinheit kommen Terminale in den Regeln aus P nur in Regeln der Form A → a, A ∈ N, a ∈ T vor (Terminalregeln). (Falls s auf einem Anfangsstück konstant 0 ist, wandle G nach dem Algorithmus aus Satz 2.1.1 um und wende nach der unten beschriebenen Konstruktion Satz 2.1.2 an.) Sei f eine Zeichenbewertung für G. Konstruiere eine Grammatik G′ = ⟨N′, T, S, P′⟩ durch:

N′ = N ∪ N′ mit N′ = \{[\begin{matrix}X \\ • \end{matrix}]| X ∈ N\} bestehend aus Kopien der Zeichen aus N,

und P′ konstruiere durch:

1. Wiederhole für jedes (α → β) ∈ P mit α = wXz, β = wyz, w, y, z ∈ (N ∪ T)^{∗}, X ∈ N, y ≠ ε:

• Falls y ∈ N, übernehme (α → β) in P′.

• Falls |y| > 1, so hänge an das letzte Zeichen von y ein kodiertes Gewicht (•) an (analog zum Beweis von Satz 4.1.6) und übernehme die so kopierte Regel in P′.

2. Füge nun zu P′ von jeder Regel aus P′ außer Terminalregeln alle möglichen Kopien hinzu, in denen solche kodierten Gewichte beim veränderten Zeichen auf ihrer Stelle, bei den unveränderten Zeichen an diesen hängen bleiben.

3. Füge für jede Terminalregel A → a aus P die Regel [\begin{matrix}A \\ • \end{matrix}]→ a zu P′ hinzu.

Analog zum Beweis von Satz 4.1.6 folgt dann L(G′) = L(G).

Mit f′: N′ ∪ T → IN definiert durch

f′(X) = f(X) für alle X ∈ N
f′([\begin{matrix}X \\ • \end{matrix}]) = f(X) + m für alle X ∈ N
f(x) = max{f′(X) | X ∈ N} + m + 1

wobei

m := max{f(X) | X ∈ N} · max{s(i) | 1 ≤ i ≤ ord(G)} · ord(G)

sieht man G′ ∈ QGCSG , und damit folgt die Behauptung.

5.4 Offene Fragen

Für interessant halten wir die Frage, ob die exponentielle Zeithierarchie für linear beschränkte Automaten kollabiert.

Dazu wäre interessant, folgendes zu beantworten:

• Gibt es für jede s-schwach wachsend kontextsensitive Grammatik bezüglich einer ungleichmäßigen Stellenbewertung eine äquivalente in Cremers-Normalform?

• Gibt es eine gleichmäßige Stellenbewertung s, für die WGCSL_{s} abgeschlossen unter inversen Homomorphismen ist?

(nach Satz 5.2.5 sind diese Fragen äquivalent)

oder wenigstens

Gilt WGCSL_{w} = T –NSPACE-TIME (n, O(w^{n})) ?

Danksagung

An dieser Stelle möchte ich all denen danken, die durch Ermutigung, Diskussion und/oder Wegweisung zum Gelingen dieser Arbeit beigetragen haben.

Insbesondere möchte ich Gerhard Buntrock für die intensive Betreuung danken. Durch seine Einsatzfreude und seinen Ideenreichtum hat er mich immer wieder herausgefordert und einigen Erkenntnissen auf die Beine geholfen. In fruchtbaren Diskussionen ist das Gedankengebäude, das hinter dieser Arbeit steht, gewachsen und immer wieder verbessert worden. Durch seine zeitintensive und gründliche Durchsicht verschiedenster Versionen des Manuskriptes hat er nicht nur einigen Beweisen zu mehr Klarheit und einigen Aspekten zu mehr Betrachtung verholfen, sondern auch der deutschen Rechtschreibung und Orthographie zu vermehrter Berücksichtigung.

Ebenso möchte ich Klaus Wagner danken, der durch sein reges Interesse, seinen beweglichen Geist sowie durch seine ehrliche Hingabe an den Beruf eines Forschungs- und Lehrteamleiters eine angenehme und fruchtbare Arbeitsatmosphäre schafft. Durch seine kontinuierlichen Fragen, insbesondere nach den Nullstellen von Stellenbewertungen, und seinen Sinn für Präzision trug er maßgeblich zur Abrundung der Arbeit bei.

Auch danke ich Diana Rooß für die Geduld, mit der sie der Einleitung und der Zusammenfassung einigen Schliff gab, sowie für ihre Offenheit und Bereitschaft zur Diskussion. Ebenso danke ich Heribert Vollmer, der in seinem Streben nach einfacher Klarheit und Genauigkeit sowie ästhetischer Schönheit einer Arbeit mein (bisher unerreichtes) Vorbild wurde, Herbert Baier, dem ich den Entwurf der Kopfzeile der Seiten dieser Arbeit verdanke, und Ulrich Hertrampf, der durch seine Diskussionsbereitschaft und Freude an konstruktiver Kritik immer wieder anspornt und herausfordert, sowie Carmen Schwenkel, die durch fruchtbare Zusammenarbeit gerade in der Einarbeitungsphase, durch zahlreiche Anregungen und der Herausforderung durch ihre eigene Arbeit sowie die darin offen gebliebenen Fragen meiner Arbeit auf den Weg half und ihr die Richtung wies.

Schließlich möchte ich all denen danken, die durch Ermutigung und Gebet mir immer wieder auf die Beine geholfen haben. Eva Kix verdanke ich zahlreiche klärende Gespräche und Gebetsabende. Ihr, ihrem Mann Joachim Kix, Astrid Boots, Norbert und Beate Hemrich, Barbara Linhardt, Andrea Mager, Mathias (†) und Nadine Meynen sowie Else Woltemate danke ich für die Gemeinschaft und das tragende Netz, durch das wir einander durch Gottes Gnade stützen und beistehen dürfen.

Ebenso danke ich Siegfried Pihan, der in Geduld immer wieder versucht hat, mich aufzurichten. Außerdem hat er durch seine Durchsicht der Einleitung und seine Geduld beim Anhören stets neuer Beweisentwürfe, obwohl er fachfremd ist, sehr zur Entwicklung dieser Arbeit beigetragen.

Desweiteren danke ich meinen Eltern Brigitte Meinecke-Niemann und Bernhard Niemann, die trotz aller Schwierigkeiten mir durch diese Zeit der Entwicklung hindurchhalfen und trotz Fachfremdheit viel Verständnis für meine Arbeit aufbringen, und meinen Schwestern Eilika und Solveig, die durch ihre lockere und liebevolle Kritik sowie zahlreiche Spaßereien mein Leben bereichern.

Vor allem danke ich unserem Herrn Jesus Christus, durch den ich lebe, von dem ich lerne, der mich trägt, in dem ich Ruhe finde und der mir Kraft gibt. Nicht nur zeigt er überaus große Geduld dabei, mir immer wieder zu zeigen, wie Leben aussehen kann, wenn man es aus seiner Hand empfängt, sondern er ist auch der beste Informatiker, den es gibt, und ich glaube, es macht ihm Spaß, zusammen mit einem Kind Gottes solch ein Gedankengebäude zu bauen und zu erforschen. Ich danke ihm für seine Geduld mit mir, seine Gnade und seine Vergebung. Ohne ihn wäre nicht nur diese Arbeit nicht (oder zumindest nicht so) zustande gekommen, sondern mein Leben wäre weiterhin ein Trümmerhaufen ohne Hoffnung wie das vieler Menschen, die ihn nicht kennen. Auch wenn es nicht leicht ist, ein Leben mit ihm zu lernen, möchte ich lieber das, als so zu leben wie zu der Zeit, als ich ihn noch gar nicht kannte.

Wer Jesus Christus, den wahren Menschen und wahren Gott, Friedefürst, wunderbaren Ratgeber, Erlöser, Überwinder der Sünde und des Todes, Ewigvater und König, kennenlernen möchte, der lese z.B. das Evangelium nach Johannes und/oder bitte ihn selbst um seine Bekanntschaft. Denn wer da bittet, der empfängt; und wer da sucht, der findet; und wer da anklopft, dem wird aufgetan. (Mat 7,8 und Luk 11,10, Luther-Übers., rev. 1984)

Literaturverzeichnis

[BL92] Gerhard Buntrock und Krzysztof Loryś, On growing context-sensitive languages, 19th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 623, S. 77-88, Springer-Verlag, 1992

[BL94] Gerhard Buntrock and Krzysztof Loryś. The variable membership problem: Succinctness versus complexity, 11th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Band 775, S. 595–606, Springer-Verlag, 1994

[BO93] Ronald V. Book und Friedrich Otto, String Rewriting Systems, Texts and Monographs in Computer Science, Springer-Verlag, 1993

[Boo69] Ronald V. Book, Grammars with Time Functions, Dissertation, Harvard University, Cambridge, Massachusetts, Februar 1969

[Bun93] Gerhard Buntrock, Growing context-sensitive languages and automata, TR 69, Universität Würzburg, September 1993

[Bur93] Hans-Jörg Burtschick, mündliche Kommunikation, 19.8.93

[Cho59] Noam Chomsky, On Certain Formal Properties of Grammars, Information & Control 2, S. 137-167, 1959

[Cre73] A.B. Cremers, Normal Forms for Context-sensitive Grammars, Acta Informatica, 3:59–73, 1973

[DW86] Elias Dahlhaus und Manfred K. Warmuth, Membership for growing contextsensitive 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

[Gla64] A.W. Gladkij, Über die Komplexität der Ableitung in kontextsensitiven Grammatiken, auf Russisch, Algebri i Logika Sem., 3:29-44, 1964

[Har78] Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978

[HU79] John E. Hopcroft, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979

[Jan88] Matthias Jantzen, Confluent String Rewriting, EATCS Monographs on Theoretical Computer Science, Springer-Verlag, 1988

[Jan92] Matthias Jantzen, A remark on increasing grammars and intersection with regular sets, Unveröffentlichtes Manuskript, 1979 [Knu76] Donald E. Knuth, Big Omicron and Big Omega and Big Theta, SIGACT-News,

Apr.–Juni 1976

[Ku64] S.-Y. Kuroda, Classes of Languages and Linear-Bounded Automata, Information & Control 7, S. 207-223, 1964

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

[Lo70] J. Loecks, The parsing of general phrase structure grammars, Information and Control, 16 (1970), S. 207–223

[Ni92] Gundula Niemann, Die Länge von wachsenden Grammatiken, die aus quasi wachsenden erzeugt werden, Studienarbeit, Universität Würzburg, Dez. 1992

[Nie] Gundula Niemann, Arbeit in Vorbereitung

[Sal78] Arto K. Salomaa, Formale Sprachen, Springer-Verlag, 1978

[Sw92] Carmen Schwenkel, Einige komplexitätstheoretische Untersuchungen kontextsensitiver Grammatiken mit Bewertungsfunktionen, Studienarbeit, Universität Würzburg, Juni 1992

[Sw93] Carmen Schwenkel, Eigenschaften schwach wachsend kontexsensitiver Sprachen, Diplomarbeit, Universität Würzburg, August 1993

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

[Tur36] Alan M. Turing, On Computable Numbers, with an Application to the Entscheidungsproblem, Proc., London Math. Soc. 42, S. 230-265, 1936

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