Guten Morgen zusammen.
Das aktuelle Thema der Vorlesung ist ja Grammatiken und ich möchte den
Faden vielleicht noch mal aufnehmen.
In der letzten Vorlesung, wir haben ja in der letzten Vorlesung vor
Weihnachten mit diesem neuen Kapitel begonnen.
Grammatiken, im Prinzip kennen Sie Grammatiken aus Grundbegriffe der
Informatik.
Das sind Regelsysteme, um Sprachen zu erzeugen und wichtig ist diese
Hierarchie von Regelsystemen.
Hierarchie in dem Sinne, dass man beginnt mit Regelsystemen, für die
man keine Einschränkungen hat und dann sukzessive sinnvolle
Einschränkungen vornimmt.
Wir haben das letzte Mal diese Hierarchie, die sogenannte Homsky
-Hierarchie, angeschaut und auch bei einigen Grammatiken aus der
Hierarchie schon sehr gut verstanden, um was es sich handelt.
Was interessiert einen bei so einer Grammatik?
Es interessiert einerseits, wie mächtig ist die Grammatik?
Welche Sprachklasse wird durch die Grammatik erzeugt?
Enthält die Sprachklasse sinnvolle Sprachen vor dem Hintergrund von
Programmiersprachen oder ist sie vielleicht zu eingeschränkt?
Einerseits.
Und andererseits, wie komplex ist das Wortproblem?
Also wie schwierig ist es für eine gegebene Sprache, die von einer
entsprechenden Grammatik erzeugt wird, um ein gegebenes Wort zu
entscheiden, ob das Wort zu der Sprache gehört.
Die Homsky-Hierarchie beginnt eben mit Grammatiken, Regelsystemen, bei
denen man gar keine Einschränkungen hat.
Das ist Typ Null.
Für Typ Null haben wir festgestellt, die Typ Null Grammatiken, das
sind genau die Sprachen, die dadurch erzeugt werden.
Das sind gerade die Sprachen, die durch Turing-Maschinen akzeptiert
werden.
Prämieentscheidbare Sprachen, aber da fallen nicht entscheidbare
Sprachen darunter.
Das heißt also für Sprachen, die durch Typ Null Grammatiken erzeugt
werden, können sie noch nicht mal sagen, dass das Wortproblem
entscheidbar ist.
Das ist definitiv zu schwierig.
Definitiv ist diese Sprachklasse zu groß.
Dann hatten wir Typ 1, die kontextsensitiven Sprachen.
Da haben die Regeln der Grammatik folgende Form.
Entweder steht links ein Wort bestehend aus Variablen und rechts
irgendein beliebiges Wort, gemischt aus Variablen und Symbolen aus dem
Eingabealphabet.
Einzige Restriktion, die linke Seite ist nicht länger als die rechte.
Oder eben links steht das Startsymbol und rechts steht das leere Wort.
Bei der Sprachklasse haben wir festgestellt, bei der Klasse der
Sprachen, die durch diese Art von Grammatiken erzeugt wird, dass sie
auch Sprachen enthält, für die das Wortproblem entweder schwer ist.
Das war sozusagen der Tenor unserer Überlegung.
Das heißt also, die Sprachklasse ist vermutlich auch zu groß, als dass
man sagt, wir betrachten jetzt genauer kontextsensitive Grammatiken
als Grundlage für Programmiersprachen.
Vielleicht hier eine Bemerkung.
Sie werden möglicherweise leicht abweichende Definitionen der
entsprechenden Grammatiktypen sehen, in Lehrbüchern oder anderen
Vorlesungen oder wie auch immer.
Was ist jetzt richtig, was ist falsch?
Naja gut, wenn man eine Definition hat und dann eine Aussage beweisen
kann, die im Prinzip eine Äquivalenz zu dieser Definition ist.
Also in dem Fall, ich habe eine Grammatik von diesem Typ und kann
beweisen, jede Grammatik von diesem Typ lässt sich in eine überführen,
wo die Regeln ein bisschen anders sind, möglicherweise eingeschränkter
als hier, die aber dieselbe Sprache erzeugt.
Dann meine ich damit, na gut, da habe ich eine Definition und was
Äquivalentes und dann ist es eher Geschmackssache, ob man jetzt dieses
eine oder das andere, also die eine Sorte Einschränkung oder die
andere Sorte Einschränkung nimmt als Definition.
Eine Einsicht dieser Art werden wir heute im Zusammenhang mit den
kontextfreien Grammatiken oder Typ-2-Grammatiken auch selbst uns
erarbeiten.
So, erstmal die Typ-2-Grammatiken oder kontextfreien, wie sind die
definiert?
Die Einschränkung ist die, dass auf der linken Seite immer genau eine
Variable steht.
Rechte Seite ist so ein beliebiges Wort, gemischtes Wort aus Variablen
und Symbolen aus dem Eingabealphabet Sigma.
Aber die linke Seite, da zu sagen, da darf nur eine Variable stehen,
das ist schon eine starke Einschränkung und insbesondere im
Unterschied zum Kontextsensitiven heißt das, dass wo auch immer in
einem Wort eine Variable vorkommt und ich eine Regel habe, diese
Variable kann folgendermaßen ersetzt werden, kann ich dies auch tun,
während bei den Kontextsensitiven sie gewisse Möglichkeiten haben,
Variablen zu ersetzen durch Worte, aber möglicherweise nur, wenn diese
Variable in einem bestimmten Kontext, also in einem bestimmten Wort
vorkommt.
Hier die rechte Seite bei den kontextfreien, die ist ja nicht weiter
eingeschränkt und wir werden aber feststellen, dass man jede
kontextfreie Grammatik in eine überführen kann, bei der diese rechte
Seite sehr stark eingeschränkt.
Dazu mehr später.
Wie komplex hier das Wortproblem ist, das haben wir uns noch gar nicht
angeguckt.
Auch dazu mehr heute.
Wir hatten dann noch die Typ-3-Grammatiken oder rechtslinearen
Grammatiken, wo also die Form der Regeln noch stärker eingeschränkt
ist.
Linke Seite ist wie bei der kontextfreien eine Variable.
Mehr einschränken kann man ja auch nicht, aber bei der rechten Seite
haben wir eben auch noch eine Einschränkung, eine starke
Einschränkung.
Die rechte Seite darf entweder das leere Wort sein oder muss so
aussehen, ein Symbol aus Sigma gefolgt von einer Variablen.
Das ist eine starke Einschränkung, weil man eben hier Symbol aus Sigma
gefolgt von der Variablen hat, also rechts sozusagen von dem Symbol
von Sigma ist eine Variable, bei der man noch weiter ableiten kann.
Deshalb heißen diese rechtslinear.
Was wir aber festgestellt haben ist, dass die Sprachklasse, die
hiervon produziert wird, genau die regulären Sprachen sind.
Also genau die Sprachen, die durch Endlicher und Automaten akzeptiert
werden.
Diese Sprachklasse haben wir sehr genau zu Beginn der Vorlesung im
ersten Kapitel studiert und für die Sprachklasse haben wir
festgestellt, dass sie zu eingeschränkt ist, als dass sie als
Grundlage für Programmiersprachen sinnvoll wäre, denn in diese
Sprachklasse fällt noch nicht mal die Sprache der korrekten
Klammerausdrücke, beziehungsweise noch nicht mal eingeschränkter
sozusagen die Sprache der Worte 0 hoch n, 1 hoch n, eine natürliche
Zahl.
So, das also zur Wiederholung zu Grammatiken und Chomsky-Hierarchie
und unser Thema ist jetzt das Thema kontextfreie Grammatiken, denn die
haben wir uns im Prinzip aufgespart.
Die sind besonders interessant und wahrscheinlich auch besonders
nützlich.
Das ist jetzt unsere Vermutung, nachdem wir sozusagen über das
Ausschlussprinzip die weniger oder stärker eingeschränkten Klassen von
Grammatiken ja als entweder zu groß oder zu wenig mächtig
identifiziert haben.
So, also kontextfreie Grammatiken sehen so aus, die Regeln haben die
Form, eine Variable kann ersetzt werden durch ein beliebiges Wort.
Und wir haben auch festgestellt, dass die Sprachen, von denen wir
schon im ersten Kapitel nachweisen konnten, dass sie eben, dass da
sozusagen das die Klasse der regulären Sprachen sozusagen aufhört,
dass sie jenseits sind, sehr wohl kontextfrei sind.
Also die Sprache der Worte 0 hoch n, 1 hoch n ist kontextfrei, haben
wir uns überlegt, indem wir entsprechende Regeln angegeben haben.
Das wiederhole ich jetzt nicht, weil es auch ziemlich leicht.
Die Sprache der Palindrome ist kontextfrei, das wirkt noch mal
interessant für uns.
Palindrome, also Worte, die von vorne gelesen, dasselbe sind wie von
hinten gelesen.
Oder ja, noch weiter als eben 0 hoch n, 1 hoch n, die Sprache der
Wörter über 0, 1, bei denen die Anzahl der Nullen und die Anzahl der
Einsen gleich ist.
Okay, jetzt zur heutigen Vorlesung.
Wir werden uns also jetzt heute und noch eine ganze Weile genauer mit
kontextfreien Grammatiken beschäftigen.
Wie angekündigt, werden wir heute feststellen, dass man also diese
Einschränkungen an das Aussehen der Regeln bei kontextfreien
Grammatiken noch deutlich einschränken kann, ohne sozusagen an
Mächtigkeit zu verlieren.
Das ist das eine.
Und das andere, wir werden heute feststellen, dass sich das
Wortproblem für kontextfreie Grammatik, also für Sprachen, die durch
eine kontextfreie Grammatik erzeugt werden, in Polynomialzeit
entscheidend ist.
Das ist gut.
Dann gibt es natürlich noch eine Frage, die werden wir dann auch noch
studieren.
Was ist eigentlich das Maschinenmodell, das zu kontextfreien
Grammatiken gehört?
Bei den Typ 0 und Typ 1 Grammatiken kann man sagen, na gut, die Turing
-Maschinen, also es ist genau die Turing-Maschine bei Typ 0.
Bei Typ 1 kann man auch sagen, na ja, gut, die Turing-Maschine, aber
eingeschränkt, eingeschränkt bezüglich Platzbedarf.
Bei Typ 3, der endliche Automat, und kontextfrei liegen da irgendwie
dazwischen.
Da wäre es natürlich ganz schön, wenn man dazu auch ein
Maschinenmodell hat, was vielleicht mächtiger ist als ein endlicher
Automat und weniger mächtig als eine Turing-Maschine.
Und auch dem werden wir uns widmen und auch dieses Maschinenmodell
werden wir kennenlernen.
So, aber heute, wie gesagt, erst mal zwei andere Themen.
Jetzt als ein bisschen vorgeplänkelt noch eine Sache, die wir im
Prinzip auch kennen, soweit ich weiß, nämlich Syntaxbäume.
Ich glaube, Sie kennen Syntaxbäume, um Ableitungen zu visualisieren.
Wenn nicht, na gut, wir wiederholen es jetzt.
Also ein Syntaxbaum visualisiert die Ableitung eines einzelnen Wortes
durch Anwendungen von Regeln einer vorgegebenen Grammatik.
An der Wurzel steht das Startsymbol, also S, die Startvariable und
jeder innere Knoten entspricht genau einer Variable.
Und an den Blättern stehen eben Symbole aus Sigma oder das leere Wort.
Und wenn ein innerer Knoten A, also A steht für eine Variable, als
Nachfolger von links nach rechts, deutsche Worte Alpha 1 bis Alpha R,
deutsche Symbole Alpha 1 bis Alpha R, Alpha I ist aus V oder aus
Sigma, hat, so muss es die Regel geben, A kann abgeleitet werden zu
Alpha 1 bis Alpha R.
Syntaxbäume werden wir später auch benutzen, das ist einfach ein gutes
Hilfsmittel, wenn wir sowas wie ein Pumping-Lemma für kontextfreie
Grammatiken kennenlernen und überweisen.
Gut, aber jetzt erstmal, wie sieht so ein Syntaxbaum aus?
Hier haben wir Regeln, S kann abgeleitet werden zu 0B, ersetzt werden
durch 0B, 1A oder 1A, A kann ersetzt werden durch 0 oder 0S oder 1A, A
und B kann ersetzt werden durch 1, 1S oder 0BB.
Das sind gerade die Regeln der Grammatik, die die Sprache der Wörter,
bei der Anzahl der Nullen gleich Anzahl der Einsen ist, erzeugt.
Und wenn wir da jetzt einfach mal irgendeine Ableitung betrachten, wie
sieht dann der Syntaxbaum aus?
Also hier haben wir eine Ableitung des Wortes 1, 1, 0, 0, 1, 0, die so
aussieht, erstmal wird S durch 1A ersetzt, dann dieses A durch 1AA
ersetzt, Sie sehen ja, das geht, A kann ersetzt werden durch 1AA, dann
wird das hintere A durch 0 ersetzt, die entsprechende Regel gibt es
auch, dann wird dieses mittlere A ersetzt durch 0S, die Regel gibt es
auch, dann wird S ersetzt durch 0B und dann wird B ersetzt durch 1.
Ja, wenn man sich dazu den Syntaxbaum anguckt, also einen Syntaxbaum,
das ist ja jetzt im Moment noch nicht so ganz klar, ist das eindeutig,
naja gut, also S wird ersetzt durch 1A, S ist die Wurzel, darunter
haben wir dann 1 und A, dann A wird ersetzt durch 1AA, A wird ersetzt
durch 1AA, dieses A wird ersetzt durch 0S, dieses A wird ersetzt durch
0, S wird ersetzt durch 0B, das war der Schritt, B wird ersetzt durch
1.
Und das war jetzt ganz eindeutig, also wie aus dieser Ableitung dieser
Syntaxbaum wird, ist eine eindeutige Angelegenheit.
Da gab es jetzt keine Wahlmöglichkeiten, auch wenn ich hier die
Reihenfolgen dieser Ersetzungen von irgendwelchen A hier mal, wir uns
hier für diese eine entschieden haben, dass erst das hintere A durch 0
ersetzt wird und dann das mittlere A durch 0S, das macht hier keinen
Unterschied, ja, bei sozusagen dem Übergang von dem Level zu dem
Level.
Ob ich jetzt erst lese, A kann durch 0S ersetzt werden und dann A wird
durch 0 ersetzt oder A wird durch 0 ersetzt oder A durch 0S, der Baum
bleibt derselbe.
Aber man sieht hier schon, dass eben das, was bei kontextfreien
Grammatiken ja auch inhärent ist, nämlich, dass Sie die Reihenfolge
der Ersetzungen beliebig wählen können.
Wenn Sie also auf der rechten Seite irgendein Wort haben, wo Variablen
vorkommen, welche Variable Sie als nächstes ersetzen, das ist egal.
Da kommt dann immer derselbe Syntaxbaum raus.
Das heißt also, der eine Syntaxbaum, der gehört zu verschiedenen
Ableitungen.
Und jetzt ist eben die nächste Frage, wie verschieden können denn die
Ableitungen sein, die zum selben Syntaxbaum gehören?
Also, zu jeder Ableitung gehört genau ein Syntaxbaum.
Zu jedem Syntaxbaum gehören jedoch verschiedene Ableitungen des
gleichen Wortes, weil ich eben diese Reihenfolge der Ersetzungen von
Variablen ändern kann.
Und das haben wir hier nochmal im Beispiel.
Diese erste Ableitungsregel ist nicht dieselbe wie die, die wir eben
hatten, also gucken wir uns das nochmal an.
Also wir ersetzen s durch 1a, und dann das a durch 1aa, und dann das
mittlere a durch 0s, und dann das s durch 0b, und dann das hintere a
durch 0.
Das ist wie hier, aber man könnte jetzt auch so vorgehen, also s wird
ersetzt durch 1a, dann wird a ersetzt durch 1aa, dann wird das hintere
a ersetzt durch 0, dann wird das mittlere a ersetzt durch 0s, dann
wird s ersetzt durch 0b, und dann wird b ersetzt durch 1.
Das sind jetzt einfach Varianten in der Reihenfolge der Anwendung der
Regel.
Hier steht das nochmal, für Chomsky 2 oder Typ 2 oder eben
Kontextfreie Grammatiken gilt, wegen der Kontextfreiheit, dass die
Reihenfolge, in der abgeleitet wird, für das Ergebnis unerheblich ist.
Insofern kann man sich natürlich irgendwie festlegen, dass man sagt,
wenn ich nicht zu viel Freiheit lassen will, dann gehe ich in einer
bestimmten Reihenfolge vor beim Ableiten, und eine mögliche
Reihenfolge wäre eben immer die linkeste Variable ableiten, oder immer
die rechteste Variable ableiten.
Also eine, wo man immer in jedem Schritt die linkeste Variable
ersetzt, heißt Linksableitung, eine, wo man immer die rechteste
ersetzt, heißt Rechtsableitung.
So, und jetzt aber, wie ist das mit der Eindeutigkeit?
Wir sagen, dass eine Kontextfreie Grammatik eindeutig heißt, wenn es
für jedes Wort genau einen Syntaxbaum gibt.
Also für jedes Wort genau einen Syntaxbaum.
Der Syntaxbaum gehört sehr wohl zu verschiedenen Ableitungen.
Diese Ableitungen sind aber nur in dem Sinne verschieden, als dass man
die Reihenfolge, in denen die Variablen abgeleitet werden, halt mal
so, mal so wählt.
So, das könnte aber noch verschiedener sein.
Bei eindeutigen Grammatiken nicht, aber bei nicht eindeutigen
Grammatiken.
Also wir sagen, eine Kontextfreie Grammatik heißt eindeutig, wenn es
für jedes Wort genau einen Syntaxbaum gibt.
Und eine Kontextfreie Sprache heißt eindeutig, wenn es eine eindeutige
Grammatik zu der Sprache gibt.
Und ansonsten heißt die Sprache inhärent mehrdeutig.
So, und jetzt schauen wir uns mal die Sprache l gleich 0 hoch n, 1
hoch n, n größer gleich 1 an.
Von der wissen wir, die ist Kontextfrei.
Die Kontextfreie Grammatik dazu könnte so aussehen.
Da haben wir also nur diese zwei Sorten Regeln.
s kann ersetzt werden durch 0,1 und s kann ersetzt werden durch 0,s,1.
Da ist klar, dass sie eindeutig ist.
So, und jetzt schauen wir uns mal eine andere Sprache an.
Sprache, die entsteht, wenn wir folgende Regeln benutzen dürfen.
Das ist wieder die Sprache der Wörter über 0,1, wo die Anzahl der
Nullen gleich die Anzahl der Einsen ist.
Und da gucken wir uns jetzt mal wieder ein Wort an, nämlich 1, 1, 0,
0, 1, das ist doch 1, 1, 0, 0, 1, 0, sorry, also was wir eben auch
hatten.
Ein Wort, das abgeleitet wird, oder das zu einem Syntaxbaum gehört,
sieht man natürlich an den Blättern, wenn man einfach die Blätter von
links nach rechts spielt.
Das ist klar.
Also hier haben wir genau dasselbe Wort, 1, 1, 0, 0, 1, 0, wie hier,
1, 1, 0, 0, 1, 0.
Aber die Syntaxbäume sind verschieden.
Und hier wird eben tatsächlich auch eine andere Folge von Regeln
benutzt.
Also nicht nur, dass sozusagen Ableitungsregeln mal in der Reihenfolge
und mal in der Reihenfolge angewendet werden, sondern hier werden
wirklich andere Ableitungsregeln rechts bei dem Syntaxbaum rechts als
bei dem Syntaxbaum links angewendet.
Also das ist der Syntaxbaum, den wir eben schon hatten.
Dazu gehörten verschiedene Ableitungen für das Wort 1, 1, 0, 0, 1, 0,
die aber nur in dem Sinne verschieden waren, als dass wir einzelne
Regeln mal in der und mal in der Reihenfolge angewendet haben.
Aber hier, sehen Sie, wenden Sie wirklich andere Regeln an.
Am Anfang fängt es noch gleich an.
S wird ersetzt durch 1A, A wird ersetzt durch 1AA, dieses A wird
ersetzt durch 0, dieses A wird ersetzt durch 0S, aber hier wenden Sie
jetzt S wird ersetzt durch 1A an, während Sie hier S wird ersetzt
durch 0B anwenden.
Das sind einfach zwei verschiedene Regeln.
Aber, richtig angewendet, dann folgt eben hier die Regel B wird
ersetzt durch 1 und hier folgt die Regel A wird ersetzt durch 0 und
dann ist ja alles wieder wunderbar.
Okay, das heißt also, diese Sprache ist nicht eindeutig.
Bei einem selben Wort gibt es verschiedene Syntaxformen.
Okay.
So, jetzt der nächste Schritt.
Also, diese Grammatik war nicht eindeutig.
Zu der Sprache können wir jetzt einfach auf Basis von dem hier noch
gar nichts sagen.
Also, diese Grammatik ist nicht eindeutig.
So,
jetzt das erste große Thema der heutigen Vorlesung, nämlich kann man
das Aussehen der Regeln von kontextfreien Grammatiken einschränken
ohne Verlust?
Und die Antwort ist ja.
Man kann nämlich jede kontextfreie Grammatik im Wesentlichen in die
sogenannte Chomsky-Normalform bringen.
Erstmal, nach unserer Definition ist eine kontextfreie Grammatik in
Chomsky -Normalform, wenn alle Regeln folgende Form haben.
Entweder auf der rechten Seite stehen genau zwei Variablen, also links
steht sowieso nur eine Variable, da es sich um eine kontextfreie
Grammatik handelt, aber jetzt auf der rechten Seite genau zwei
Variablen oder genau ein Symbol aus Sigma.
Sie sehen, dass Sie auf die Art das leere Wort nicht erzeugen können.
Also das ist jetzt ein bisschen Geschmackssache, ob man hier auch noch
eine Regel zulässt, mit der das leere Wort erzeugt werden kann, denn
bei Chomsky-freien Grammatiken, entsprechend Definition, können
natürlich auch Sprachen entstehen, die das leere Wort enthalten.
Da werden wir hier noch was tun müssen, wenn wir Chomsky-Normalform
mit den kontextfreien Grammatiken sozusagen als Äquivalent im
Wesentlichen bringen wollen.
Also das ist jetzt erstmal eine Definition.
Wir nennen einfach eine kontextfreie Grammatik in Chomsky-Normalform,
wenn die Regeln dieses sehr eingeschränkte Aussehen haben.
Auf der rechten Seite genau zwei Variablen oder genau ein Symbol aus
Sigma.
Also nach der Definition von Chomsky-Normalform kann das Wort Epsilon
nicht erzeugt werden.
Wir erweitern diese Grammatiken noch um folgende Regeln.
Also wenn wir wollen, dass auch das leere Wort erzeugt wird, dann
lassen wir zusätzlich noch folgende Regeln zu.
Für ein neu eingeführtes Startsymbol S', gibt es die Regel S' nach S
und S' nach Epsilon.
Das heißt also für unsere erweiterte Chomsky-Normalform wollen wir
gleich sehen, kann die das leere Wort erzeugen.
Indem wir gucken, gibt es da diese eine Regel vom Startsymbol eine
Ableitung zum leeren Wort.
Wir nennen jetzt eine Grammatik in erweiterte Chomsky-Normalform, wenn
das eine Grammatik ist, wo die Regeln in Chomsky-Normalform sind und
es zusätzlich so eine Regel S' nach Epsilon und S' nach S gibt.
Das ist jetzt einfach ein technisches Detail, dass wir das so
definieren.
Und für solche Grammatiken gilt, jede kontextfreie Grammatik kann in
eine Grammatik in erweiterte Chomsky-Normalform überführt werden.
Also, was heißt das?
Wenn ich eine beliebige kontextfreie Grammatik habe, dann kann ich
dazu eine Grammatik konstruieren, bei der die Regeln alle die Form
haben, die rechte Seite besteht aus zwei Variablen, genau zwei
Variablen, oder die rechte Seite besteht aus genau einem Symbol aus
Sigma, oder die Regel hat die Form S' nach S, S' nach Epsilon.
Und dabei verliere ich nichts.
Das heißt also, die Sprache, die durch meine kontextfreie Grammatik
erzeugt wird, ist genau die Sprache, die durch diese entsprechend
konstruierte Grammatik in erweiterter Chomsky-Normalform erzeugt wird.
Gut, das beweisen wir und das machen wir konstruktiv, indem wir
sozusagen Schritt für Schritt uns in Richtung einer Grammatik, die in
erweiterter Chomsky-Normalform ist, bewegen.
Wir gucken uns unsere Regeln an, gucken uns an, was an den Regeln ist
noch nicht so, wie es sein soll, und versuchen diese Regeln zu
ersetzen durch Regeln, die näher an dem sind, was wir haben wollen,
wenn wir eben erweiterte Chomsky-Normalform anstreben.
Also, wir geben eine Schritt-für-Schritt-Überführung der Regeln in
Regeln in Normalform an.
Großbußstaben sind immer Variablen, nicht-Terminale, Kleinbußstaben
repräsentieren immer Terminale.
Okay.
Und wir werden bei jedem Schritt dieser Schritt-für-Schritt
-Überführung uns folgendes Beispiel angucken.
Grammatik über dem Alphabet a, b und mit folgenden Variablen Großa,
Großb, Großc, Großd, Große und Großf.
In folgenden Regeln, s kann ersetzt werden durch Großa, s kann ersetzt
werden durch Kleina, Großa, Kleina, s kann ersetzt werden durch
Kleinb, Großb, Kleinb, oder s kann ersetzt werden durch Epsilon.
a kann ersetzt werden durch Großc oder durch Kleina, Großb kann
ersetzt werden durch Kleinb, c durch Af oder durch Cde oder durch
Epsilon, d durch a oder b oder Kleinab, e durch Großb, f durch Großd
oder Große.
Naja, so sieht die halt aus.
Jetzt wollen wir die also in Chomsky-Normalform bringen.
Hier ist einiges noch nicht in Ordnung.
Wir haben auf der rechten Seite solche gemischten Wörter.
Wörter, wo Variablen und Nicht-Terminale und Terminale vorkommen.
Das darf es in Chomsky-Normalform nicht geben.
Und auf der rechten Seite gibt es Wörter, die eine Länge haben, die
zwar nur aus Variablen bestehen, Nicht-Terminale, aber die eine Länge
haben, die größer 2 ist.
Oder wir haben solche Kettenregeln, also auf der rechten Seite steht
genau eine Variable, das darf man in Chomsky-Normalform auch nicht.
Und dann wollen wir ja auch erstmal so Regeln, links eine Variable,
rechts Epsilon, nicht haben.
Und das nur für ein künstliches Startsymbol S-strich haben dürfen.
Das heißt, es ist eine Menge zu tun.
So, wie ist die Vorgehensweise?
Der erste Schritt ist, wir wollen alle Regeln so
umformen, dass auf der rechten Seite entweder nur Symbole aus V stehen
oder nur Symbole aus Sigma.
Das erste Ziel ist, keine gemischten Worte mehr auf der rechten Seite.
Wie machen wir das?
Zu allen rechten Seiten von Regeln, die es noch nicht erfüllen, gucken
wir uns die Symbole aus Sigma an und führen dafür neue Variablen ein
und fügen eine Regel, diese Variable kann durch das entsprechende
Symbol aus Sigma ersetzt werden, rein ein, und ersetzen dann eben auf
den rechten Seiten, wo dieses Symbol aus Sigma mit Variablen zusammen
vorkommt, dieses Symbol durch diese Variable.
Also, stellen Sie vor, auf der rechten Seite haben Sie so ein
gemischtes Wort, da kommt so ein a vor.
Ich führe jetzt zu dem a die Variable y a neu ein und die Regel y a
kann ersetzt werden durch a und ersetze auf allen rechten Seiten, wo a
in einer gemischten Regel vorkommt, a durch y a.
Also, wie sieht das hier aus?
Hier ist rot markiert, wo die rechte Seite nicht so ist, wie wir sie
haben wollen.
Genau, ich war eben etwas unsauber, also wir wollen auf der rechten
Seite entweder nur Symbole aus v oder sogar nur ein Symbol aus Sigma
haben.
Das ist ja die eine Regel.
Das heißt also, wir ersetzen sogar so einen kleinen a durch die
entsprechende Variable y a, wenn wir auf der rechten Seite ein Wort
haben, das länger als 1 ist und nur aus Symbolen aus Sigma steht.
Also, die Regeln, die jetzt dieses Ziel hier noch nicht erfüllen, ist
s kann ersetzt werden durch klein a groß a klein a, s kann ersetzt
werden durch klein b groß b klein b und d kann ersetzt werden durch
klein ab.
Hier haben wir also auf den rechten Seiten klein a und klein b in
Regeln stehen, die noch nicht die Form haben, wie wir sie uns hier
wünschen.
Also führen wir eine neue Variable y a ein und die Regel y a kann
ersetzt werden durch klein a und eine neue Variable y b und die Regel
y b kann ersetzt werden durch klein b und wir ersetzen jetzt also
diese klein a durch y a bei allen Regeln, die nicht die gewünschte
Form haben und wir ersetzen klein b durch y b in allen Regeln.
Okay, das war einfach.
Zweiter Schritt, also was haben wir jetzt?
Wir haben jetzt schon viel erreicht.
Wir haben jetzt auf den rechten Seiten entweder nur ein Symbol aus
Sigma, also diese Regeln, wo auf der rechten Seite nur ein Symbol aus
Sigma steht, die sehen ja schon so aus, wie sie bei Chomsky-Normalform
aussehen dürfen, oder eben wir haben auf der rechten Seite Wörter
bestehend aus Nicht-Terminalen.
Die sind schon mal ganz gut, aber die haben nicht die richtige Länge,
möglicherweise nicht die richtigen Längen, die rechten Seiten.
Okay, das heißt also, diesen Regeln müssen wir uns jetzt widmen und
jetzt machen wir folgendes, wir bringen die zumindest durch geeignete
Ersetzung der Regeln auf eine Form, dass die rechte Seite höchstens
Länge 2 hat.
Also jetzt Regeln, wo auf der rechten Seite nur Variablen stehen, aber
die entsprechenden Worte möglicherweise Länge 3 oder länger haben,
ersetzen wir durch geeignete Regeln, sodass auf der rechten Seite nur
noch eine oder zwei Variablen stehen.
Wie machen wir das?
Na gut, wir schauen uns solche Regeln an, die haben einfach irgendwie
die Form A wird ersetzt durch ein Wort, Groß B bis Groß B1 bis Groß
BM, M größer 2, die müssen wir durch neue Regeln ersetzen, dafür
führen wir, wenn wir also so eine rechte Seite der Länge M haben, M
minus 2 neue Variablen ein, die nennen wir C1 bis CM minus 2 jetzt in
dem Fall und ersetzen dann diese Regel, A kann ersetzt werden durch B1
bis BM, durch eine ganze Menge neue Regeln, nämlich die Regel A kann
ersetzt werden durch B1, das ist das erste Symbol hier, gefolgt von
C1, das ist diese erste neue Variable,
C1 beziehungsweise CI kann ersetzt werden durch BI plus 1, das ist
also das I plus 1 Symbol hier auf der rechten Seite, gefolgt durch CI
plus 1, also die I plus 1 Variable aus den neuen Variablen und
schließlich CM minus 2, das ist die letzte neue Variable, kann ersetzt
werden durch BM minus 1 BM.
Das ist offensichtlich, dass wir diese Regel, also alles was wir mit
der Regel machen können, mithilfe dieser Regeln auch machen können.
Und die Regeln haben alle diese schöne Form, die rechte Seite enthält
genau zwei Variablen.
Schauen wir uns das mal an, im Beispiel.
Welche Regeln sind nicht in Ordnung, für diesen Schritt?
Na gut, also die, wo wir auf der rechten Seite Variablen-Wörter haben,
die eine Länge größer als 2 haben.
Das ist hier bei der Regel der Fall.
S kann ersetzt werden durch YA, AYA und bei S kann ersetzt werden
durch YY, BBYB und bei der Regel C kann ersetzt werden durch CDE.
Das M ist hier 3, da muss man jeweils M minus 2, also eine neue
Variable einführen und die nennen wir hier C1 dafür, C2 dafür und C3
dafür.
Wir führen C1 ein als neue Variable, um hier diese Regel, S kann
abgeleitet werden durch YA plus AYA zu ersetzen.
Und dafür brauchen wir eigentlich nur die Regel, C1 kann ersetzt
werden durch AYA und anstatt dieser Regel, die Regel S kann ersetzt
werden durch YA C1.
Mit den beiden Regeln, S kann ersetzt werden durch YA C1 und C1 kann
ersetzt werden durch AYA, können wir S kann ersetzt werden durch YA
AYA simulieren.
Und für die anderen beiden Regeln, die nicht in Ordnung sind, geht es
analog.
Okay, jetzt haben wir schöne rechte Seiten, bis auf, wir haben hier
noch so ein Y auf der rechten Seite, das wollen wir loswerden und wir
haben hier noch so Kettenregeln, also so rechte Seiten, die aus genau
einer Variable bestehen.
Also eine Variable hier etwa, E kann ersetzt werden durch eine andere
Variable.
So, widmen wir uns erstmal den rechten Seiten, die Y sind.
Also, es kommen keine Regeln der Form A wird ersetzt durch Y vor.
Da müssen wir ein bisschen genauer hingucken.
Die Vorgehensweise besteht aus zwei Phasen.
In der ersten Phase wollen wir alle die Variablen identifizieren, die
ableitbar sind zu Y.
Also nicht nur Variable, wo es eine Regel gibt.
Variable kann ersetzt werden durch Y, sondern die ableitbar sind zu Y.
Also wo A durch mehrere Regeleinwendungen durch Y ersetzt werden kann.
Diese Menge nennen wir V'.
Da tun wir erstmal alle die A rein, für die es die Regel A kann
ersetzt werden durch Y gibt.
Und dann prüfen wir aber nach, ob durch diese Regelanwendung weitere
Regeln der Form B kann ersetzt werden durch Y entstehen würden.
Dann wird also geprüft, ob neue Regeln B kann ersetzt werden durch Y
entstehen, wenn man auf der rechten Seite A in allen Regeln, wo A auf
der rechten Seite vorkommt, durch Y ersetzt.
Wenn auf der rechten Seite nur A vorkommt und wir A durch Y ersetzen,
dann kommt eine neue Y-Regel zustande.
Wenn das der Fall ist, wenn also durch Ersetzen von A auf der rechten
Seite eine neue Regel B kann ersetzt werden durch Y entstehen würde,
dann kommt diese Variable B halt auch in V'.
Und das machen wir so lange, bis sich in V' nichts mehr ändert.
Dafür muss man einfach immer die neuen Variablen, die man in V'
reingeguckt hat, angucken, wo sie auf der rechten Seite stehen, wo
Ersetzen dieser Variablen auf der rechten Seite durch Y eine neue Y
-Regel produzieren würde.
Und wenn durch keine der Variablen mehr etwas Neues passiert, dann
kann man damit aufhören.
Das ist aber erstmal nur so testweise.
Also diese Ersetzungen, die wir hier bei dieser Vorgehensweise mal
vornehmen, die werden nicht endgültig gemacht, die werden nur
testweise vorgenommen.
In der ersten Phase wollen wir nur gucken, welche Regeln der Form
Variable kann ersetzt werden durch ein Y, würde denn entstehen, wenn
ich solche Regeln rausnehme und die entsprechenden Ersetzungen mache.
Am Ende habe ich dann also alle Variablen, die irgendwie ableitbar
sind zu Y.
Also die Menge V' aller Variablen, für die gilt, A kann zu Y
abgeleitet werden.
In der zweiten Phase mache ich jetzt wirklich eine echte Ersetzung.
Ich gucke mir das V' an, das ich produziert habe, und streiche da alle
Regeln, A kann ersetzt werden durch Y, und füge aber stattdessen für
eine Regel A kann ersetzt werden durch B, C.
Die zusätzliche Regel ein, A kann ersetzt werden durch B, falls C in
V' ist, und A kann ersetzt werden durch C, falls B in V' ist.
Das heißt also, A kann ersetzt werden durch B, C bleibt drin.
Ich gucke mir alle Variablen in V' an, für jede Variable, für die ich
so eine Regel habe, tue ich die raus, und dann gucke ich mir alle
Regeln an, A nach B, C.
Also ich weiß ja, die rechten Seiten, wo auf der rechten Seite eine
Variable steht, die haben entweder Länge 1 oder 2, und wenn die hier
diese Länge 2 haben, dann füge ich zusätzlich zu der Regel noch ein, A
nach B, wenn das zweite Symbol in V' ist, und A nach C, wenn das erste
Symbol in V' ist.
Okay, dann gucken wir uns das hier mal an.
Also erstmal muss ich dieses V' produzieren.
Da ändert sich an meinen Regeln noch nichts.
Ich will einfach nur identifizieren, welche Variablen lassen sich
ableiten zum leeren Wort.
Erstmal gucke ich mir die Regeln an, bei denen auf der rechten Seite Y
steht.
Die entsprechenden linken Seiten, die Variablen, die kommen schon mal
in V' rein.
Das heißt, Initialisierung ist, ich gucke mir an, welche Regel A nach
Y habe ich.
Ja, S kann sich ableiten, ersetzen lassen durch Y, und C kann sich
ersetzen lassen durch Y.
Das heißt, im ersten Schritt bekomme ich S und C als Elemente von V'.
Und dann gucke ich an, und wenn ich jetzt die entsprechenden Regeln
anwenden würde auf rechten Seiten, bekäme ich dann neue Regeln.
Eine Variable kann ersetzt werden durch ein Y.
Dafür muss ich gucken, wo steht auf der rechten Seite nur S oder nur
C.
Das ist der Fall hier, da steht nur C auf der rechten Seite.
Das heißt, A kommt auch in das V' rein.
Ansonsten steht nirgendwo auf der rechten Seite nur A oder nur C.
Das heißt, im ersten Schritt kommt A noch in V' rein, und ich habe
jetzt also die Menge V' gleich A, C, S.
Jetzt kann aber ersetzen von A durch Y auf der rechten Seite eben neue
Y -Regeln erzeugen.
Das heißt, ich gucke jetzt im zweiten Durchlauf nach, was passiert
denn, wenn ich auf der rechten Seite A durch Y ersetze.
Dafür muss ich gucken, steht irgendwo auf der rechten Seite A alleine?
Ja, hier steht A alleine, aber S ist ja schon in V' drin.
Das ist also nichts Neues.
Hier steht A alleine, D ist noch nicht in V' drin, also kommt die mal
wieder zu.
Ansonsten steht groß A nirgendwo rechts alleine.
Das heißt also, im zweiten Durchlauf kommt nur groß D in V' dazu.
Dritter Durchlauf, gucke nach, wo steht auf der rechten Seite D
alleine?
Hier.
F ist noch nicht in V' drin, das heißt also, F kommt in diesem
Durchlauf neu hinzu, sonst steht D nirgendwo auf der rechten Seite
alleine.
Vierter Durchlauf, ich gucke, ob eben dieses F mir was Neues liefern
würde, wenn ich also auf der rechten Seite F durch Y ersetzen würde.
Auf keiner rechten Seite steht F alleine, das heißt also, der vierte
Durchlauf bringt nichts Neues, keine Veränderung von V'.
Das heißt, ich bin mit dieser ersten Phase fertig.
Ich kenne jetzt die Variablen, die sich ableiten lassen zu Y.
Jetzt streiche ich die Y-Produktion und simuliere praktisch die
Ableitungen.
A kann zu Y abgeleitet werden auf den verbleibenden Regeln.
Ich gucke mir also meinen V' an und schaue mir an, ich streiche die Y
-Produktion und gucke noch an, was auf den rechten Seiten entsteht,
wenn ich entsprechende Variablen, die auf der rechten Seite vorkomme,
durch Y ersetze.
Da entsteht hier C nach F und C nach A und C nach C3 und hier C1 nach
YA und hier C3 nach E.
That's it.
Da habe ich einfach die Y-Ersetzung gemacht, entsprechend der Regeln
von Phase 2.
Was jetzt noch stört, sind diese Kettenregeln.
Eine Variable kann durch eine andere Variable ersetzt werden.
Das darf nicht sein.
Jetzt muss ich also analysieren, wie ich diese Kettenregeln loswerde.
Ziel im letzten Schritt ist, die Grammatik enthält keine Kettenregeln
der Form A kann ersetzt werden durch B.
Also A kann ersetzt werden durch B und A kann ersetzt werden durch C
und B kann ersetzt werden durch Groß-C und Groß-C kann ersetzt werden
durch Klein-C.
Ich will dieses A kann ersetzt werden durch B und A kann ersetzt
werden durch Groß-C und B kann ersetzt werden durch Groß-C loswerden.
Und es ist irgendwie klar, wie ich die loswerde, indem ich die
Ausführungen gucke.
Wenn ich so eine Folge von Kettenregeln anwende, wann kommt denn
rechts was Sinnvolles raus.
Also hier etwa, wenn ich A durch B ersetze und A durch Groß-B und Groß
-B durch Groß-C und Groß-C durch Klein-C, dann ist das, was Sinnvolles
rauskommt.
Groß -A wird ersetzt durch Klein-C.
Wenn ich hier außerdem noch beachte, dass Groß-A wird ersetzt durch
Groß -C auch nichts Neues, Sinnvolles rechts liefern würde, dann ist
irgendwie klar, das Beste, was ich tun kann, ist, dass ich einfach
diese Regeln ersetze durch Groß-A kann ersetzt werden durch Klein-C.
Wie ist jetzt die Vorgehensweise, denn diese Kettenregeln, die können
ja ganz unübersichtlich miteinander verwoben sein.
Also einfach so einmal durch und dann gucken, was kann ich da anstatt
von so einer Folge von Anwendung von Kettenregeln an die rechte Seite
tun zu den Variablen, mit denen ich anfange.
Das ist nicht ganz klar, ob das dann wirklich zu einer äquivalenten
Grammatik führt.
Naja gut, also wenn ich sage, die können so miteinander verwoben sein,
dann kann einerseits durch Kettenregeln ich in Kreise laufen und die
sollte ich mal als erstes versuchen loszuwerden.
Und dann können die Kettenregeln also irgendwie so eine partielle
Ordnung praktisch oder so ein zykelfreier gerichteter Graph aussehen.
Da muss ich dann die Kettenregeln auch in einer sinnvollen Reihenfolge
sozusagen ersetzen.
Das heißt also in der ersten Phase versuche ich die Zyklen zu finden
oder finde ich die Kreise.
Also die Folgen von Kettenregeln, wo die erste Variable hinten wieder
auftaucht, also der Form A1 kann ersetzt werden durch A2, A2 durch A3
und so weiter, das führt mich zu AN und AN kann schließlich ersetzt
werden durch A1.
Wenn ich so einen Kreis habe, dann könnte ich all die AI dazwischen
durch A1 ersetzen.
All die AI, weil die sind dann im Prinzip äquivalent.
Die führen mich auch nur wieder zu A1 und alles was ich sonst noch von
A1 aus machen kann, kann ich also auch von denen aus machen.
Und wenn ich diese Kreise losgeworden bin, dann muss ich also in
meinem a-zyklischen gerichteten Graph, der durch die Regeln sozusagen
induziert wird, sinnvoll die verbleibenden Kettenregeln loswerden.
Und dazu mache ich folgendes, ich sortiere mir die Variablen geeignet,
sodass entsprechend dieser Sortierung von hinten ich sozusagen
Kettenregel für Kettenregel äquivalent ersetzen kann.
Also, wenn ich die sozusagen richtig sortiert habe, dann kann ich für
eine Regel A kann ersetzt werden durch B und jede Regel B kann ersetzt
werden durch klein b.
Stattdessen einführen, Gruß A kann ersetzt werden durch klein b und
Gruß A kann ersetzt werden durch Gruß B kann ich streichen.
Wenn ich das in der richtigen Reihenfolge mache, dann führt mich
sozusagen diese Form von Ersetzung zu einer äquivalenten Grammatik.
Was ist eine sinnvolle Sortierung?
Was meine ich damit?
Wir machen eine topologische Sortierung auf den Variablen, die in
Kettenregeln vorkommen.
Also V1 bis Vk sind die Menge der Variablen, die irgendeine Rolle
spielen bei Kettenregeln.
Und die Induzierung entspricht einer topologischen Sortierung, wenn
folgendes gilt.
Wenn gilt für jede Regel, bei denen diese Variablen involviert ist,
der Form, oder jede Ableitung der Form, Vi kann abgeleitet werden zu
Vj, impliziert i ist kleiner j.
So eine topologische Sortierung kriege ich natürlich nur, wenn ich
keine Zyklen habe.
Deshalb ist es wichtig, vorher diese Zyklen loszuwerden.
Gut, dann schauen wir uns jetzt mal für unsere Grammatik die
Kettenregeln an und den Abhängigkeitsgraf, der zu diesen Kettenregeln
gehört.
Also hier in Rot sind die Kettenregeln.
Und da habe ich S kann abgeleitet werden zu A und dann habe ich A kann
abgeleitet werden zu C.
Dann habe ich C kann abgeleitet werden zu F oder C kann abgeleitet
werden zu C3.
Ach nee, Moment, sorry.
Ach doch, doch, doch.
Zu C3, genau.
Das müsste halt Rot sein.
Ach nee, nochmal zwei zurück.
Also in Rot sind die Zyklen.
Also der ganze gerichtete Graf zeigt mir die Kettenregeln oder die
Abhängigkeiten der Kettenregeln.
In Rot sind die Zyklen.
Also ich habe S nach A und dann A nach C und dann C nach F oder C nach
C3.
Von F geht es weiter nach E oder nach D.
Von C3 nach E, von E nach B und von F nach D.
Und dann kann man von D zurück nach A und von C zurück nach A.
Und dann gibt es noch diese Kettenregel C1 wird ersetzt durch YA.
Und als erstes gucke ich mir an die Kreise.
Also hier sind alle Kettenregeln Rot und hier sind mit roten Pfeilen
nur die Kreise.
Visualisiert.
Jetzt gucke ich mir also diese Kreise mal an.
Das ist also erstmal dieser Kreis A nach C und C nach A und dann der
Kreis A nach C nach F nach D und wieder nach A.
Was daraus folgt ist, dass also A, C, F und D äquivalent sind.
Alles was ich von A aus machen kann, kann ich auch von C aus machen,
auch von F aus machen, auch von D aus machen und so weiter.
Jetzt entferne ich alle die an diesen Zyklen beteiligten Regeln und
ersetze alle Vorkommen von dem was dazwischen steht, also C, F, D,
durch A.
Und lösche dann alle Regeln die dadurch entstehen würden, die die Form
haben, A kann ersetzt werden durch A.
Denn das macht ja keinen Sinn.
Okay, schauen wir uns den Zyklus mal an.
Also hier sind jetzt rot alle Vorkommen von Variablen aus diesem
Zyklus.
Und ich ersetze jetzt all diese rot Vorkommenden durch A.
Im ersten Fall bringt das nichts Neues.
Ich habe hier die Regel A nach C.
Wenn ich jetzt das C durch A ersetze, bekäme ich die Regel A nach A.
Die bringt aber nichts Neues, die lösche ich also.
Weiter geht's.
C nach A, F.
Ich ersetze all die Variablen aus dem Kreis, die da vorkommen, durch
A.
Dadurch kriege ich A nach AA.
Außerdem gibt es C nach F.
Wenn ich C und F durch jeweils durch A ersetze, bekäme ich wieder A
nach A.
Die kann ich streichen.
Dann C nach A.
Wenn ich das C durch A ersetze, kriege ich wieder A nach A.
Kann ich streichen.
Und C nach C, C3.
Ich ersetze das Kurs C jeweils durch A.
Dadurch kriege ich A nach A, C3.
Und so weiter.
Also einige Regeln werde ich los, weil die Ersetzungen durch A einfach
A nach A ergeben.
Was ich nicht brauche.
Ansonsten habe ich eben jetzt alle Vorkommen der Variablen aus dem
Kreis ersetzt durch A.
Okay, damit bin ich die Kreise los geworden.
Und habe jetzt nur noch diesen Abhängigkeitsgraf.
Und jetzt möchte ich die weiteren Kettenregeln, die hier immer noch in
Rot stehen, loswerden.
Und dazu muss ich jetzt also meine Regeln bzw.
die Variablen topologisch sortieren.
Das heißt also, was links steht, muss in meiner topologischen
Sortierung immer vor allem, was rechts steht, kommen.
In allen Regeln.
Das kann ich hier wunderbar ablesen.
Also S muss in der topologischen Sortierung vor A kommen.
A muss vor C3 kommen.
A und C3 müssen vor E kommen.
Und die müssen alle vor B kommen.
Das heißt also, für diesen Teilgraf habe ich die topologische
Sortierung S, A, C3, E, B.
Und dann habe ich noch den kleinen Teilgraf.
Dafür habe ich die topologische Sortierung C1, Y, A.
Und ob ich die jetzt vor oder hinter diese Kette setze, ist
Geschmackssache.
Ich habe es einfach dahinter gesetzt.
Und entsprechend dieser topologischen Sortierung, aber von hinten
angefangen, muss ich jetzt weiter Kettenregeln ersetzen.
Also hier in umgekehrter topologischer Sortierung vor.
Ersetze A, kann ersetzt werden durch B.
A kann ersetzt werden durch Beta.
Beta ist irgendeine rechte Seite.
Falls die Regel B kann ersetzt werden durch Beta existiert.
Die topologische Sortierung ist diese hier.
Ich fange also von hinten an.
Also habe ich irgendwo auf der linken Seite Y, A stehen von der
Kettenregel?
Nein.
Ich habe auf der rechten Seite Y, A von der Kettenregel stehen.
Und davor steht C1.
Das heißt also, ich gucke jetzt nach.
Gibt es irgendeine Regel Y, A nach klein Beta?
Dann ersetze ich die Regel C1 nach Y, A durch C1 nach klein Beta.
Es gibt Y, A, kann ersetzt werden durch klein A.
Also ersetze ich diese Regel.
C1 kann ersetzt werden durch Y, A.
Durch die Regel C1 kann ersetzt werden durch klein A.
Das ist das hier.
Ich war jetzt bei C1.
Gibt es noch irgendwas mit C1?
Vorkommen von C1?
Nein.
Dann gehe ich weiter.
Vorkommen von B.
Hier B steht hier und hier auf der rechten Seite.
Und ich habe eine Regel.
Groß B kann ersetzt werden durch klein B.
Das heißt also, die Groß B auf der rechten Seite, die ersetze ich
durch klein B.
Und jetzt kommt die Regel.
Die Regel, so hier, A nach klein B.
Und E nach klein B zustande.
Dann gehe ich weiter.
Gucke mir an.
E auf der rechten Seite.
Habe ich irgendeine Ersetzung?
Jetzt in der aktuellen Grammatik irgendeine Regel?
E kann ersetzt werden durch Beta?
Ja, ich habe E kann ersetzt werden durch klein B.
Das heißt also, dieses E kann ich durch klein B ersetzen.
Und so weiter.
Das mache ich eben, bis ich hier durch diese Sortierung durch bin.
Wenn ich damit fertig bin, hat meine Grammatik die gewünschte Form.
Also, ich habe keine Kettenregeln mehr.
Ich hatte vorher schon dafür gesorgt, dass die rechten Seiten entweder
nur aus einem Symbol aus Sigma bestehen oder aus maximal zwei
Variablen.
Wenn ich die, die aus genau einer Variable bestehen, jetzt also im
vierten Schritt losgeworden bin, habe ich also wirklich nur noch
rechte Seiten, die aus genau aus einem Symbol aus Sigma oder aus genau
zwei Variablen bestehen.
So, was ich jetzt unter der Hand eliminiert habe, ist mögliche
Ableitungen von S aus zu Epsilon.
Ob es sowas gab, habe ich in dem entsprechenden Schritt daran gesehen,
dass in meiner Menge V' auch S vorgekommen ist.
Das war bei der Grammatik auch der Fall.
Wenn das der Fall ist, muss ich jetzt erweitern, indem ich also noch
diese Sonderregeln einführe mit einem neuen Symbol S'.
S' kann ersetzt werden durch S und S' kann ersetzt werden durch
Epsilon.
So, und dann bin ich fertig.
Okay, was ich also jetzt habe, ist, dass jede kontextfreie Grammatik
sich in so eine Grammatik in erweiterter Kontextform die Normalform
überführen kann.
Wofür ist das gut?
Eine sehr eingeschränkte Form von Regeln zu haben, ist natürlich gut,
um damit zu arbeiten.
Und wir werden jetzt im nächsten Schritt tatsächlich damit arbeiten,
wenn wir nämlich zeigen, dass für kontextfreie Grammatiken das
Wortproblem in Polynomialzeit entscheidbar ist.
Und das ist eben dieser Satz hier.
Es gibt einen Algorithmus, der steht in der Literatur unter CYK
-Algorithmus für Kug-Yanga-Kazami, die Leute, die sich den Algorithmus
überlegt haben, der für eine kontextfreie Grammatik G in erweiterter
Chomsky -Normalform und ein Wort W aus Sigma-Stern in Zeit O von
Anzahl der Regeln mal Länge des Wortes hoch 3 entscheidet, ob das Wort
in der Sprache ist, die durch die Grammatik erzeugt wird, also in
Polynomialzeit.
Also sozusagen die Vorgabe der Grammatik, Anzahl der Regeln und so
weiter, die könnten sie als konstant annehmen, oder eben wenn sie
sagen, die will ich nicht vernachlässigen, wie viele Regeln die
Grammatik hat, dann nehme ich eben dieses Anzahl der Regeln hier mit
rein.
Aber eigentlich interessiert einen ja immer, ist die Laufzeit eines
Algorithmus, der für ein vorgegebenes Wort entscheidet, ob das Wort in
der vorgegebenen Sprache ist, Polynomial ist in der Länge des Wortes.
Also dass das hier sozusagen grubig in der Länge des Wortes ist, das
ist vor allem hier die entscheidende Aussage.
Ich habe eben so unter der Hand gesagt, in erweiterter Chomsky
-Normalform, jetzt in dem Satz steht nur in Chomsky-Normalform.
Das Essenzielle ist ja, dass ich mit dem Satz mir überlegen kann, dass
ich für eine beliebige kontextfreie Grammatik, egal in welcher Form
die daherkommt, im Prinzip mit ein bisschen Sonderaufwand das
Wortproblem in Polynomialzeit entscheiden kann.
Der Sonderaufwand wäre, die erstmal in erweiterte Chomsky-Normalform
zu bringen.
Und der sehe ich sofort an, ob das leere Wort dazugehört oder nicht.
Das heißt also, wenn hier das leere Wort wäre, dann brauche ich
einfach gucken, gibt es die entsprechende Regel S' nach Y.
Interessant ist nur, für andere Wörter kann ich entscheiden, ob das
entsprechende Wort durch Ableitung aus der entsprechenden Regelmenge
produziert werden kann.
Und wie das geht, ist also jetzt der Beweis für diesen Satz.
Dazu gucke ich mir an, wie so ein Wort aussieht.
Das sieht irgendwie so aus, W ist gleich W1 bis Wn, Wi sind jetzt also
Symbole aus Sigma.
Und ich gucke mir an, welche Teilworte können aus irgendeiner
beliebigen Variablen abgeleitet werden.
Das ist jetzt mehr, wenn ich mir das angucke für beliebige Variablen
und beliebige Teilworte, dann sehe ich da mehr, als ich eigentlich nur
sehen brauche.
Denn was ich eigentlich wissen will, ist, ob die Variable S ableitbar
ist zu diesem ganzen Wort.
Aber wenn ich mir alle Variablen A bestimme, für die gilt, A ist
ableitbar zu Wi, Wi bis Wj.
Wi bis Wj ist eben das entsprechende Teilwort von W.
Und die entsprechenden Variablen, Variablenmenge Vij nenne, dann ist
die Variablenmenge, die mich eigentlich interessiert, V1n und ob S in
V1n ist.
Also wenn ich diese Vij bestimmen kann, für alle Ij zwischen 1 und n,
dann kann ich entscheiden, ob W in L von D ist, indem ich einfach
nachgucke, ob in V1n S drin ist.
Dieses Muster müsste Ihnen jetzt bekannt vorkommen.
Sowas haben wir schon gehabt im Zusammenhang mit regulären Sprachen
und endlichen Automaten.
Und das Prinzip, warum man hier mehr betrachtet, als man eigentlich
nur betrachten will, ist, dass wir hier dynamische Programmierung
anwenden, um an dieses V1n ranzukommen.
Um das V1n zu bestimmen, benutzen wir solche Vij mit Hilfe von
dynamischer Programmierung.
Das heißt, man konstruiert mehr, als man braucht, aber das ist die
Konstruktionsform dynamischer Programmierung, die einem das vorgibt.
Diese Vij produziere ich.
Und zwar schön von unten nach oben, sage ich mal.
Also V1n, diese Variablenmenge, die mich eigentlich interessiert, ist
die, wo der Abstand zwischen den zwei Indizes maximal groß ist.
Von 1 bis n.
Und die Vij, das sind solche Variablenmengen, wo der Abstand zwischen
i und j eben j-i ist.
Und das mache ich sozusagen von unten nach oben.
Ich gucke mir erst die an, wo der Abstand 0 ist.
Also das sind die Vii.
Und dann Vij, wo der Abstand 1 ist.
Also das ist dann Vii, i plus 1.
Und dann, wo der Abstand 2 ist, Vii, i plus 2 und so weiter.
Und die kann ich immer produzieren unter Benutzung der Vij, die ich
bisher produziert habe.
Das heißt also, ich mache mir so eine Art Tabelle der Vij nach
wachsendem Abstand zwischen j und i.
Nach wachsendem l gleich l gleich j minus i.
Beginne mit l gleich 0.
Und wenn eben l größer 0 ist, kann ich jeweils für die entsprechenden
j und i das Vij systematisch mit den zuvor produzierten Vik, Vk plus
1, j bekommen.
Denn für j minus i gleich l größer 0 kann ich Vij systematisch
herleiten, indem ich alle k zwischen i und j betrachte und die
entsprechenden Vik, Vk plus 1, j.
Das ist gerade das Prinzip der dynamischen Programmierung.
Also wie sieht die Tabelle aus?
Wir gucken uns das gleich an einem Beispiel an.
Unser Alphabet sieht so aus.
Wir haben Sternchen, Klammer auf, Sternchen, Vereinigung, Klammer auf,
Klammer zu, 1 und 0.
Das ist das Alphabet.
Und dann haben wir hier so bestimmte Variablen, s, y, s, c1, c2,
y, Klammer auf, y, Klammer zu, y, Sternchen und y, Vereinigung.
Und dann haben wir hier noch einen kleinen e und eine leere Menge.
Okay.
Die sollen also auch noch in unserem Alphabet sein.
Tauchen hier aber nicht groß auf.
So, das ist das Wort, das wir angucken und für das wir entscheiden
wollen, ob es durch diese Regeln hier produziert, also Anwendungen von
Regeln hier aus dieser Menge produziert werden.
Das Wort ist 1, Sternchen, Vereinigt, Klammer auf, 0, 1, Klammer zu,
Sternchen.
Okay.
Die Tabelle ist v, i, j für wachsenden Abstand zwischen i und j.
Erstmal Abstand zwischen i und j gleich 0, das sind die v, i, i, also
v11, v22, v33 und so weiter.
Also, welche Variablen lassen sich unmittelbar ableiten zu einem
Symbol wie i, also zu w1 oder w2 oder w2 und so weiter, heißt das.
Und dann in der nächsten höheren Stufe, v, i, i plus 1, also v12.
Welche Variablen lassen sich ableiten zu dem Wort bestehend aus w1, w2
und so weiter.
Das ist also die Bedeutung.
Also, erstmal für die unterste Reihe, da will ich einfach nur wissen,
welche Variablen lassen sich ableiten zum ersten Symbol des Wortes,
zum zweiten Symbol des Wortes, zum dritten und so weiter.
Die Symbole des Wortes, die stehen hier.
Also, erstes Symbol ist die 1, zweites ist Sternchen, drittes ist
Vereinigungszeichen, viertes Klammer auf und so weiter.
So, wie kriege ich v11, v22, v33 und so weiter?
Indem ich einfach gucke, wo habe ich eine Regel, Variable wird
ersetzt, kann ersetzt werden durch das entsprechende Symbol.
Also, welche Variable kann ersetzt werden durch 1?
S.
Welche Variable kann ersetzt werden durch Sternchen?
Y-Sternchen.
Welche Variable kann ersetzt werden durch Vereinigung, das Zeichen
Vereinigung?
Y -Vereinigung.
Welche Variable kann ersetzt werden durch Klammer auf?
Y-Klammer auf.
Welche Variable kann ersetzt werden durch 0?
S.
Welche durch 1?
Ebenfalls S.
Welche durch Klammer auf?
Y-Klammer auf.
Welche durch Sternchen?
Naja, das hatten wir schon.
Y-Sternchen.
Und ansonsten, also hier sehr einfach gehalten, das Beispiel gibt
immer nur eine Variable in der entsprechenden Variablenmenge.
Das können natürlich, das sind Mengen, diese V-I-J, ja, aber hier sind
es immer einelementige Mengen.
Also, das heißt also im ersten Schritt, es geht immer von da nach da,
also immer hier von links nach rechts und dann nächste Zeile von links
nach rechts.
Also im ersten Schritt bekomme ich diese Variablenmenge.
So, im nächsten Schritt, weil L größer 0,
weiß ich, also jede Ableitung von irgendeinem Wort, vom Teilwort B-I
bis B-J muss mit irgendeiner Regel A nach B-C beginnen.
Das geht nicht anders.
Und es muss so sein, dass ein erstes Teilwort W-I bis W-K entsteht,
indem ich die Regel B nach W-I bis W-K ansetze und das zweite Teilwort
W -K plus 1 bis W-J entsteht, indem ich die Regel C nach W-K plus 1
bis W-J anwende.
Das heißt also, jetzt für jede weitere Erstellung von V-I-J muss ich
einfach nach Regeln gucken.
Variable kann ersetzt werden durch B-C, zwei Variablen B und C.
Und ich habe die Möglichkeit, B zu ersetzen durch den Wort W-I bis W-K
und C zu ersetzen durch W-K plus 1 bis W-J und wir wachsen in Abstand
zwischen W-I und W-J, kriege ich mehr Zwischenstellen K, die ich
betrachten muss.
Das mache ich auch schön systematisch, deshalb diese Vorgehensweise,
die hier angegeben ist.
Ich gehe von links nach rechts und dann in der nächsten Zeile wieder
von links nach rechts und so weiter.
Wie implementiere ich das oder was ist das für eine Vorgehensweise?
Naja gut, ich speichere mir alle Mengen als Arrays ab, der Länge,
Anzahl der Variablen, in denen jeweils für eine Variable markiert ist,
ob sie in diese entsprechende Menge V-R-S gehören.
Und dann kann ich V-I-J berechnen, indem ich für jede Regel A nach B-C
überprüfe und für jedes K zwischen, also K größer gleich I kleiner J,
ob B ableitbar zu W-I bis W-K und C ableitbar zu W-K plus 1 bis W-J,
durch Ansehen von B in der Stelle zu V-I-K und von C in dem Array zu V
-I -K und von C in dem Array zu V-K plus 1.
Im Beispiel ist es ein bisschen einfacher, aber hier sehen Sie, das
ist also dynamische Programmierung, Sie benötigen jeweils dafür N mal,
also für so ein V-I-J, N mal Anzahl der Regeln, das heißt also für
alle V-I-J, für alle Paare I-J, N hoch 3 mal Anzahl der Regeln.
Okay, also im ersten Schritt haben wir hier diese Variablen bekommen
und jetzt geht es weiter.
Wir müssen den Abstand 1 angucken und dafür müssen wir gucken, was
haben wir an Regeln.
Variablen können abgeleitet werden zu hier so zwei
aufeinanderfolgenden, also S-Y-Sternchen oder Y-Sternchen, Y-Vereinigt
und so weiter.
Gibt es eine Regel, Variable kann abgeleitet werden zu S-Y-Sternchen?
Ja, die gibt es, nämlich S nach S-Y-Sternchen und sonst keine, das
heißt an die Stelle gehört das S.
Dann für V-II-III gibt es eine Regel, eine Variable kann abgeleitet
werden zu Y-Sternchen, gefolgt von Y-Vereinigt.
Das ist nicht der Fall, das heißt also diese Menge ist leer.
Dann gibt es eine Regel, eine Variable kann abgeleitet werden zu Y
-Vereinigt, gefolgt durch Y-Klammer auf.
Das ist nicht der Fall, also kommt hier die leere Menge hin.
Dann für die nächste Regel, für die nächste Menge, V-II-I plus 1, gibt
es eine Regel, eine Variable kann abgeleitet werden zu Y-Klammer auf,
gefolgt von S.
Das ist nicht der Fall, also kommt hier auch die leere Menge raus.
Dann kann eine Variable abgeleitet werden zu S-S.
Ja, S kann abgeleitet werden zu S-S, keine weitere.
Also wird V-5-6 genau aus S bestehen.
Dann V-6-7 kann eine Variable abgeleitet werden zu S, gefolgt von Y
-Klammer auf.
Ja, C-2 kann abgeleitet werden zu S, gefolgt von Y-Klammer auf, keine
weitere Variable.
Also kommt da Y-2 hin und dann für V-7-8 gibt es eine Variable, die
abgeleitet werden kann zu Y-Klammer auf, gefolgt von Y-Sternchen.
Nein, also kommt hier die leere Menge hin.
Okay, weiter geht's.
Jetzt V-I, I plus 1, da muss man gucken, die Zwischenstelle I und die
Zwischenstelle I plus 1.
Also, V-1-2, wie sieht die Menge V-1-2 aus?
V-1-3 aus?
Es geht mir um das Wort 1 bis 3, also V-1 bis V-3, also um das Wort 1
-Sternchen -Vereinigung.
Also hier diese ersten drei Symbole in dem Wort.
Und die könnte ich bekommen, indem ich eine Regel habe, eine Variable
kann abgeleitet werden zu zwei Variablen A, B, von denen die erste
abgeleitet werden kann zu 1 und die zweite zu Sternchen-Vereinigung.
Oder indem ich eine Regel habe, eine Variable kann abgeleitet werden
zu zwei Variablen, von denen die erste abgeleitet werden kann zu 1
-Sternchen und die zweite zu Vereinigung.
Jeweils die entsprechenden Variablenmengen, die da rechts vorkommen
können, von der Anfangsregel eine Variable, die sozusagen nach V-1-3
gehört, kann abgeleitet werden zu zwei Variablen, die dann weiter
richtig abgeleitet werden können, stehen schon hier bzw.
hier.
Also, wenn ich die erste Variante angucke, kann ich eben eine Variable
ableiten zu zwei Variablen, von denen die erste abgeleitet werden kann
zu 1 und die zweite zu Sternchen-Vereinigung.
Da stünde die erste hier und die zweite hier.
Oder aber gibt es eine Variable, die abgeleitet werden kann zu zwei
Variablen, von denen die erste ableitbar ist zu 1-Sternchen und die
zweite zu Vereinigung.
Da stünde die zweite hier und die erste hier.
Und wenn ich das einzeln durchgehe, dann komme ich darauf, dass es
keine Variable gibt, über die ich 1-Sternchen-Vereinigung ableiten
kann und auch keine, über die ich Sternchen-Vereinigung-Auf ableiten
kann usw.
Aber ich kann C2 ableiten zu S-Y-Vereinigt und S weiter ableiten zu 0
und Y-Vereinigt zu 0,1 und Y-Vereinigt zu Klammerauf.
Deshalb kommt C2 hier rein und hier gibt es keine Variable, die sich
ableiten lässt.
Hier in so einem Variablenpaar, mit dem ich weiterkomme und insgesamt
1 Klammerauf-Sternchen ableiten kann.
Und dann gehe ich wieder 1 höher und dann wird das jetzt wieder
komplizierter, weil es jetzt wieder mehr Möglichkeiten gibt, wie ich
die Zwischenstelle wähle.
Also jetzt für diese Zeile geht es um die Teilworte der Länge 4.
Das wäre also 1-Stern-Vereinigung-Klammerauf.
Die entsprechende Menge, die sich dazu ableiten lässt, ist V1-4.
Oder eben Sternchen-Vereinigung-Klammerauf-0.
Die Menge der Variablen, die sich dazu ableiten lässt, das wäre gerade
V2 -5.
Und dafür muss ich gucken, bei V1-4 kann ich irgendeine Variable
ableiten zu zwei Variablen, sodass die erste sich zum ersten Teil des
Wortes und die zweite zum zweiten Teil des Wortes ableiten kann.
Und diese beiden Teilworte, die könnten jetzt entweder Länge haben 1
und 3 oder 2 und 2 oder 3 und 1.
Und für 1 und 3 müsste ich hier gucken und hier und für 2 und 2 hier
und hier und für 3 und 1 hier und hier und hier.
Hier stehen Gott sei Dank viele leere Mengen, sodass da nicht allzu
viel rauskommen kann.
Insgesamt kommt raus, ich kann nur für diese Menge hier, das ist V4-7,
eine nicht leere Menge bekommen, nämlich genau die Menge, die S
enthält.
Und zwar für die Regel, S kann sich ableiten lassen zu Y-Auf, C2.
Y-Auf ist schon mal das erste Symbol meines Teilworts, was ich
betrachte.
Und C2 ist eine Variable, die sich weiter ableiten lässt zu dem
restlichen Teilwort, das da ist 0 1 Klammer auf.
Und zwar indem C2 abgeleitet wird zu Sy-Auf und S weiter abgeleitet
wird zu SS und S zu 0 und S zu 1.
Und wenn ich so weiter vorgehe, dann kriege ich hier halt dann noch
weitere Mengen und so weiter.
Das ist ein bisschen mühsam.
Und wie gesagt, das Beispiel ist insofern irritierend, als dass diese
Mengen V, I, J alle einelementig sind.
Das muss im Allgemeinen nicht unbedingt der Fall sein.
Also leere Menge oder einelementig sind, das muss nicht unbedingt der
Fall sein.
Das sind immer variablen Mengen, die hier stehen.
Okay.
Machen wir mal ein Zwischenergebnis.
Ich habe das meiste davon in der Einführung schon gesagt.
Also zu dieser einen großen Frage.
Ich habe eine Grammatik oder einen Typ von Grammatiken aus der Chomsky
-Hierarchie und ich interessiere mich, wie schwierig ist das
Wortproblem für die entsprechenden Grammatiken.
Wo weiß ich, dass bei Typ 0 das Wortproblem nicht entscheidbar ist,
bei Typ 1 das Wortproblem im Allgemeinen entweder vollständig ist, Typ
3 das Wortproblem in linearer Zeit lösbar ist.
Das ist einfach das Wort in den endlichen Automaten reinschicken und
einmal durch.
Und Typ 2, das ist das, was wir jetzt mit dem CYK-Algorithmus
festgestellt haben, das Wortproblem in polynomialer Zeit lösbar ist,
im Wesentlichen kugelig in der Länge des Wortes.
Und das wäre es dann für heute.