Hallo zusammen, guten Morgen.
Wir haben ja am Dienstag mit einem neuen Kapitel angefangen, dem
Kapitel Grammatiken und das Kapitel wird uns jetzt noch eine Weile
beschäftigen, zur Erinnerung, was wir am Dienstag besprochen haben.
Wir haben uns überlegt, was Grammatiken sind und dann die sogenannte
Chomsky - Hierarchie kennengelernt oder eingeführt, die sozusagen eine
Hierarchie gibt von Sprachklassen in Abhängigkeit dazu, welche
Restriktionen wir für die Regeln der entsprechenden Grammatik
festlegen.
In dieser Hierarchie ist sozusagen das Allgemeinste, dass man gar
keine Restriktionen, gar keine Einschränkungen festlegt.
Die entsprechende Grammatik, Grammatiken heißen Typ 0 Grammatiken und
dann haben wir peu à peu sozusagen das Aussehen der Regeln, wie die
Regeln aussehen dürfen, festgelegt und kamen dann auf die Typ 1
Grammatiken oder kontextsensitiven Grammatiken, Typ 2 kontextfreie
Grammatiken, Typ 3 rechtslineare Grammatiken.
Und dann haben wir uns diese Grammatiken der Reihe nach angeschaut
unter dem Blickwinkel, wie komplex ist es denn für eine Sprache, die
mit einer entsprechenden Grammatik erzeugt werden kann, das
Wortproblem zu entscheiden, die Sprache zu entscheiden.
Bei Typ 0 kam raus, dass es verdammt komplex in der Klasse der
Sprachen, die durch Typ 0 Grammatiken erzeugt werden können, sogar
nicht entscheidbare Sprachen liegen.
Das war sozusagen das Ergebnis dieser ersten Überlegung, bei denen wir
genauer auf die Typ 0 Grammatiken geschaut haben, also Grammatiken, wo
man überhaupt keine Einschränkungen bezüglich dem Aussehen der Regeln
voraussetzt.
Die entsprechende Klasse von Sprachen ist gerade die Klasse der semi
-entscheidbaren Sprachen.
Und wir wissen, es gibt semi-entscheidbare Sprachen, die nicht
entscheidbar sind.
Also Typ 0 Grammatiken sind sicher nicht geeignet, zum Beispiel als
Grundlage für Programmiersprachen.
Typ 1 Grammatiken, die sind ja schon deutlich eingeschränkt im
Vergleich zu, keine Einschränkungen.
Bei Typ 1 Grammatiken haben wir festgestellt, dass auch in der
entsprechenden Sprachklasse sehr komplexe Sprachen liegen können,
nämlich NP-vollständige Sprachen.
Die Sprache zum Klickproblem ist in der Klasse der kontextsensitiven
Sprachen und wir wissen, das Klickproblem ist NP- vollständig.
Wir haben sogar diese Klasse genauer angegeben.
Das ist die Klasse der Sprachen, die mit einer deterministischen
Turing -Maschine mit linearem Speicherplatzbedarf entschieden werden
können.
Dies klingt jetzt erst mal harmlos.
Durch eine deterministische Turing-Maschine mit linearem
Speicherplatzbedarf entschieden werden können, klingt harmlos.
Aber es ist nicht harmlos.
Mit linearem Speicherplatz kann man sehr viel machen.
Was wir an dem Beispiel gesehen haben, dass zum Beispiel das
Klickproblem in diese Sprachklasse reinfällt.
Also Typ 1 Grammatiken sind also anscheinend immer noch nicht
restriktiv genug, dass wir sagen können, die entsprechenden Sprachen
sind etwa als Grundlage für Programmiersprachen geeignet.
Und auf der anderen Seite haben wir ganz unten bei den
eingeschränktesten Grammatiken festgestellt, dass die jetzt wieder zu
restriktiv sind, denn die Typ 3 oder rechtslinearen Grammatiken
erzeugen gerade die regulären Sprachen.
Also die Klasse der Sprachen, die durch Typ 3 Grammatiken erzeugt
werden, ist gleich der Klasse der Sprachen, die von einem endlichen
Automaten akzeptiert werden, ist gleich die Klasse der regulären
Sprachen.
Und wir wissen, dass die in ihrer Ausdrucksfähigkeit sehr
eingeschränkt sind, dass noch nicht mal korrekte Klammerausdrücke in
diese Sprachklassen reinfällt.
Gut, das heißt also, Fazit der letzten Vorlesung war, es lohnt sich,
sich auf die kontextfreien Grammatiken zu konzentrieren.
So, wie sehen die kontextfreien Grammatiken aus?
Nochmal, sie sehen so aus, die Regeln haben nach Definition zunächst
einfach die Formen, links steht eine Variable, rechts ein Wort.
Also keinerlei Einschränkungen bezüglich dem, was hier rechts steht.
Es kann beliebiges Wort sein, gemischtes Wort aus Variablen und
Terminalsymbolen, es kann auch das leere Wort sein, aber links sind
wir sehr speziell, da darf nur eine Variable stehen.
Auf diese Grammatiken oder die entsprechenden Sprachen wollen wir uns
jetzt konzentrieren.
So, das erste Hilfsmittel, das wir kennenlernen im Zusammenhang mit
Produzieren von Worten mit Hilfe einer Grammatik, sind sogenannte
Syntaxbäume.
Syntaxbäume sind eigentlich nur eine Darstellungsmöglichkeit für
Ableitung eines Wortes.
Also ein Wort, eine Sprachklasse lässt sich durch Aneinanderreihung
von Regeln der entsprechenden Grammatik ableiten und Syntaxbäume kann
man benutzen, um so eine Ableitung visuell darzustellen.
Und zwar hat ein Syntaxbäum an der Wurzel die Variable, die dem
Dachsymbol entspricht, jeder innere Knoten entspricht irgendeiner
Variablen und die Blätter entsprechen gerade Symbolen aus Sigma oder
eben dem leeren Wort.
Und wenn ein innerer Knoten, also Variable A, als Nachfolger von links
nach rechts, Alpha 1 bis Alpha r, jeweils Symbole aus V vereinigt
Sigma hat, so muss eben diese Ableitungsregel A nach dem Wort Alpha 1
bis Alpha r in der Grammatik sein.
Das ist sozusagen die Beschreibung eines Syntaxbäumes.
Wir schauen uns das jetzt mal ein Beispiel an.
Folgende Grammatik hatten wir schon das letzte Mal betrachtet.
Die Grammatik mit den Regeln s kann abgeleitet werden in einem Schritt
zu 0b oder zu 1a, a kann abgeleitet werden in einem Schritt zu 0 oder
zu 0s oder zu 1aa und b kann abgeleitet werden völlig symmetrisch
sozusagen zu den drei Ableitungsregeln für a zu 1, 1s, 0bb.
Erinnern Sie sich, diese Grammatik erzeugt die Sprache aller Wörter,
bei denen die Anzahl der Nullen gleich die Anzahl der Einsen ist.
Das hatten wir uns das letzte Mal klar gemacht.
Wenn man da jetzt eine bestimmte Ableitung betrachtet, eine Ableitung
für ein Wort, hier für das Wort 1 1 0 0 1 0 und sieht die so aus, s
nach 1a und weiter Ableitung nach 1 1 a a, indem man a ersetzt durch 1
aa, dann weiter zu 1 1 a 0, indem man das hintere a ersetzt durch 0,
Anwendung der Regel a nach 0, dann weiter zu 1 1 0 s 0, indem man a
ersetzt durch 0s, also die Regel a nach 0s anwendet, dann weiter zu 1
1 0 0 b 0 und dann weiter zu 1 1 0 0 1 0.
Der entsprechende Syntaxbaum sieht folgendermaßen aus.
Wir malen einfach hin, was hier in der Ableitung passiert, beginnend
von der Startvariable s, sozusagen als Wurzel des Baumes.
Hier wird s abgeleitet zu 1a, das heißt also für 1 brauchen wir ein
Blatt.
In einem Syntaxbaum sollen ja die Symbole aus Sigma, die entstehen,
durch Blätter symbolisiert oder repräsentiert werden und für a
brauchen wir einen inneren Knoten, also wir führen ein die Wurzel s
und dann linkes Kind 1, rechtes Kind a.
Das nächste, was passiert hier ist, dass a ersetzt wird durch 1a a,
das heißt also im Baum führen wir von links nach rechts Kinder 1, a
und a ein für den inneren Knoten a.
Dann geht es weiter, indem das hintere a abgeleitet wird zu 0, das
heißt also hier bei den Kindern von diesem a wird das rechteste Kind
a, bekommt das rechteste Kind a ein Kind 0.
Das muss natürlich auch ein Blatt sein, weil von da aus geht es nicht
weiter.
Dann ging es weiter mit, dieses mittlere a wird durch 0s, das heißt
also das mittlere Kind a hier im Baum bekommt die Kinder von links
nach rechts 0s, dann wird s ersetzt durch 0b, das heißt also hier
diese Knoten s bekommt die Kinder 0b von links nach rechts und dann
wird b ersetzt durch 1, also unter b hängen wir das Blatt 1.
Es ist klar, dass in dem Baum die Reihenfolge der Kinder natürlich
relevant ist.
Wie wir von dieser Ableitung zu dem Baum kommen, das ist ein
eindeutiger Weg.
Der Baum zur Ableitung ist eindeutig.
Zu jeder Ableitung gehört genau ein Syntaxbaum.
Jetzt kann man sich natürlich auch umgekehrt fragen, wenn ich nur
diesen Baum kenne, komme ich dann automatisch auf diese eine
Ableitung, wie ich vorher betrachtet habe, oder könnte ich durch
Betrachten dieses Baumes auch auf andere Ableitungen kommen, bei denen
es genauso wäre, wenn ich die Ableitung dann umgekehrt wieder in den
Syntaxbaum überführe, komme ich gerade zu diesem Syntaxbaum.
Man kann sich leicht überlegen, dass man zu so einem Syntaxbaum
durchaus verschiedene Ableitungen haben kann.
Verschiedene Ableitungen natürlich desselben Wortes, das ist klar.
Also dieser Syntaxbaum gehört insbesondere zu dem Wort, wir lesen
einfach die Blätter von links nach rechts, 1 1 0 0 0 0, hier 1, ich
habe mich versprochen, 1 1 0 0 1 0.
Aber vielleicht gibt es ja auch eine andere Ableitung, die denselben
Syntaxbaum hat, eine andere Ableitung zu demselben Wort.
Das kann es geben, das sieht man an dem Beispiel.
Hier haben wir zwei Ableitungen, dasselben Wort, das Wort ist 1 1 0 0
1 0, die beide, wenn man von der Ableitung einfach den Syntaxbaum dann
konstruiert, zu demselben Baum führen.
Also gucken wir uns das nochmal an hier, die erste Ableitung ist S
nach 1 A, weiter nach 1 1 A A und so weiter.
Dazu den Syntaxbaum aufbauen, dann bekommen wir eben hier die Kinder 1
A zu S und dann für die nächste Ableitung, da wird ja dieses A ersetzt
durch 1 A A, das heißt also A bekommt die Kinder 1 A A.
Dann wird hier das mittlere A ersetzt durch 0 S, das heißt für dieses
mittlere Kind A ersetzen wir, fügen wir die Kinder 0 S ein.
Dann geht es so weiter, dass dieses S ersetzt wird durch 0 B, das
heißt also dieses Kind S wird ersetzt durch 0 B und dann wird das B
ersetzt durch 1 und dann wird dieses hintere A ersetzt durch 0.
Also man kommt genau zum selben Baum, obwohl diese Ableitung jetzt
etwas anders ist als die Ableitung, die wir auf der Folie davor
angesehen haben.
Das ist, wenn ich mich nicht irre, auch genau die Ableitung, die hier
drunter steht, die wir auch schon vorher angeguckt haben.
Es ist offensichtlich, warum wir hier zwei verschiedene Ableitungen
für dasselbe Wort haben, die zum selben Wort gehören, weil wir
bestimmte jetzt bei dieser Grammatik für dieses Wort verschiedene
Möglichkeiten haben in der Reihenfolge, wie Regeln angewendet werden.
Es ist auch klar bei kontextfreien Sprachen, dass die Reihenfolge, in
der Regeln angewendet werden, völlig irrelevant ist.
Das ist eben wegen der Kontextfreiheit so.
Wir können immer nur eine Variable zu irgendwas ableiten und wenn Sie
jetzt ein Wort produziert haben, in dem Terminalsymbole und Variablen
irgendwo drinnen stehen, ob Sie dann erst eine hintere Variable weiter
ableiten oder eine, die weiter vorne steht, also in welcher
Reihenfolge Sie das machen, das ist völlig irrelevant.
Da kommt immer dasselbe raus.
So, jetzt kann man natürlich sagen, na ja gut, dann will ich mich
darauf festlegen, das immer schön systematisch zu machen, also sagen
wir mal von links nach rechts oder von rechts nach links.
Und dementsprechend kann man sich festlegen, wir schauen immer
Linksableitungen an.
Eine Linksableitung ist eine Ableitung, bei der in jedem Schritt die
linkeste Variable abgeleitet wird.
Das kann man machen.
So, jetzt Eindeutigkeit.
Also wir haben gesagt,
zu einem Syntaxbaum können verschiedene Ableitungen gehören, aber
eigentlich ist das ja noch nicht so schlimm.
Ein Syntaxbaum gehört immer zu einem Wort.
Wenn wir jetzt zu einem Wort verschiedene Syntaxbäume hätten, dann
wird es schon ein bisschen unübersichtlicher und entsprechend nennen
wir eine kontextfreie Grammatik.
Eindeutig, wenn für jedes Wort der Sprache, die durch die Grammatik
erzeugt wird, genau ein Syntaxbaum existiert.
Und dann nennen wir die Sprache oder eine Sprache, eine kontextfreie
Sprache, eindeutig, wenn es eine eindeutige Grammatik zu dieser
Sprache gibt.
Also wir haben eine kontextfreie Sprache, da gibt es eine kontextfreie
Grammatik, wie genau die Worte dieser Sprache produziert, mit der wir
genau die Worte zu dieser Sprache ableiten können.
Aber es ist ja denkbar, dass es mehr als eine kontextfreie Grammatik
gibt zu der Sprache.
Also das kann man sich leicht überlegen, dass also beim Aufstellen der
Regeln, die man braucht, um Wörter einer vorgegebenen kontextfreien
Sprache zu erzeugen, wir durchaus Freiheiten haben.
Wenn aber unter diesen Grammatiken, diesen kontextfreien Grammatiken,
die es zur kontextfreien Sprache gibt, eine ist, die eindeutig ist,
also die diese schöne Eigenschaft hat, zu jedem Wort haben wir genau
einen Syntaxbaum, dann heißt die Sprache eindeutig, ansonsten inhärent
mehrdeutig.
Inhärent mehrdeutig, also zu der Sprache, egal welche Grammatik ich
jetzt aufstelle zu dieser kontextfreien Sprache, wenn ich dann zu den
Worten der Sprache gehe, kann es sein, dass es verschiedene
Syntaxbäume gibt zu dem Wort.
Das nur am Rande erkennt, ist jetzt für das, was wir im folgenden
machen, nicht ganz so wichtig.
Sie wissen, die Sprache 0 hoch n, 1 hoch n ist kontextfrei.
Wir haben auch eine entsprechende Grammatik angeschaut, nämlich diese
hier, kann sich vielleicht auch andere überlegen, das ist jetzt nicht
der Punkt, aber diese hier, die nur die Regeln hat, S nach 0, 1 und S
nach 0, 1, 0, S, 1, also S nach 0, 1 und S nach 0, S, 1, die ist
eindeutig.
Die Grammatik ist eindeutig.
Wenn Sie jetzt für ein festes n das Wort 0 hoch n, 1 hoch n
produzieren wollen, haben Sie nur einen Weg, wie das geht.
Das ist sehr, sehr eindeutig, nämlich Sie wenden die Regel aus R, S
nach 0, S, 1, n-1 mal an und dann ganz am Schluss wenden Sie die Regel
für dieses mittlere S, S nach 0, 1 an.
So bekommen Sie 0 hoch n, 1 hoch n und dann gibt es auch keine andere
Möglichkeit, zu 0 hoch n, 1 hoch n zu kommen.
Das heißt also, das ist eine eindeutige Sprache, während die Sprache
der Wörter, wo die Anzahl der Nullen gleich Anzahl der Einsen ist,
nicht eindeutig ist.
Da können Sie jetzt schon zu dieser Grammatik, die wir kennen,
verschiedene Syntaxbäume angeben zu demselben Wort.
Zu dem Wort 1, 1, 0, 0, 1, 0, das wir ja auch vorhin angeguckt haben,
gibt es verschiedene Syntaxbäume.
Der Syntaxbaum, den wir eben hatten, war der hier, der links, aber man
kann sich überlegen, dass man auch Ableitungen für dieses Wort
aufstellen kann, die zu diesem Syntaxbaum führen.
Der ist wirklich anders als der hier.
Da haben einige Knoten andere Nachfolger.
Ab dem Level hier drunter, unter 1, a, a, sieht es halt einfach anders
aus.
Das nur am Rande, das ist im Moment nicht so wichtig.
Was jetzt für uns wieder interessant ist, wenn wir uns auf
kontextfreie Sprachen
konzentrieren, ist die Frage, wie komplex ist denn das Wortproblem.
Das war ja das, was wir bei den Typ 0, Typ 1, Typ 3 Grammatiken uns
genauer angeguckt haben und wo wir festgestellt haben, also bei Typ 0,
bei Typ 1 ist das Wortproblem möglicherweise nicht mal berechenbar bei
Typ 0 oder bei Typ 1 NP-vollständig und andererseits bei Typ 3 kommen
wir auf eine zu eingeschränkte Sprachklasse.
Wie ist das denn jetzt bei Typ 2?
Also mal erste Überlegung in die Richtung, wie komplex ist denn das
Wortproblem für Typ 2 oder kontextfreie Sprachen.
Ich habe Sie eben darauf aufmerksam gemacht, dass die Regeln einer
kontextfreien Grammatik schon eine sehr allgemeine Form haben dürfen.
Die Einschränkung bezieht sich bezüglich dem, was links stehen darf,
da muss immer eine Variable stehen, aber rechts können beliebige
gemischte Worte stehen.
Das ist sehr vielfältig.
Um mit so einer Grammatik, mit einer kontextfreien Grammatik arbeiten
zu können und auch dann vielleicht über kontextfreie Grammatiken etwas
beweisen zu können, wie zum Beispiel etwas über die Komplexität des
Wortproblems.
Es ist ganz nützlich, wenn man das Aussehen der Regeln einschränken
kann, ohne die Sprachklasse, die entsprechende Sprachklasse
einzuschränken.
Bei kontextfreien Sprachen geht das oder bei kontextfreien
Grammatiken, wie wir gleich sehen werden.
Eine kontextfreie Grammatik nennt man Grammatik in Homski-Normalform,
wenn die Regeln folgende sehr eingeschränkte Form haben.
Entweder steht auf der rechten Seite ein Wort bestehend aus zwei
Variablen oder auf der rechten Seite steht nur ein Terminalsymbol.
An der linken Seite eine Variable ist ja sowieso klar bei
kontextfreien Grammatiken, so müssen die aussehen, aber auf der
rechten Seite könnte ja viel Allgemeineres stehen, als bei Homski
-Normalform zu sagen, rechts dürfen nur entweder zwei Variablen stehen
oder ein Terminalsymbol, das sieht nach einer starken Einschränkung
aus.
Sie sehen jetzt hier auch, dass man mit solchen Regeln ja noch nicht
mal das leere Wort produzieren könnte.
In kontextfreien Sprachen kann aber das leere Wort drin sein.
Das heißt, da müssen wir uns jetzt noch was überlegen, aber das ist
jetzt mehr technisch.
Das nennen wir also jetzt eine kontextfreie Sprache in Grammatik in
Homski -Normalform und die erste Frage, die wir uns stellen werden,
ist, kann man denn jede kontextfreie Grammatik in diese Form bringen?
Also hier nochmal die Bemerkung dazu, dass wir ja im Allgemeinen bei
kontextfreien Sprachen auch das leere Wort produzieren können müssen,
was hier streng genommen bei Homski-Normalform, also Grammatiken in
Homski -Normalform nicht ginge und deshalb sagt man, naja gut, also um
auch das leere Wort produzieren zu können, erlaubt man noch zusätzlich
eine Regel Startsymbolen nach Epsilon.
Nur Startsymbolen nach Epsilon.
Wenn man jetzt also eine Sprache betrachtet, die kontextfrei ist und
das leere Wort enthält und dazu eine kontextfreie Grammatik hat und
die in Homski-Normalform bringen wollte, was wir gleich probieren
werden, dann müsste man erstmal außen vor lassen, dass das leere Wort
erzeugt werden kann.
Man würde das erstmal sozusagen unterdrücken, die Grammatik in diese
Form bringen und danach sagen, naja gut, aber ich muss auch das leere
Wort erzeugen können.
Dann würde man zusätzlich einführen einfach eine Regel S' nach Epsilon
mit einem neuen Startsymbol S' und dann S' nach S.
Das ist einfach so ein technischer Zusatz.
Okay,
gut.
Und jetzt also der Satz, der uns interessiert.
Jede kontextfreie Grammatik, die nicht das leere Wort erzeugt, kann in
eine Grammatik in Homski-Normalform überführt werden.
Das heißt, wir können wirklich kontextfreie Grammatik, wo die Regeln
sehr allgemeine Form haben können, was das Aussehen der rechten Seite
angeht, in diese sehr eingeschränkte Form bringen, wo auf der rechten
Seite nur entweder zwei Variablen stehen oder ein Terminalsymbol.
Und dass wir jetzt bei dem Satz sagen, jede kontextfreie Grammatik,
die nicht das leere Wort erzeugt, ist einfach, weil wir sozusagen den
Gedanken und kontextfreie Grammatiken, die auch das leere Wort
erzeugen können, mal sozusagen zur Seite schieben, weil streng
genommen die Homski-Normalform halt so definiert ist, dass dabei keine
Möglichkeit besteht, das leere Wort zu erzeugen.
Gut, das ist jetzt ein konstruktiver Beweis, den wir führen.
Wir geben sozusagen eine Schritt-für-Schritt-Überführung der Regeln
unserer beliebigen kontextfreien Grammatik in Regeln in Homski
-Normalform an.
Der Beweis geht jetzt so ein bisschen länger, so technisch, aber nicht
schwierig.
Großbuchstaben sollen wie bisher auch immer Variablen bzw.
Nicht-Terminalsymbole symbolisieren und Kleinbuchstaben immer
Terminalsymbole.
Und ich sage gleich dazu, bei dem Beispiel, das wir jetzt bei dem
Beweis mitführen, schauen wir tatsächlich ein Beispiel an, bei dem
Regeln existieren, wo rechts das leere Wort, also Epsilon steht, die
sogar so ist, dass die entsprechende Sprache das leere Wort enthält.
Aber da werden wir uns dann ganz am Schluss darum kümmern, sozusagen
wieder zu bereinigen, dass wir vielleicht zwischendurch, um sozusagen
auf Homski-Normalform zu kommen, alle Regeln, Variable wird nach
Epsilon abgeleitet, eliminieren und dadurch auch die Möglichkeit
eliminieren, das leere Wort abzuleiten.
Da kümmern wir uns ganz am Schluss darum.
Brauchen Sie jetzt nicht nervös werden.
Also wir veranschaulichen den Beweis an folgendem Beispiel einer
kontextfreien Grammatik.
Unser Alphabet Sigma besteht aus den Symbolen klein A und klein B.
Unsere Variablenmenge besteht aus den Variablen Groß A, Groß B, Groß
C, Groß D, Groß E, Groß S.
S ist die Startvariable und wir haben folgende Regelmenge.
Eine ganze Menge Regeln.
S kann ersetzt werden durch A, S kann ersetzt werden durch klein A,
Groß A, klein A, durch klein B, Groß B, klein B, durch Epsilon.
A kann ersetzt werden durch Groß C oder durch klein A und so weiter.
Also wir haben hier insbesondere eine ganze Menge Regeln, die bei
einer Grammatik in Homski-Normalform nicht mehr sein dürfen.
Das darf alles nicht sein.
Was nicht sein darf, ist, dass auf der rechten Seite so ein gemischtes
Wort steht.
So ein Wort, bestehend aus Nicht-Terminal- und Terminalsymbolen.
Was nicht sein darf, ist, dass da rechts nur eine Variable steht.
Was nicht sein darf, ist, dass da rechts drei oder mehr Variablen
hintereinander stehen.
Was nicht sein darf, ist, dass da rechts ein Wort über dem Alphabet
steht, das länger als eins ist.
Was darf noch nicht sein, dass wir hier hinten so ein Epsilon haben.
Da sind eine ganze Menge Regeln drin, also so ziemlich alle, fast
alle, die in Homski-Normalform nicht vorkommen dürfen.
Schritt für Schritt versuchen wir die jetzt loszuwerden.
Und der erste Schritt ist,
wir überführen unsere Regeln in Regeln, bei denen auf der rechten
Seite entweder nur Symbole aus V stehen oder nur ein Symbol aus Sigma.
Nur ein Symbol aus Sigma, das ist ja dann schon gut.
Diese Regeln sind dann schon fertig.
Nur Symbole aus V auf der rechten Seite kann immer noch abweichen von
dem, was wir wollen, weil die Worte, die könnten lang sein, länger als
zwei oder nur aus einem Symbol aus V existieren.
Aber hier werden wir los, gemischte Worte und Wörter aus Sigma-Stern,
die länger als eins sind.
Und das Vorgehen ist folgendes.
In allen rechten Seiten ersetzen wir erstmal Symbole aus Sigma durch
Variablen.
Also für jedes A aus Sigma führen wir so eine Variable yA ein und
fügen dann noch Regeln yA nach A ein.
Also wie sieht das hier aus?
Die Regeln, die wir hier loswerden wollen, das sind die, wo auf der
rechten Seite nur Symbole aus V oder Symbole, die wir loswerden
wollen, sind diejenigen, wo auf der rechten Seite gemischte Worte
stehen oder Wörter aus Sigma-Stern, die länger als eins sind.
Das sind hier die rot markierten.
Also hier auf der linken Seite stehen unsere Regeln aus unserer
Grammatik und da wollen wir loswerden.
Die Regel S nach klein A groß A klein A, S nach klein B groß B klein B
und D nach klein AB.
Was machen wir?
Also für klein A führen wir die Variable yA ein, für klein B führen
wir die Variable yB ein und wir ersetzen jetzt einfach überall auf der
rechten Seite klein A durch yA, klein B durch yB und führen dann noch
die Regeln yA nach A, yB nach B ein.
Das war einfach.
Das war jetzt noch nicht schwierig, was wir da gemacht haben.
Es ist klar, dass wenn wir diese Grammatik jetzt in diese überführen
oder diese Regelmenge in diese Regelmenge überführen, werden dieselben
Worte auf die Art produzierbar.
Da ändert sich nichts an dem, was man mit der Grammatik machen kann.
Okay, what's next?
Die rechten Seiten sind noch zu lang.
Vielleicht noch einmal zurück zu dieser Folie.
Die rechten Seiten sind schon für die Regeln gut, wo auf der rechten
Seite ein Symbol aus Sigma steht, weil wenn da ein Symbol aus Sigma
steht, da steht ja auch nur dieses eine Symbol aus Sigma nach dem, was
wir jetzt gemacht haben.
Das heißt also, die rechten Seiten sehen jetzt so aus, entweder steht
da ein Symbol aus Sigma, das ist schon mal gut, kann man schon mal
abhaken, oder stehen da Worte über V-Stern, die aber beliebig lang
sein können.
Wir wollen aber nur Worte der Länge genau zwei.
So, damit konzentrieren wir uns jetzt mal auf die langen, die zu lang
sind.
Sozusagen rechte Seite, Epsilon, das habe ich jetzt sozusagen nicht
mitwiederholt, da kümmern wir uns dann auch noch drum.
Also wir kümmern uns jetzt um die Regeln, wo auf der rechten Seite ein
Wort aus V-Stern steht, das eine Länge hat, die größer als zwei ist.
Also umgekehrt, als Ziel unseres zweiten Schrittes haben wir alle
rechten Seiten haben Länge kleiner gleich zwei.
So, sei also jetzt mal A nach B1 bis Bm so eine Regel, wie noch nicht
diese Bedingung, rechte Seite hat eine Länge kleiner gleich zwei
erfüllt, wissen wir aber insbesondere, da auf der rechten Seite stehen
nur Variablen.
Also es gäbe eine Regel A nach B1 bis Bm und m ist größer zwei.
Diese Regel durch andere Regeln zu ersetzen, die eine gute Form haben,
ist eigentlich auch nicht schwer.
Wir führen m-2, neue Variablen, C1 bis Cm-2 ein und dann statt dieser
Regel A nach B1 bis Bm folgende Regeln.
A nach B1, C1, Ci für i größer gleich eins, kleiner gleich m-3, Ci
nach Bi plus eins, Ci plus eins und dann die letzte sozusagen Cm-2
nach Bm-1, Bm.
Ist klar.
Auf die Art können Sie mit diesen Regeln insgesamt auch A ableiten
nach B1 bis Bm.
Also Sie können all das produzieren, was Sie weiter dann durch
Ableitungen der Bi, die hier rechts stehen, weiter bekommen können.
Nächster Schritt.
Also schauen wir uns das mal einfach ein Beispiel an.
Also welche Regeln haben wir hier, wo die Länge der rechten Seite
größer zwei ist?
Das sind hier wieder die Regeln, wo wir hier rechts die Worte rot in
rot eingefärbt haben.
Also S nach Y A, A Y A bzw.
S nach Y B, B Y B bzw.
C nach C D E.
Für jedes dieser Wörter führen wir jetzt diese zusätzlichen Variablen
ein.
Die nennen wir hier C1, C2, C3 und führen dann die entsprechenden
Regeln ein.
Also für S nach Y A, A Y A kommt die Regel S nach Y A C1, C1 nach A Y
A.
Die beiden Regeln.
Für S nach Y B, B Y B führen wir ein die neue Variable C2 und die
Regel Y B C2, C2 B Y B.
Und für die Regel C nach C D E führen wir die neue Variable C3 ein und
die Regel C nach C C3, C3 D E.
Wohlgemerkt jetzt mit dieser Indizierung der neuen Variablen, das ist
nicht exakt eins zu eins, so wie wir es vorher formal beschrieben
haben.
Denn jetzt haben wir für diese eine Regel hier formal gesagt, da
führen wir entsprechend wie groß dieses M hier ist, also wie lang das
Wort hier rechts ist, neue Variablen C1 bis C M minus 2 ein.
Und wenn man jetzt also mehrere Regeln von dieser Art hat, die rechten
Seiten haben ja nichts miteinander zu tun von diesen verschiedenen
Regeln dieser Art, dann würde man also jeweils neue Variablen E1 bis
B, E S minus 1 für die nächste Regel dieser Art und so weiter
einführen.
Das haben wir jetzt hier nicht gemacht, sondern wir haben einfach die
neuen Variablen C1 bis C3 genannt.
Auch weil diese rechten Seiten ja so lang nicht sind, die sind halt
nur um eins länger als gewünscht.
Nur dass sie da nicht stutzig werden, welche Rolle hier die C1, C2, C3
spielen.
Okay, aber das ist, denke ich, auch einfach zu verstehen, was hier
passiert.
So, jetzt wollen wir die Regeln, wo auf der rechten Seite Epsilon
steht, loswerden.
Von der Sorte haben wir ja in unserer Grammatik auch ein paar.
Und wie gesagt, nicht nervös werden.
Wir werden jetzt, indem wir diese Regeln unterdrücken, auch
unterdrücken, dass unsere Grammatik das leere Wort erzeugen kann.
Und das wäre ja dann nicht mehr dasselbe.
Da kümmern wir uns aber ganz am Schluss dann wieder drum.
Also wir wollen jetzt als Ziel keine Regeln mehr haben der Form A nach
Epsilon.
Wohlgemerkt, solche Regeln könnten sie auch haben in einer Grammatik,
die nicht das leere Wort erzeugen kann.
Kann ja schon sein.
Da können die auch ganz brauchbar sein.
A verschwinden lassen.
So, Vorgehen.
Das Vorgehen besteht aus zwei Phasen.
In der ersten Phase wollen wir all die Variablen finden, die sich
möglicherweise auch durch mehrere Ableitungsschritte ableiten lassen
zum leeren Wort.
Für die müssen wir dann vorsehen, dass dasselbe, was durch Ableiten
dieser Variablen zum leeren Wort passieren kann, innerhalb von einem
Wort, in dem diese Variable vorkommt, dass das auch anderweitig immer
noch machbar ist.
Was heißt das, wenn ich A durch mehrere Regeln ableiten kann zum
leeren Wort?
Das heißt also, in allen Produktionen, wo auf der rechten Seite ein
Wort produziert wird, in dem A vorkommt, kann ich auch das A
verschwinden lassen.
Dann kann ich auch das entsprechende Wort produzieren, wo dieses A
nicht vorkommt.
Das muss sich jetzt ermöglichen für diese Variablen, für die es also
die Produktion A nach Epsilon gibt.
Deshalb will ich in der ersten Phase die erstmal identifizieren und in
der zweiten Phase dann entsprechende Ersetzungen vornehmen.
Also dafür gucken wir, das machen wir sukzessive, gucken wir erstmal
nach, für welche Variablen gibt es denn die Ableitungsregeln,
Variablen nach leerem Wort und dann gucken wir, welche Variablen
lassen sich zu dieser Variablen ableiten und damit im nächsten Schritt
zum leeren Wort und so weiter.
Also, es werden erst alle A mit A nach Epsilon, ist eine Regel, in
diese Menge V' alle Variablen, für die gilt, die lassen sich irgendwie
zu Epsilon ableiten, aufgenommen.
Und dann wird geprüft, ob sozusagen neue Regeln entstehen würden, B
nach Epsilon, wenn man auf der rechten Seite ein A, was wir in dem
Schritt vorher identifiziert haben, einfach durch Epsilon ersetzen
würde.
Wenn wir auf die Art neue Regeln B nach Epsilon bekämen, wird das
entsprechende B auch in V' aufgenommen und so weiter.
Und das machen wir so lange, bis wir nach sozusagen Überprüfung, ob
durch Ersetzen von einem B, das in V' aufgenommen wurde, neu
aufgenommen wurde, durch Epsilon eine neue Regel produzieren würde,
der Form Variable wird abgeleitet nach Epsilon.
Damit hören wir auf, wenn das nicht mehr passiert.
Also das Verführen hört auf, wenn sich V' nicht mehr endet, wenn wir
keine neuen Variablen mehr in V' aufnehmen müssen.
Das heißt also, diese Phase 1 ist nur dafür da, die Variablen zu
identifizieren, die nach V' reingehören.
Also die Variablen, die sich irgendwie ableiten lassen nach Epsilon.
Dass wir dann bei dieser Prozedur immer mal nachgucken und was würde
passieren, wenn ich die entsprechende Variable, die ich gerade in V'
aufgenommen habe, durch Epsilon ersetzen würde auf irgendeiner rechten
Seite.
Das machen wir nicht.
Das ist nur Testweise, um herauszufinden, ob neue Variablen nach V'
reingehören.
Also das ist noch keine Ersetzung, sondern nur eine Phase, in der
dieses V' produziert wird.
Am Ende dieser Phase enthält V' alle Variablen A mit A ableitbar nach
Epsilon insgesamt.
In der zweiten Phase schauen wir uns dieses V' an, streichen erstmal
die ganz normalen Regeln A nach Epsilon, die es für A aus V' gibt und
fügen dafür
zusätzlich ein, wenn es eine Regel A nach B, C, insgesamt für Regeln
der Form A nach B, C, für die gilt C ist in V' oder B ist in V', neue
Regeln A nach B beziehungsweise A nach C ein.
Also wenn wir irgendeine Regel haben, A nach B, C, dann füge eine
zusätzliche Regel A nach B ein, falls C in V' ist, also C sich
ableiten lässt nach Epsilon, beziehungsweise eine neue Regel A nach C,
falls B sich ableiten lässt nach Epsilon.
Klingt sinnvoll.
Und wohlgemerkt, wir brauchen jetzt auch nur solche Regeln A nach B, C
anzugucken, denn wir sind schon soweit, dass die rechten Seiten Länge
kleiner gleich 2 haben.
Also das ist jetzt mal das Erste, was wir machen.
Wir streichen alle, wir gucken die Elemente aus V' der Reihe nach an.
Wenn für entsprechende Variable gilt, es gibt die Regel A nach
Epsilon, dann wird die gestrichen.
Wenn es eine Regel gibt A nach B, C mit C in V', dann wird zusätzlich
eingeführt die Regel A nach B, beziehungsweise wenn B in V' wird
zusätzlich eingeführt die Regel A nach C.
Ruhig gemerkt, A nach B, C bleibt auch drin.
Jetzt gucken wir uns das mal hier an.
Also erstmal, wie kommen wir an das V' ran?
Hier rechts stehen unsere ganzen Regeln, so wie sie jetzt aussehen
nach den vorherigen Ersetzungsschritten.
Und das V', das soll ja alle Variablen enthalten, die irgendwie auch
über mehrere Schritte ableitbar sind nach Epsilon und wir fangen an,
das V' zu produzieren, indem wir erst nach den Regeln gucken, wo eine
Variable direkt nach Epsilon ableitbar ist.
Also es gibt zum Beispiel die Regel S Epsilon, also muss S hier rein
und es gibt hier die Regel C nach Epsilon, also kommt C nach V' rein.
Also die Initialisierung liefert S und C und jetzt müssen wir
nachgucken, ob dadurch, dass wir die entsprechenden Regeln anwenden
würden, noch weitere Regeln der Form Variable wird ersetzt durch
Epsilon entstehen.
Ich muss jetzt gerade mal die Batterien in meinem Zeiger auswechseln.
Bei dieser ersten Überlegung würde jetzt noch A dazukommen.
Warum?
Weil ich
die Regel A nach C habe und die Regel C nach Epsilon in meiner
Originalgrammatik.
Das heißt also, für das C, das ich bei der Initialisierung schon als
Element von V' identifiziert habe, würde Anwenden von C nach Epsilon
auf irgendeine rechte Seite dazu führen, dass ich die Regel A nach
Epsilon bekomme.
Ansonsten würde durch Anwendung C nach Epsilon auf irgendeine rechte
Seite nichts Böses passieren und genauso durch Anwenden S nach Epsilon
würde nichts weiter passieren.
Das heißt also, im ersten Durchlauf bekomme ich A dazu.
S und C muss ich jetzt gar nicht mehr weiter betrachten, aber A.
Ich muss jetzt gucken, ob irgendwo auf der rechten Seite, wo das A
vorkommt, ersetzen dieses A durch Epsilon dazu führt, dass ich eine
Regel bekomme, Variable nach Epsilon.
Ja, A kommt hier auf manchen rechten Seiten alleine vor und das sind
ja die Situationen, die hier relevant sind.
Nämlich hier
kommt es alleine vor, das ergibt aber nichts Neues.
S ist ja schon drin in V'.
Aber hier, bei der Regel D nach A, kommt A rechts alleine vor.
Das heißt, wenn ich A durch Epsilon ersetze, bekomme ich D nach
Epsilon.
Das heißt also, D muss neu reinkommen in V'.
Weiter gucken zeigt uns, dass in diesem zweiten Durchlauf auch keine
weitere Variable in V' reinkommt.
Aber nachdem D jetzt neu reingekommen ist in V', müssen wir
nachgucken, ob Ersetzen von D auf einer rechten Seite durch Epsilon
eine neue Regel Variable nach Epsilon produziert.
Das ist der Fall, nämlich es gibt eine Regel F nach D.
Wenn ich hier D durch Epsilon ersetze, habe ich eine Regel F nach
Epsilon.
Also muss F in V' rein.
So, das war der dritte Durchlauf.
Jetzt müsste ich überall noch auf den rechten Seiten nachgucken.
Wo kommt denn F alleine vor?
Das ist nirgends der Fall.
Das heißt also, es kommen keine neuen Variablen mehr in V' rein.
Das heißt, nach diesem vierten Durchlauf bin ich fertig mit der ersten
Phase.
Ich weiß jetzt also, welches die Variablen sind, die irgendwie durch
einen oder auch mehrere Schritte ableitbar sind nach Epsilon.
Und jetzt streiche ich die Epsilon-Produktion und simuliere
Ableitungen der Art, A lässt sich irgendwie ableiten zu Epsilon auf
die verbleibenden Regeln, wo dieses V gleich A, B, also wo Elemente
aus V' vorkommen.
Dafür gucke ich mir auf der rechten Seite an, wie hier.
Gibt es da in Worten auf der rechten Seite Variablen, die in V' sind?
Und dann führe ich dafür die entsprechenden Regeln ein, die ich
bekäme, wenn ich diese Variable durch Epsilon ersetze.
Und das passiert hier an diesen Stellen.
Wenn ich dieses C durch Epsilon ersetze, bekomme ich als neue Regel C
nach C3.
Wenn ich dieses A durch Epsilon ersetze, bekomme ich als neue Regel C
nach F.
Was noch?
Wenn ich hier dieses A durch Epsilon ersetze, bekomme ich als
zusätzliche neue Regel C1 nach YA und so weiter.
Hier entsteht auch noch eine neue Regel.
Das heißt also, die neuen Regeln, die hinzukommen, sind gerade die, wo
hier die rechte Seite rot ist.
Jetzt habe ich immer noch Regeln, die mir nicht gefallen, nämlich
solche Kettenregeln.
Links steht eine Variable und rechts steht eine Variable, also A nach
C.
Wir wollen ja auf den rechten Seiten nur zwei Regeln mit zwei
Variablen haben.
Das heißt, ich muss jetzt diese Kettenregeln, die sogar teilweise noch
hinzugekommen sind durch den Schritt, ich ersetze die Regeln, wo auf
der rechten Seite Y steht, auch noch loswerden.
Also Ziel für den vierten Schritt ist, die Grammatik enthält keine
Regeln der Form A nach B.
Also solche hier wie A nach B oder A nach C oder B nach C, die will
ich loswerden.
Dafür muss ich natürlich gucken, wo kann mich das hinführen.
Hier zum Beispiel kann mich A nach B und dann B weiter nach C und dann
C weiter nach klein c eben dazu führen, dass ich A nach klein c
ableite.
Und das muss ich auch weiter ermöglichen.
Aber diese Zwischenschritte, die sind ja auch eigentlich ziemlich
überflüssig, die will ich einfach sozusagen einsparen.
Eben die entsprechenden Regeln verlustfrei, sage ich mal, eliminiere.
Das ist jetzt wieder eine Vorgehensweise mit zwei Phasen.
Ich schaue sozusagen an, wo können mich solche Kettenregeln hinführen.
Das kann man sich als einen Graph vorstellen, so einen Ablaufgraph von
A nach B, von B nach C und so weiter.
Und dieser Graph kann jetzt Zykel enthalten, dass ich also über lauter
solche Anwendungen von Kettenregeln wieder am Anfang rauskomme oder
halt einfach so was baumartiges.
Bei so einem Zykel kann ich in nullkommanix sozusagen die Sache
erledigen, indem ich einfach den ganzen Kreis zusammenziehe, so können
Sie sich das bildlich vorstellen, nämlich alle entsprechenden
Variablen, die in dem Zykel vorkommen, die sozusagen immer rechte
Seite einer Kettenregel und dann linke Seite der nächsten Kettenregel
sind, ersetze durch eine dieser Variablen.
Also wenn ich etwa so einen Kreis finde A1 nach A2, A2 nach A3 und so
weiter bis An-1 nach An und dann von An wieder nach A1, kann ich
eigentlich all diese Ai, all diese Variablen, die hier zwischen
vorkommen, durch A1 ersetzen.
Und das zweite ist jetzt, es können natürlich auch andere Konstrukte
entstehen, wenn ich solche Kettenregeln nacheinander angucke und da
muss ich auch systematisch die einzelnen Kettenregeln ersetzen.
Und jetzt muss ich mir nur überlegen, in welcher Reihenfolge, in
welcher Systematik mache ich das am besten.
Das ist jetzt diese zweite Phase.
Ich betrachte also jetzt wieder Regeln der Form A nach B und wohin
mich das führt.
Aber wenn ich jetzt alle Kreise losgeworden bin, dann ist das
sozusagen ein gerichteter kreisfreier Graph, den kann ich topologisch
sortieren und dann gehe ich einfach diese Regeln rückwärts nach dieser
topologischen Sortierung durch und ersetze eine Regel der Form A nach
B.
Für jede Regel, die es gibt, der Form B nach einem Symbol aus Sigma,
durch A nach dem entsprechenden Symbol aus Sigma.
Und das ist ja das, woraus mir ankommt, dass wenn ich von A aus über
Kettenregeln irgendwann mal zu einem Symbol aus Sigma kommen kann,
dass ich das auch nach eliminierende Kettenregeln noch kann.
Das entspricht einfach dem Zusammenziehen dieser ganzen Kette und
ersetzen der entsprechenden Regeln durch A nach dem Terminalsymbol.
Aber das muss ich ein bisschen systematisch machen und das machen wir
eben entsprechend der topologischen Sortierung der entsprechenden
Kettenregeln rückwärts.
Also wie sieht das aus?
Wir gucken uns einfach die Variablen an aus den Kettenregeln und dann
so topologisch sortiert.
Das heißt also, die Variable bekommt Index i, kleiner Index j, wenn
ich von vi nach vj kommen kann durch mehrere Kettenregeln.
Und ich habe jetzt hier schon vorausgesetzt, dass ich die Zykel
entfernt habe.
Gucken wir uns die ganze Sache mal an in unserer Grammatik.
Hier rechts ist die Grammatik.
Jetzt erstmal,
welche Regeln wollen wir alle loswerden?
Alle die, wo wir hier was rot haben.
Also s nach a, a nach c,
c nach f, c nach a, c nach c3 und so weiter.
Außerdem ist relevant, dass am Ende von unseren Kettenregeln zum
Beispiel auch das b steht und das b lässt sich nach klein b ableiten.
Also dass das jetzt hier trotzdem rot ist, ist so ein bisschen
unsystematisch, denn nach demselben Gedanken müsste man auch y a nach
a rot machen.
Ich weiß jetzt auch nicht so genau, warum das in dem einen Fall das b
links hier rot ist und hier das y a nicht rot.
Das werde ich korrigieren.
Aber was wir als erstes feststellen, ist, wir haben einen Kreis.
a nach c, c nach f, f nach d, d nach a.
Dann heißt das, im Prinzip ist das, was wir dann weiter machen können,
von a aus, von c aus, von f aus, von d aus, äquivalent.
Denn wir kommen in dem Kreis immer, wenn wir nach a kommen, dann
kommen wir auch nach f und dann nach d.
Und wenn wir nach d kommen, dann können wir auch nach c.
Das heißt also, die sind irgendwie alle, wenn wir die erreichen
können, ist das, was wir von da aus weiter machen können, für alle
gleich.
Das heißt, die können wir alle ersetzen durch ein und dieselbe
Variable, a in dem Fall, weil hier von oben nach unten das a ist.
Und die entsprechenden Regeln, die dann entstehen würden, die einfach
so aussehen, a nach a, löschen wir.
Das heißt im Prinzip, diesen Kreis ziehen wir zusammen.
Was dadurch entsteht, ist also aus dieser linken Seite diese rechte
Seite, dieser Zyklus, a nach c, nach f, nach d, nach a, wird ersetzt,
indem wir eben überall, wo c, f und d steht, a einfügen und dann die
Regeln a nach a einfach vergessen.
Das heißt also, hier würde auf der rechten Seite c durch a ersetzt,
dann haben wir a nach a produziert, können wir vergessen.
Hier wird das c durch a ersetzt, hier rechts wird das f durch a
ersetzt, nochmal das f durch a ersetzt und nochmal das c durch a
ersetzt.
Alle Regeln, die auf der Art entstehen, der Form a nach a, kann man
vergessen.
Das heißt, was übrig bleibt, ist a nach a, a, a nach a, c, 3.
Hier genauso, das was übrig bleibt, ist a nach b und a nach y, a, y,
b.
Hier genauso, das was übrig bleibt, ist a nach e.
Hier tut sich nichts Neues und hier wird das d durch a ersetzt.
Was übrig bleibt, ist c, 3 nach a, e.
Jetzt haben wir immer noch Kettenregeln, aber die Kettenregeln, die
wir jetzt noch haben, sind nicht in Kreisen.
Die lassen sich typologisch sortieren und das machen wir im nächsten
Schritt.
Diese topologische Sortierung ist einfach hier, diese beiden Graphen
von oben nach unten gelesen.
Und da die beiden, also weil das zwei Komponenten sind, können wir die
irgendwo hintereinander setzen.
Ob man jetzt also die topologische Sortierung s, a, c, 3, e, b, c, 1,
y, a nimmt oder das c, 1, y, a nach vorne setzt, das ist egal.
Das ist also jetzt unsere topologische Sortierung und entsprechend der
topologischen Sortierung gucken wir uns jetzt all diese Kettenregeln
an, aber von hinten nach vorne betrachtet.
Also erstmal c, 1 nach y, a und
dann gibt es y, a nach klein a, also wird c, 1 nach y, a ersetzt durch
c, 1 nach klein a und so weiter.
Das nächste wäre durch b gewesen.
Wir haben eine Kettenregel e nach b und es gibt b nach klein b, also
kriegen wir e nach klein b und so weiter.
Also von hinten nach vorne werden also für die rechten Seiten dieser
Kettenregeln entsprechend der Variablen unserer Sortierung die
Ersetzungen der Variablen durch ein Terminalsymbol eingeführt, wenn
sowas existiert.
Okay, das sieht doch alles sehr gut aus.
Das heißt, wir sind jetzt schließlich bei einer Grammatik angekommen,
wo die rechten Seiten entweder nur Terminalsymbole sind oder aus Nicht
-Terminalsymbolen bestehen und genau Länge 2 haben.
Und jetzt noch, wir haben aber bei der ganzen Aktion die Möglichkeit
verloren, das leere Wort abzuleiten.
In dieser Grammatik gab es die Möglichkeit, schon allein weil es die
Regel s nach y gab, aber es hätte auch sein können, dass wir zwar
nicht die Regel s nach y haben, aber über irgendwelche anderen Regeln,
Variablen nach y vielleicht von s aus y produzierbar wäre.
Und deshalb erweitern wir die Grammatik noch um die Regeln s' nach s
und s' nach y für ein neues Startsymbol s'.
Okay, das war jetzt der erste große Schritt heute.
Jede kontextfreie Grammatik lässt sich in Chomsky-Normalform bringen.
Da machen wir jetzt ab jetzt auch nicht mehr so genau die
Unterscheidung, ob Chomsky-Normalform im strengen Sinne, wo wir also
gar keine Regel der Form haben, auf der rechten Seite steht y, oder
Chomsky -Normalform erweitert um eine Regel Startsymbol nach y für den
Fall, dass die entsprechende kontextfreie Sprache auch das Wort y
enthält.
Am Anfang gesagt, was uns interessiert, ist aber die Komplexität des
Wortproblems für kontextfreie Sprachen.
Und dieser Satz hier, der beantwortet sozusagen die Frage nach der
Komplexität des Wortproblems für kontextfreie Sprachen, der sagt
nämlich, es gibt einen Algorithmus, der für eine kontextfreie
Grammatik g, welche in Chomsky-Normalform vorliegt und ein beliebiges
Wort aus Sigma Stern in Zeit o von Anzahl der Regelmenge mal Länge des
Wortes hoch 3 entscheidet, ob das Wort in der Sprache ist, die von der
Grammatik erzeugt wird.
Und dieser Algorithmus heißt CYK-Algorithmus.
Also die Antwort ist, man kann mit polynomialem Aufwand das
Wortproblem für eine kontextfreie Sprache entscheiden.
Wortprobleme entscheiden heißt, gegeben ein beliebiges Wort über dem
Eingabealphabet kann ich entscheiden, ob das Wort in der Sprache ist
zu einer vorgegebenen Grammatik.
Was will ich jetzt für kontextfreie Grammatiken?
Ich weiß, jede kontextfreie Grammatik kann ich in Chomsky-Normalform
bringen.
Und wenn ich dann weiß, für jede kontextfreie Grammatik in Chomsky
-Normalform gilt, ich kann für ein beliebiges Wort über dem
Eingabealphabet in Polynomialzeit entscheiden, ob das Wort in der
Sprache ist, die durch die Grammatik erzeugt ist.
Dann weiß ich, für kontextfreie Grammatiken kann ich das Wortproblem
in Polynomialzeit entscheiden.
Kurze Überlegung, im Allgemeinen Fall müsste man die Grammatik noch in
Chomsky -Normalform bringen, aber das haben wir gerade gesehen, das
geht.
Das geht sogar konstruktiv über ein Verfahren, das auch ziemlich
polynomial aussieht.
Wie geht das?
Wir geben ein beliebiges Wort w gleich w1 bis wn.
Ich möchte entscheiden, ob das Wort ableitbar ist durch Regeln einer
vorgegebenen kontextfreien Grammatik, die in Chomsky-Normalform ist.
Das heißt also, ich will zu diesem Wort eine Ableitung produzieren.
Und das will ich machen in einem Aufwand, der linear ist in der Anzahl
der Regeln der vorgegebenen Grammatik mal Länge des Wortes hoch drei.
Das Prinzip, das wir hier anwenden, ist dynamische Programmierung,
haben Sie schon öfter gesehen.
Was machen wir?
Wir gucken uns folgende Teilmengen der Variablenmenge an.
Für jedes i, j, paar i, j, i kleiner gleich j, i, j zwischen 1 und n,
n Länge des Wortes, soll v, i, j die Menge der Variablen sein, die
sich ableiten lassen zu dem Teilwort wi bis wij.
Hier rechts steht wi, wi plus 1 und so weiter bis wi, wi, j.
Ich gucke alle Teilworte an.
Welche Variablen lassen sich durch Anwendung von Regeln meiner
Grammatik zu diesem Teilwort ableiten?
Und die entsprechenden Variablen stecke ich in die Variablenmenge v,
i, j, i-Index des ersten Symbols des Teilworts, j-Index des letzten
Symbols dieses Teilworts.
Wenn ich für alle i, j zwischen 1 und n, i kleiner gleich j, dieses v,
i, j kenne, dann kenne ich insbesondere auch die Menge v1n, Menge der
Variablen v1n.
Menge aller Variablen, aus denen sich wi1 bis wi1n ableiten lässt.
Und wenn da s drin ist, dann weiß ich, das Wort wi1 bis wi1n ist in
der Sprache, die durch meine Grammatik produziert wird.
Das ist keine neue Überlegung, sowas haben wir im Zusammenhang mit
regulären Sprachen und ähnlichen Automaten auch schon angeguckt, sowas
ähnliches.
Also auch von der Vorgehensweise, von der Idee.
Na ja gut, und das Gute ist eben, dass ich die v, i, j für wachsenden
Abstand zwischen i und j berechnen kann aus vorherigen v, i, j, wo der
Abstand zwischen i, j kleiner ist.
Wenn ich also sozusagen systematisch von unten nach oben diese v, i, j
aufbaue, erstmal die v, i, j, wo der Abstand zwischen i und j null
ist, das sind also die v, i, i und dann v, i, j, wo der Abstand
zwischen i und j eins ist, das ist also die v, i, i plus eins und so
weiter.
Dann kann ich sozusagen sukzessive meine v, i, j für wachsendes l
gleich j minus i aufbauen und wenn ich ganz oben bin, wenn ich
angekommen bin bei i gleich eins, j gleich n, also dem Abstand l
gleich n minus eins, dann brauche ich nur noch in der entsprechenden
Menge nachgucken, ob s drin ist.
Das ist also eine Verfahrensweise zu einem beliebigen vorgegebenen
Wort.
Nachzugucken kann ich das aus s ableiten.
Also die v, i, j wird nach wachsendem l, l ist der Abstand zwischen j
und i, aufgebaut, beginnend bei i gleich j.
Und das wird gemacht systematisch, indem man eben die v, i, j
zurückführt auf v, i, k, k plus eins, j, k zwischen i und j.
Also k größer gleich i, kleiner j.
Und diese Vorgehensweise ist die Vorgehensweise der dynamischen
Programmierung.
Und so sieht dann diese Tabelle aus.
Also hier habe ich mein Beispiel.
So sieht meine Grammatik aus.
Das ist eine kontextfreie Grammatik in Chomsky-Normalform.
Die rechten Seiten sind entweder nur Symbole aus Sigma oder Worte der
Länge zwei, wo die Symbole aus Variablen sind.
Und das Wort, das ich testen will, ist 1 Sternchen vereinigt 0 1 in
Klammern Sternchen.
Also die Grammatik sieht so aus.
Ich gehe jetzt nicht alles durch.
Also das Alphabet ist offensichtlich 0 1, 0 1, Klammer auf, Klammer
zu, Vereinigung, Sternchen, leere Menge.
Dieses e hier sollte vermutlich irgendwie Epsilon sein.
Das sieht jetzt ein bisschen komisch aus hier.
Und jetzt gucke ich mir mein Wort an.
Das schreibe ich hier unten rein in meine Tabelle.
Durchnummeriert, erstes Symbol, zweites Symbol und so weiter.
Und dann baue ich die vij auf nach wachsendem l gleich j minus i.
Das erste ist vii für i zwischen 1 und 8 und dann vii i plus 1 für i
plus 1,
i zwischen 1 und n minus 1, i plus 1 zwischen 2 und n und so weiter.
Die unterste Zeile ist sozusagen die Initialisierung und die darüber
liegende Zeile wird immer unter Betrachtung der Zeilen da drunter
angeguckt, so dass ich mich da sozusagen Zeile für Zeile durch diese
Tabelle durchhangele, bis ich bei v1n angekommen bin.
L gleich 0, das ist also bestimmende Einträge für diese erste Zeile
der vii.
Konstruiere die Menge vii, das heißt alle a, die sich ableiten lassen
einfach zu dem Symbol vii.
Da g in Chomsky-Normalform ist, geht das nur, wenn ich die
entsprechende Regel auch habe.
Kleine Überlegung, wieso eigentlich?
Naja gut, wegen Chomsky-Normalform haben die rechten Seiten, wenn sie
nicht nur aus einem Symbol aus Sigma bestehen, Länge zwei.
Das heißt also, wenn sie irgendeine Variable nur zu so einem Wort
ableiten, für irgendeine Variable nur eine Regel haben, wo auf der
rechten Seite zwei Variablen stehen, kommen sie von da aus nie mehr zu
einem einzelnen Symbol.
Das heißt, also ich brauche für diesen ersten Schritt nur die Regeln
der Form a nach wi, wi Symbol aus Sigma, anzugucken.
Das geht in O von Anzahl der Regeln.
Hier in dem Fall ist das also, ich gucke mir einfach hier die Regeln
an, wo auf der rechten Seite nur ein Symbol ist und trage die
entsprechenden linken Seiten hier ein, wenn die entsprechende Regel
existiert.
Also ich habe die Regel S nach 1, also kann ich über diese 1 das S
schreiben, ich habe die Regel Y-Stern nach Stern, ich habe die Regel Y
-Vereinigung nach Vereinigung und so weiter.
Das heißt also, diese erste Zeile der Vii sieht so aus, S Y-Stern Y
-Vereinigung Y-Auf, S S Y-Zu, Y-Stern.
Und jetzt geht es weiter für L größer 0,
gucke ich die Worte wi bis wj an, j minus i gleich l und für jedes
dieser Worte, für dieses Wort wi bis wj, für jedes Paar ij mit j minus
i gleich l,
muss jede Ableitung mit einer Regel der Form beginnen, auf der linken
Seite steht eine Variable, auf der rechten Seite stehen zwei
Variablen, wegen Chomsky-Normalform.
Und es muss außerdem gelten, dass es irgendein K zwischen i und j
gibt, sodass b sich dann ableiten lässt zu wi bis wk und c sich
ableiten lässt zu c nach wk plus 1 bij.
Und wie berechne ich dann die vij?
Ich überprüfe für jede Regel der Form a nach b, c und jedes k zwischen
i und j, ob b nach wi bis wk und c nach wk plus 1 bis wij existiert.
Und das mache ich durch Ansehen der entsprechenden Stelle in der
Tabelle unterhalb.
Also ich gucke, ob b in dem Array unterhalb zu wik gehört und c zu wik
wk gehört und c zu wk plus 1 j.
Das benötigt einen Aufwand in O von N mal R, das einmal zu tun.
Und jetzt machen wir das mal hier im Beispiel.
Also diese erste Zeile haben wir schon produziert.
Und jetzt für den ersten Schritt schaue ich nach Regeln der Form
Variable nach zwei Variablen und lassen sich jeweils die beiden
Variablen der rechten Seite ableiten zu Symbolen.
Da finde ich s nach sy-Stern.
Also s und y-Stern stehen hier nebeneinander, deshalb kann ich da
drüber links s einfügen.
Und wenn ich jetzt weiter gucke, also irgendeine Ableitung einer
Variablen nach y-Stern, y-Vereinigung gibt es nicht, nach y
-Vereinigung y-Auf gibt es nicht, y-Auf-s gibt es nicht, aber von nach
s -S, nämlich es gibt die Ableitung s nach s-S.
Das heißt also, s wird hier an dieser Stelle v5,6 eingefügt und es
gibt eine Ableitung von einer Variablen nach sy-Auf, nämlich c2 nach
sy -Auf.
Also wird an dieser Stelle 6,7, c2 eingefügt und eine weitere
Ableitung der Form Variable nach y-Auf, y-Stern existiert nicht, also
bleibt der Eintrag wiederum leer.
Dann für die nächste Zeile muss ich wieder von links nach rechts
durchgucken und dann wieder gucken, kann ich durch zwei sozusagen, was
die Indizes der entsprechenden vij für die Einträge entspricht, kann
ich eine Regel finden, wo auf der rechten Seite zwei da nebeneinander
liegende Variablen stehen.
Wenn ja, wird die entsprechende linke Seite an der Stelle in der Zeile
eingefügt.
Wenn ich hier durchgehe, finde ich das nur hier an der Stelle.
Also es gibt eine Regel der Form Variable nach sc2, nämlich da,
ne Moment.
Ich bin jetzt bei Worten, wo der Abstand zwischen j und i2 ist.
Also es gibt eine Regel der Form linke Seite nach sy-Auf, nämlich c
nach sy-Auf.
Einer Teil ist s, und dann führt das Wort der Länge 2, das danach
kommt, lässt sich ableiten zum Wort der Länge 2 und führt den hinteren
Teil y-Auf.
Also füge ich hier ein c2 mit sozusagen den Pfeilen zu den
entsprechenden beiden Variablen, zu denen das c2 abgeleitet werden
kann.
Dann gehe ich die nächste Zeile durch, gucke immer nach unten, gibt es
hier eine Regel von der rechten Seite, die entspricht zwei
nebeneinander liegenden Symbolen unterhalb die Worten der
entsprechenden Länge k-i, j-k-1 entsprechen.
Und da finde ich hier die Ableitung s nach y-Auf, c2, diese hier.
Dann gehe ich die nächste Zeile durch, da finde ich zunächst mal eine
Ableitung c nach y-Auf, s ohne Ableitung, also das ist c1 nach y,
hier, c1 nach y vereinigt s, das ist diese hier, und eine nach s,
y -Auf.
Das heißt also, was ich einfüge, ist für die Regel c1 nach y vereinigt
s, hier an der Stelle v7,
das ist c1, und an der Stelle v48, s für s nach s, y-Stern.
Für die Zeile finde ich keine entsprechende Regel, für die Zeile finde
ich die Regel s nach s, c1,
und für die oberste finde ich die Regel s nach s, y-Stern.
Jetzt habe ich hier oben also tatsächlich in dieser Menge s drin, das
heißt also, insgesamt lässt sich s über den Weg s ableiten nach s, y
-Stern, dann dieses s weiter ableiten nach s, c1, dann dieses c1
weiter ableiten nach y-Auf, s, dann dieses s weiter ableiten nach s, y
-Stern und dieses s weiter nach y, ich sage immer statt y vereinigt, y
-Auf, also bitte korrigieren im Kopf, aber wenn ich y-Auf jetzt sage,
ist es wirklich gemeint, also dieses s nach y-Auf, c2, dieses c2 dann
weiter ableiten nach s, y-Zu, dieses s weiter ableiten nach s, s und
wenn ich dann diese unteren weiter ableite, dann komme ich gerade auf
die Terminalsymbole von links nach rechts, 1, Stern vereinigt, Klammer
auf, 0, 1, Klammer zu, Stern.
So, Sie haben jetzt gesehen, dieser Algorithmus ist recht aufwendig,
aber das Prinzip ist einfach dynamische Programmierung.
Ich bin mir sicher, Sie werden das, wenn Sie den Algorithmus nicht
sowieso schon mal gesehen haben, haben Sie den schon mal gesehen?
Sie werden diese Vorgehensweise dann zur Genüge in der Übung auch mal
selbst üben.
So, aber was ist jetzt die Quintessenz?
Die Quintessenz ist hier diese vorletzte Zeile, das ist das, was wir
heute noch festgestellt haben, letztendlich.
Das Wortproblem für Typ-2-Grammatiken, also kontextfreie Grammatiken,
ist in polynomialer Zeit lösbar.
Also insgesamt, für Typ-0-Grammatiken ist das Wortproblem im
Allgemeinen nicht entscheidbar, für Typ-1-Grammatiken ist das
Wortproblem im Allgemeinen entweder vollständig, für Typ-2-Grammatiken
ist das Wortproblem immer polynomial lösbar, für Typ-3-Grammatiken
können Sie das sogar in linearer Zeit lösen, aber die Typ-3
-Grammatiken haben ein sehr eingeschränktes Aussehen.
Wir werden uns jetzt natürlich weiter mit kontextfreien Sprachen oder
kontextfreien Grammatiken beschäftigen, das ist irgendwie klar, da
bleiben jetzt viele weitere Fragen.
Wie kann ich für eine Sprache entscheiden, ob sie kontextfrei ist?
Wenn wir sehen, da gibt es sowas wie das Pumping Lemma, das wir für
reguläre Sprachen kennengelernt haben, das sieht sehr ähnlich aus,
Pumping Lemma für kontextfreie Sprachen.
Dann, was ist eigentlich das Maschinenmodell zu kontextfreien
Sprachen?
Typ -3-Sprachen ist der endliche Automat, hier weiter oben ist die
Turing -Maschine, die man da benutzen kann, aber kann man jetzt
irgendwie ein eingeschränkteres Maschinenmodell als die Turing
-Maschine bauen, was genau zu den kontextfreien Sprachen gehört?
Also hier bleiben jetzt eine ganze Menge Fragen noch zu beantworten
und das machen wir dann ab nächster Vorlesung.