Wir fangen einen neuen Abschnitt im Buch an.
Kapitel 1 ist ja die Chomsky-Hierarchie.
Wir arbeiten uns von unten nach oben von den sehr speziellen,
regulären Sprachen jetzt zu den kontextfreien Sprachen, die besonders
spannend sind, weil sie eigentlich den Schlüssel darstellen für die
Verarbeitung der meisten formalen Sprachen.
Programmiersprachen, XML, HTML, das sind alles kontextfreie Sprachen.
Und um die effizient zu verarbeiten, muss man was darüber wissen,
welche Eigenschaften die haben.
Das Beispiel, das wir...
Zwei Beispiele, die wir gesehen hatten, waren Klammerausdrücke, also
eine vereinfachte Form von Klammerausdrücken, oder die Sprache A hoch
N, B hoch N, mit N größer gleich 1.
Aber eben auch der Syntax von Pascal, C, C++, Java, was sie wollen,
sind kontextfreie Sprachen.
Hier zur Erinnerung unser Bild.
Die regulären Sprachen verstehen wir jetzt sehr gut, was die mit
endlichen Automaten zu tun haben.
Und jetzt gucken wir uns an kontextfreie Sprachen.
Wir wollen dann so Fragen beantworten, warum ist A hoch N, B hoch N, C
hoch N keine kontextfreie Sprache.
Wir wollen einen Maschinen-Typ haben, der genau die Typ-2-Sprachen
akzeptiert.
Wir wollen das Wortproblem lösen.
Wir wollen Standardprobleme in solchen Sprachen lösen, usw.
Heute werden wir uns mit Normalformen beschäftigen.
Das klingt auf den ersten Blick langweilig.
Wir werden dann aber sehen, später z.B.
beim Wortproblem, dass die Normalformen es einem erleichtern,
Algorithmen zu entwerfen.
Weil dann braucht man Algorithmen plötzlich nicht mehr für beliebige
Typ -2-Grammatiken, sondern nur noch für Typ-2-Grammatiken mit ganz
besonderen Eigenschaften.
Ich denke, diese Normalform-Geschichte geht sogar über das Thema
formale Sprachen hinaus.
In der Informatik ist es einfach eine ganz wichtige Grundtechnik, zu
sagen, wir haben eine Problemstellung, die sehr allgemeine
Problemstellungen enthält.
Wir wollen aber nur einen Algorithmus bauen für sehr spezielle
Problemstellungen.
Das ist dann kein Problem, wenn wir einen Übersetzer definieren
können, der die allgemeinen Problemstellungen in speziellere
übersetzt, die in eine Normalform bringen.
Und auch die Algorithmen, die wir hier vorstellen werden, um
Normalformen von Grammatiken zu erstellen, sind eigentlich typische
Beispiele dafür.
Und in anderen Anwendungen sieht das sehr ähnlich aus.
Wir werden nämlich immer so Ersetzungsregeln spezifizieren, die sagen,
okay, wenn hier eine komplizierte Regel ist, dann ersetze die durch
eine andere Regel, die einfacher ist.
Abschlusseigenschaften hatten wir bei regulären Sprachen sehr viel
drüber gesehen, werden wir hier auch was drüber machen und wir werden
Kellerautomaten kennenlernen.
In Normalform gehen wir schrittweise vor.
Wir machen erst ganz einfache Sachen, nämlich wie wir Epsilon
-Produktionen loswerden können.
Die sind strikt gesehen gar nicht erlaubt in Typ-2-Sprachen, werden
aber in der Praxis oft betrachtet.
Und wir werden erklären, warum das kein Problem ist, weil wir nämlich
solche Epsilon-Produktionen auch wieder loswerden können.
Dann gibt es spezielle Produktionen, die eine Variable in eine andere
umbenennen, die können wir uns komplett sparen.
Und mit den beiden Techniken wird es dann relativ einfach, eine erste
wichtige Normalform herzustellen, nämlich die Chomsky-Normalform.
Da sind die einzigen Produktionen, die erlaubt werden, Variable wird
abgeleitet zu einem Terminalsymbol oder Variable wird abgeleitet zu
genau zwei Variablen.
Und dann werde ich noch kurz die Greibach-Normalform vorstellen, da
wir nicht viel darüber sagen, weil die nicht so wichtig ist.
Also Epsilon-Elimination.
Das sieht ja sehr formal aus, diese Formel.
Also was wir hier behaupten, für jede Grammatik, wo die Produktionen
die Form haben, Variable, wird abgeleitet zu Folge von Variablen oder
Terminalsymbolen, gibt es auch eine Grammatik, die die gleiche Sprache
akzeptiert und strikt vom Typ 2 ist.
Und nach unserer Definition heißt das, die einzige Epsilon-Produktion,
die erlaubt ist, ist Startsymbol wird abgeleitet zu Epsilon und auch
nur dann, wenn das Startsymbol auf keiner rechten Seite vorkommt.
Und so eine Transformation werden wir kennenlernen.
Ich gebe hier im Prinzip einen Algorithmus an, von dem wir dann
beweisen müssen, dass er das tut, was wir wollen.
Der besteht aus mehreren Phasen.
In der ersten Phase berechne ich erstmal alle Variablen, aus denen
sich das leere Wort ableiten lässt.
Diese Menge nenne ich Vy.
Wie finde ich die?
Ich sage, solange es eine Produktion gibt,
meine ich immer eine Produktion, die ich noch nicht angeschaut habe.
Und zwar eine Produktion X nach Alpha, mit der Eigenschaft X habe ich
noch nicht in Vy drin.
Und Alpha besteht nur aus Variablen in Vy.
Füge ich X zu Vy hinzu.
Jetzt eine kleine Verständnisfrage, gegen das Einschlafen.
Das klingt irgendwie auf den ersten Blick paradox.
Am Anfang ist Vy leer.
Wie soll es überhaupt am Anfang eine Produktion geben dieser Form?
Wie sehen die am Anfang aus, diese Produktionen?
Könnte mir das jemand sagen?
Alpha in Vy-Stern.
Am Anfang sind das genau die Produktionen nach Y.
Aber später können das eben auch Produktionen sein, in denen Variablen
in Vy vorkommen.
Weil ich weiß ja schon, alles was in Vy ist, daraus kann ich Y
herleiten.
Und wenn ich jetzt Produktionen habe, in denen nur Sachen aus Vy
vorkommen, kann ich aus jeder dieser Variablen Y herleiten, kriege ich
Y.
Und deshalb ist das dann auch so eine Y-Produktion.
Diese Vorverarbeitung liefert uns jetzt das folgende.
Das habe ich hier jetzt als so eine Assertion formuliert.
Ich behaupte, Vy ist jetzt genau die Menge der Variablen, aus denen Y
herleitbar ist.
Das könnte man jetzt durch einen Induktionsbeweis beweisen, werde ich
aber, wenn ich das richtig erinnere, nicht tun.
Dann kommt der wichtigste Schritt.
Ich schaue mir jetzt Produktionen der Form X nach Alpha-Y-Beta an.
Wobei Y so eine Y-Variable ist.
Und dann führe ich eine zusätzliche Produktion ein, X nach Alpha-Beta.
Ich habe hier zugeschrieben und ich habe die vorher noch nicht
eingefügt.
Das brauche ich, damit ich hier keine Endlosschleife kriege, dass ich
Sachen irgendwie mehrfach einfüge.
Aber das Wichtigste hierbei ist, ich füge hier einfach Produktionen
hinzu.
Und das macht nur Sinn, wenn ich dabei die Sprache nicht verändere.
Und das ist eine Invariante.
Wo man dann im Prinzip auch noch zeigen muss, dass das eben eine
Schleifeninvariante ist, die immer erfüllt ist.
Ich weiß nicht, ob wir da im Detail dazu kommen.
Aber es ist schon recht intuitiv, weil ich füge hier eine Produktion
hinzu, die sicherlich keine neuen Ableitungen zulässt.
Weil ich kann immer, wenn ich diese Ableitung mache, AY-Beta...
Nee, Quatsch.
Also immer wenn ich diese Ableitung mache, hätte ich ja auch diese
dann nehmen können und dann aus dem Y das leere Wort herleihen.
Und damit ändere ich nichts.
Ich habe also jetzt keine zusätzlichen Wörter produziert und da ich
hier nur Produktionen hinzunehme, habe ich auch sicherlich nicht
weniger produziert.
Also diese Invariante ist ziemlich klar eigentlich.
Und jetzt habe ich ja zunächst mal die Y-Produktion noch gar nicht
eliminiert, sondern ich habe nur Produktionen hinzugefügt.
Übrigens unter anderem können hierbei auch neue Y-Produktionen
entstehen, wenn nämlich Alpha und Beta leer sind.
Was ich dann mache ist, jetzt schmeiße ich einfach alle Y-Produktionen
hinaus.
Das ist nicht ganz eine Invariante, dabei wird die Sprache
möglicherweise leicht verändert und zwar was passieren könnte, ist,
dass ich das leere Wort verliere.
Weil es ist sicherlich so, wenn ich alle Produktionen herausschmeiße,
bei der das leere Wort auf der rechten Seite steht, dann kann ich das
leere Wort nicht mehr produzieren.
Weil die Behauptung ist, das ist die einzige Änderung, die
stattfindet.
Und das liegt einfach daran, dass wenn ich hier eine Y-Produktion
streiche, dann ist das V in VY.
Und ich habe aber an allen Stellen, wo ich das möglicherweise brauchen
kann, diese Produktionen hinzugefügt, die ich dadurch ersetzen kann.
Also ein detaillierter Beweis müsste jetzt sagen, zeige mir eine
beliebige Ableitung eines Wortes, das Y-Produktionen verwendet mit der
ursprünglichen Grammatik und ich gebe dir jetzt eine neue Ableitung,
die diese Y-Produktion nicht verwendet, sondern stattdessen diese neu
eingeführten verwendet.
Und das kann man sich überlegen, dass das immer geht, durch einen
Induktionsbeweis.
Und dann muss ich noch eine Nachverarbeitung machen.
Falls das Y in der Sprache war, füge ich ein neues Startsymbol S'
hinzu, die Produktion S'Y und die Produktion S'S.
Das ist nötig, weil für Typ 2 Grammatiken erlaube ich ja nur Y
-Produktionen von S vom Startsymbol aus und die darf aber auf keiner
rechten Seite stehen.
Unsere ursprüngliche Grammatik war aber tatsächlich so, dass S auch
auf der rechten Seite stehen durfte, deshalb füge ich halt das neue
Startsymbol hinzu, das garantiert auf keiner rechten Seite erscheint.
Und dann darf ich das Ganze machen.
Okay.
Was vielleicht noch eine ganz nette Übung ist, wir haben hier so einen
iterativen Algorithmus gefunden, angegeben der Vy bestimmt.
Und naiv implementiert würde der immer und immer wieder durch die
Produktionenmenge scannen.
Dann kann man einen Linearzeitalgorithmus angeben, dessen Laufzeit
linear ist in Anzahl Variablen plus Summe der Länge der Produktionen.
Also sozusagen die Beschreibungskomplexität dieser Grammatik.
Und oh Wunder, das ist ein Graphen-Algorithmus.
Hat was mit Graph-Terraversierung zu tun, aber müsste man sich dann
noch überlegen.
Habt ihr die schon gestellt, die Aufgabe?
Okay.
Fragen zu diesem Epsilon-Eliminations-Algorithmus?
Machen wir mal ein Beispiel.
Hier ist eine Grammatik für die Sprache A-Stern, B-Stern.
Wir haben S nach A, B.
Die Variable Groß A steht, darf As produzieren.
Die Variable Groß B darf Bs produzieren.
Und da hier A-Stern, B-Stern steht, dürfen wir aber auch nichts
produzieren.
Das ist ja eine reguläre Sprache und es ist auch fast eine reguläre
Grammatik, außer dass wir am Anfang dieses S nach A, B angegeben
haben.
Gucken wir uns den Algorithmus an.
Der berechnet erstmal die Epsilon-Produktionen.
Am Anfang ist V-Epsilon leer.
Dann sieht er A-Epsilon.
Folglich kann aus A das leere Wort hergeleitet werden.
Ich tue das A rein, er sieht das B-Epsilon, er tut das B rein und
jetzt sieht er hier S nach A, B.
Das sind beides Variablen in V-Epsilon.
Folglich passt das auch hier auf diese Bedingung und ich gebe auch
noch das S ein.
Also sind alle meine Variablen in Epsilon-Variablen.
Machen wir mal weiter.
Hier wieder die Grammatik, die Produktionen.
Das V-Epsilon habe ich jetzt berechnet.
Jetzt kommt diese Hauptschleife, die Produktionen der Form Alpha-Y
-Beta mit Y in V-Epsilon bestimmt und dann dieses X nach Alpha-Beta
hinzufügt.
Und jetzt gucken wir mal an, was der sich da sucht.
Jetzt geht man systematisch einfach durch die Produktionen durch.
Zum Beispiel nimmt man sich jetzt die Produktion A nach AA.
Was war die Bedingung?
Da muss doch eine Epsilon-Variable drin vorkommen.
Mehr war das nicht.
Alpha ist gleich klein a, Beta ist das leere Wort, Y ist a.
Und dann sage ich, aha, dann gilt diese Regel, dann kann ich direkt
auch das Terminalsymbol A ableiten aus dem Groß A.
Völlig analog.
Diese Produktion B nach BB, da kann ich das Groß B ersetzen und nur
ein B nach klein b als Produktion machen.
Dann auch S nach AB.
S nach AB nehme ich jetzt mehrmals, nämlich in zwei verschiedenen
Formen.
Einmal ist Alpha gleich a, die Variable ist B und Beta ist das leere
Wort.
Dann entsteht diese Produktion.
Ich lasse das a weg.
Und das andere Mal ist Alpha das leere Wort, die Epsilon-Variable ist
a und Beta ist gleich b.
Ich glaube es ist genau umgekehrt.
Also man kann dieses a, b zweimal matchen.
Das ist hier wichtig, weil ich dadurch zwei verschiedene Produktionen
kriege, S nach B und S nach A.
Jetzt habe ich hier dieses S nach A erzeugt, aber das ist ja auch
wieder so eine Epsilon-Produktion.
Deshalb wird daraus ein S Epsilon und das gleiche hier aus dem S B
wird ein S Epsilon.
Also was ich jetzt insgesamt habe ist meine alten Produktionen, sowie
die Produktionen A nach A, B nach B, S nach B und S nach A.
Und S nach Epsilon.
Fragen zu dem Beispiel soweit?
Okay, also machen wir weiter.
Also bis hierhin habe ich jetzt zusätzliche Produktionen eingefügt,
die Sprache nicht geändert.
Aber wir sehen, ich habe die Epsilon-Produktionen nicht etwa
eliminiert, sondern ich habe zusätzliche hinzugefügt.
Klingt jetzt auf den ersten Blick nicht so zielführend, aber ich habe
jetzt so viel Zeug hinzugefügt, dass ich mir jetzt leisten kann,
einfach alle Epsilon-Produktionen hier wegzulassen, die rot
markierten.
Da habe ich das Kind ein bisschen mit dem Bader ausgeschüttet, weil
das leere Wort ist in der Sprache A-Stern, B-Stern, aber nicht mehr in
der Sprache, die von dieser Grammatik akzeptiert wird.
Aber das wird jetzt im letzten Schritt repariert, wo ich S Strich zum
neuen Startsymbol mache.
Und die Produktionen S Strich nach Epsilon und S Strich nach S
hinzufüge.
Fragen dazu?
So, jetzt muss man von diesem durchaus schon etwas komplexeren
Algorithmus einen Korrektheitsbeweis machen, den werde ich nur
skizzieren.
Ich habe hier sogar Skizzen-Skizze geschrieben, insofern als ich über
einige Sachen wirklich relativ kurz hinweggehe.
Also zunächst muss man eben zeigen, dass für jedes X in V Epsilon auch
tatsächlich Epsilon ableitbar ist.
Das kann man machen, indem man so eine Ableitung angibt.
Dann muss ich, wenn aus irgendeiner Variable Epsilon ableitbar ist,
zeigen, dass X dann auch in V Epsilon sein muss.
Das kann man durch Induktion über die Ableitungslänge.
Die Schleifeninvariante habe ich schon darüber gesprochen, warum die
gilt.
Also die für diese Schleife, die Produktionen hinzufügt.
Ich muss die Terminierung beweisen, da werde ich gleich noch darauf
eingehen.
Dann ist eben ganz wichtig, dass das Entfernen der Epsilon
-Produktionen L von G nicht verändert, mit Ausnahme von dem leeren
Wort, das dann möglicherweise entfernt wird.
Da kann man eine Induktion über die Ableitungslänge machen.
Ich gucke mir eine Ableitung an.
Ich habe eine Satzform Gamma X Delta, die abgeleitet wird zu Gamma
Alpha Y Beta Delta.
Und dann eine Epsilon-Produktion anwendet, die Y durch Y ersetzt.
Und die kann ich ersetzen durch eine kürzere Ableitung, indem ich
direkt X nach Alpha Beta die neu eingeführte Produktion hinzufüge.
Da muss man allerdings ein bisschen aufpassen, weil hier steht das
jetzt so, dass die direkt nebeneinander stehen.
Da muss man erst mal zeigen, dass man OBDA annehmen kann, dass die
direkt hintereinander stehen oder eben noch allgemeinere
Teilableitungen zulassen.
Und das habe ich hier nicht komplett ausformuliert.
So jetzt Terminierungsbeweis.
Also wir haben ja hier eine Menge von Produktionen, wenden eine
bestimmte Regel an und immer wenn die anwendbar ist, fügen wir eine
neue Produktion hinzu.
Da muss man aufpassen, dass das überhaupt terminiert.
Es könnte ja sein, dass man immer neue Produktionen baut.
Und das kann nicht passieren aus zwei Gründen.
Also zunächst mal dadurch, dass wir hier diese Bedingung haben, dass X
Alpha Beta noch nicht in der Produktionenmenge drin sein kann, kann
ich eine Produktion nicht beliebig oft hier verwenden.
Ich kann nur für alle Epsilon-Variablen, die darin vorkommen, einmal
so ein Pattern Alpha Epsilon-Variable Beta nehmen und dadurch eine
neue Produktion erzeugen.
Und danach kann aber diese Produktion selber nicht mehr aktiviert
werden.
Jetzt könnte man sagen, das ist noch kein Terminierungsbeweis, weil es
werden ja auch neue Produktionen erzeugt, die selber wieder in diesem
Pattern sein können.
Aber der Trick ist, neue Produktionen produzieren kürzere
rechte Seiten.
Oder anders formuliert, ich schaue mir jetzt die maximale Länge einer
rechten Seite an und sehe jetzt, neue Produktionen haben immer Länge
auf der rechten Seite, die kleiner ist als diese Maximallänge.
Das heißt, nach endlich vielen Schritten kann ich auf Produktionen
maximaler Länge keine Regel mehr anwenden.
Und auch die neuen Produktionen, die da eingefügt wurden,
haben halt kürzere Länge.
Damit ist sozusagen die Maximallänge abgehakt, dann gehe ich zur
nächsten Länge.
Ich kann da Sachen anwenden, es werden neue Produktionen erzeugt, aber
nur solche, die noch kürzer werden und so weiter.
Und ich habe ja immer nur endlich viele Produktionen begrenzter Länge,
ich kann also auch nicht beliebig viele neue Produktionen erzeugen,
weil irgendwann habe ich alle Produktionen dieser Länge, die es
überhaupt gibt, erzeugt, wenn ich annehmen würde, dass es unendlich
viele sind und dann terminiert das zwangsläufig.
Fragen zur Terminierung von dem Algorithmus.
So, also das war jetzt eine eigentlich relativ simple Normalform, die
halt nur Epsilon-Produktionen los wird.
Jetzt schauen wir uns die nächst einfache Form von Produktionen an.
Das könnte Variablen nach Terminalsymbol sein, aber die wollen wir
nicht wirklich eliminieren, weil die gibt es sogar in Typ 3.
Und die sind irgendwie sinnvoll, aber es gibt Produktionen der Form
Variable wird umbenannt in eine andere Variable.
Und das ist zwar manchmal nützlich zur Formulierung von Grammatiken,
ist aber nicht wirklich notwendig.
Und die können wir eliminieren.
Und dafür wenden wir wieder einen Algorithmus an, der in mehreren
Schritten die Dinger losführt.
Zunächst mal, man kann das wieder als eine Vorverarbeitung sehen,
eliminieren wir zyklische Umbenennungen.
Ja, der Form A wird umbenannt in B, B wird in C umbenannt, C wird in A
umbenannt.
Da können wir dann hergehen, wenn es so einen Kreis gibt, Y1 bis Yk.
Wenn wir einfach nur Y1 überleben lassen und alle anderen Variablen
eliminieren.
Das heißt, überall in der Grammatik werden jetzt Y2 bis Yk durch Y1
ersetzt.
Dann könnten möglicherweise noch Umbenennungen entstehen, das heißt,
entstehen garantiert so der Form Y1 nach Y1.
Aber die führen ja offensichtlich zu nichts.
Die kann ich ja in jeder Ableitung, in der so eine Umbenennung einer
Variable in sich selbst vorkommt, einfach weglassen.
Und man kann sich auch wieder relativ leicht überlegen, dass durch
diese Kontraktion von Kreisen die Sprache nicht verändert wird.
Weil ich habe einfach hier mehrere Synonyme durch ein einziges Wort
ersetzt.
Und wenn ich das beliebig oft mache,
ist dieser Umbenennungsgraf, den ich hier definiert habe, kreisfrei
geworden.
Und übrigens wieder in Bezug zur Algorithmen-1-Vorlesung.
Wenn ich das hier effizient machen will, also nicht immer wieder
Kreise suchen, was Linearzeit braucht in der Größe des
Umbenennungsgrafen, die ersetzen und dann muss ich wieder suchen, was
dann zu mindestens quadratischer Worst-Case-Laufzeit führt, kann ich
auch einmal die starken Zusammenhangskomponenten des
Umbenennungsgrafen identifizieren.
Das geht in Linearzeit mit Tiefensuche.
Und dann einfach, statt nur diese Kreise zu ersetzen, ganze starke
Zusammenhangskomponenten zu ersetzen durch einen beliebigen
Repräsentanten der starken Zusammenhangskomponente.
Fragen dazu?
Genau.
Wenn ich das gemacht habe, kann es immer noch solche
Einheitsproduktionen geben.
Das definiert dieser Umbenennungsgraf allerdings einen gerichteten
azyklischen Graphen.
Und da kann ich jetzt auch eine Normalisierung vornehmen.
Ich nehme mir einfach eine
beliebige Variable, die hier in diesem Graphen irgendwie mittendrin
erscheint.
Das heißt, hier auf der rechten Seite können auch noch andere Sachen
als diese Umbenennungen entstehen.
Da gucke ich mir aber jetzt nur Sachen an, wo die rechte Seite größer
ist als 1.
Und jetzt kann ich so eine Variable hier eliminieren, indem ich
einfach sage, alle Variablen, die umbenannt werden können in diese
Variable, erben einfach sämtliche der rechten Seiten hier.
Also wenn ich zum Beispiel A1 in B umbenannt nennen konnte, dann füge
ich zusätzliche Produktionen A1 nach X1, A1 nach X2, A1 nach Xm.
Und danach gibt es keine Variable mehr, die in B umbenannt wird.
Die alten Produktionen hier muss ich natürlich erhalten.
Aber ich habe dann sozusagen eine Variable aus diesem
Umbenennungsgraphen eliminiert.
Und wenn ich das in umgekehrter topologisch sortierter Reihenfolge
mache, wieder Bezug auf Algorithmen 1, dann nehme ich immer eine
Variable, und das geht immer, die als rechte Seite keine Umbenennung
mehr vornimmt, und eliminiere alle Umbenennungen in diese Variable.
Das ist, was ich hier gemeint habe.
Ich nehme immer eine Variable, deren rechte Seiten keine Umbenennungen
mehr darstellen, und eliminiere alle Umbenennungen der Form Variable
in diese Variable, indem ich hier diese Abkürzungen einfüge.
Das kann ich sukzessive so weit machen, bis es überhaupt keine
Umbenennungen mehr gibt.
Weil aus B macht jetzt keine Umbenennung mehr, sondern nur noch diese
anderen Sachen.
Und die Umbenennungen in B habe ich eliminiert, und das kann ich
sukzessive machen.
Und wenn ich immer eine nehme, die auf ihrer rechten Seite selber
keine Umbenennungen hat, kann ich immer finden, zum Beispiel wenn ich
das in umgekehrter topologischer Reihenfolge mache, dann sind sie
irgendwann alle eliminiert.
Fragen dazu?
Jetzt der eigentliche Hauptsatz der heutigen Vorlesungshälfte.
Wir gucken uns eine regelrechte Normalform an.
Man sagt, eine Grammatik G' ist in Chomsky-Normalform, falls ihre
Produktionen nur zwei mögliche Formen haben.
Entweder Variable wird abgeleitet zu Terminalsymbol, ein einziges,
oder Variable wird abgeleitet zu zwei Variablen.
Und der Satz lautet, zu jeder kontextfreien Grammatik G, die Epsilon
nicht produziert, gibt es eine Grammatik G' in Chomsky-Normalform,
sodass die Sprache von G' die gleiche ist wie die Sprache von G.
Der Beweisansatz ist nicht überraschend, wir verändern schrittweise
die Grammatik G.
Und die Invariante wird sein, dass dabei die Sprache selber
unverändert bleibt.
Wir machen jetzt als Vorverarbeitung wieder, benutzen wir als
Unterprogramme das, was wir schon gemacht haben.
Wir eliminieren erstmal alle Epsilons, dann eliminieren wir alle
Einheitsproduktionen.
Dann habe ich immer noch keine Chomsky-Normalform, aber das
vereinfacht die Aufgabe, die ich jetzt habe.
Jetzt eliminiere ich gemischte rechte Seiten.
Das heißt rechte Seiten, auf denen sowohl Terminalsymbole vorkommen,
als auch Nicht-Terminalsymbole.
Und was ich dafür mache ist, für jedes Terminalsymbol A in Sigma,
führe ich eine neue Variable Va ein, sowie eine Produktion Va nach A.
Das ist schon mal gut, weil die genügt der Chomsky-Normalform, diese
Produktion, da kann ich also nichts falsch machen.
Und da Va auch sonst nirgendwo verwendet wird, das ist ja eine neue
Variable, verändere ich damit auch nicht die Sprache.
Und jetzt schaue ich mir jede einzelne Produktion L, R und P an.
Und wenn A jetzt auf der rechten Seite dieser Produktion vorkommt und
die rechte Seite größer gleich 2 ist, dann ersetze ich einfach die As
durch Va in dieser Produktion.
Kann mir jemand erklären, warum ich das nur für die rechten Seiten
größer gleich 2 mache?
Weil die rechten Seiten der Größe 1 sind ja schon in Chomsky
-Normalform.
Also wenn das Terminalsymbol A auf der rechten Seite vorkommt und da
nichts anderes vorkommt, ist das schon Chomsky-Normalform.
In allen anderen Fällen ersetze ich das A durch das Va.
Damit verändere ich die Sprache nicht, weil ich aus dem Va ja genau
das A herleiten kann.
Das heißt, in jeder Ableitung, in der das Ding vorkommt, muss ich halt
nur einen zusätzlichen Schritt einfügen, wo aus diesen Va jeweils das
A wieder abgeleitet wird.
Danach habe ich meine Produktionenmenge so vereinfacht, dass sie die
Form haben, Variable wird ersetzt durch ein einzelnes Terminalsymbol
oder Variable wird ersetzt durch eine Folge von Nicht
-Terminalsymbolen.
Und ich weiß sogar, dass diese Folge mindestens Länge 2 hat, weil die
Umbenennungen habe ich ja schon eliminiert und die Y-Produktionen
auch.
Hier mal ein Beispiel, wenn ich eine Produktion der Folgeform hatte,
linke Seite nach A, X, B, B, C, Y, dann ersetze ich einfach, und ich
sage jetzt, Groß-A ist mein Va, Groß-B ist mein Vb, Groß-C ist mein
Vc, dann ersetze ich diese Produktion durch die Produktion, L wird
ersetzt durch Groß-A, X, Groß-B, Groß-B, Groß-C, Y.
Noch Fragen dazu?
So, jetzt habe ich immer noch lange rechte Seiten, die allerdings nur
noch aus Variablen bestehen.
Und jetzt sage ich wieder, solange es solche Dinge gibt, und zwar
solche mit mindestens 3 Variablen auf der rechten Seite, die mit 1
habe ich bereits eliminiert, die mit 2 stören mich nicht, weil die die
Chomsky -Normalform bereits erfüllen, also solange es zu lange rechte
Seiten gibt, spalte ich die sozusagen auf, diese langen Produktionen.
Ich hole mir wieder eine neue Variable C und ersetze diese lange
Produktion jetzt durch zwei Produktionen, also das hier war Y1 bis Yk,
jetzt definiere ich C als eine Abkürzung für Y1, Y2 und ersetze Y1, Y2
durch C.
Das heißt, ich habe im Prinzip eine lange Produktion in zwei kurze
aufgespalten.
Gucken wir uns das wieder an einem Beispiel an, wenn ich eine
Produktion L nach W, X, Y, Z habe, füge ich jetzt eine neue Variable A
ein, die ich zu W, X ersetze, und dann ersetze ich das hier, das W, X,
Y, Z halt durch A, Y, Z.
Und das kann ich sukzessive machen, das ist ja jetzt immer noch eine
lange Produktion.
Dann denke ich mir noch eine neue Variable B aus, die zu A, Y
abgeleitet wird.
Und dann habe ich L, B, Z, B, A, Y und A, W, X, das sind alles Chomsky
-Normalform -Produktionen.
Fragen dazu?
So, gucken wir uns mal ein ausführlicheres Beispiel an.
Eine ganz einfache Form unserer Klammerausdruck-Grammatik, die nur ein
einziges Nicht-Terminalsymbode E hat.
Die hat jetzt zunächst mal gemischte Produktionen, wo Sternchen,
Klammerauf, Klammerzu und Plus sind ja Terminalsymbole.
Da füge ich jetzt halt Variablen V+, V, Stern, V, Klammerauf und V,
Klammerzu ein und ersetze diese Terminalsymbole hier durch diese
Variablen und füge eben Produktionen hinzu, die V+, V, Stern, Stern,
V, Klammerauf, Klammerauf und V, Klammerzu, Klammerzu ersetzen.
Das war diese Vorverarbeitung, Elimination von gemischten rechten
Seiten.
Die Grammatik enthält gar keine Umbenennungen, die brauche ich also
nicht eliminieren.
Die enthält auch keine Epsilons, die brauche ich auch nicht
eliminieren.
Jetzt kommt dieser Hauptschritt, der die langen Produktionen durch
kürzere ersetzt.
Ich habe das jetzt mal so geschrieben, also aus dem E, V+, E wird
jetzt C nach E, V+, und E nach CE.
Damit habe ich diese Produktion verarztet.
Aus dem E, V, Stern, E wird D nach E, V, Stern und E nach DE.
Aus dem E nach V, Klammerauf, E, V, Klammerzu wird F nach V,
Klammerauf, E und E nach F, V, Klammerauf.
Was haben wir noch?
Die war lang, die haben wir ersetzt, die war lang, die haben wir
ersetzt, die war lang, die haben wir ersetzt.
Das ist bereits eine Chomsky-Normalformproduktion.
Und dann bin ich jetzt fertig.
Fragen zu dem Beispiel.
Dann gibt es noch die Greibach-Normalform.
Die will ich einfach nur mal erwähnen.
Also zu jeder kontextfreien Grammatik G, die Y nicht erzeugt, gibt es
eine Grammatik G' in Greibach-Normalform.
Und das ist nichts anderes, als dass die Produktionenmengen alle die
Form haben müssen.
Variable wird abgeleitet zu Terminalsymbol und dann Folge von
Variablen.
Das ist eine ganz natürliche Verallgemeinerung von Typ-3-Grammatiken.
Typ-3-Grammatiken haben die Form, Variable wird abgeleitet zu
Terminalsymbol und dann Null- oder Einvariablen-Symbol.
Jetzt sind mehrere Variablen-Symbole erlaubt, aber es wird sozusagen
bei jeder angewandten Produktion tatsächlich ein Nicht-Terminal-Symbol
erzeugt.
Und dahinter kommen nur Variablen.
Das ist ganz nützlich in einigen Beweisen, vor allem im Zusammenhang
mit Kellerautomaten.
Aber da wir da sowieso nicht ins Detail einsteigen werden an der
Stelle oder das anders machen, will ich das hier nur erwähnen.
Also man kann jetzt einen Algorithmus angeben, der sehr ähnlich
funktioniert wie der für die Chemsky-Normalform, der halt geeignete
Ersetzungen vornimmt und dann diese Greibach-Normalform erzeugt.
Aber ich denke, das ist fast etwas, was man als Übungsaufgabe stellen
könnte.
Wenn man wollte, muss man aber.
Fragen zur Greibach-Normalform?
So, Pumping-Lemmer machen wir nächstes Mal, oder?
Dann gehen wir jetzt zur Übung über.
Gut.
Wir fangen die Übung an, nochmal mit der Minimierung von normalen
Automaten.
Also nochmal zurück zu regulären Sprachen.
Bei der Automatenminimierung war ja auch der Algorithmus aus der
Vorlesung relativ abstrakt.
Nicht sehr nah an der Ausführung, wie man es jetzt wirklich auf einem
Blatt durchrechnen würde.
Müsste man das in der Übung machen.
Der Automat hier, der ist auch schon auf der Vorlesungs-Homepage, weil
das ist im Endeffekt der Automat, den wir in der letzten Übung gebaut
haben.
Da hatte ich ihn auf Papier gezeichnet, relativ spontan und er sah
ziemlich anders aus.
Aber im Endeffekt ist das der Automat, den wir mit der Nerode-Relation
erzeugt haben, als wir gefragt haben, alle Wörter, die als
drittletzten Buchstaben in A haben.
Also dieser Automat akzeptiert alle Wörter, die als drittletzten
Buchstaben in A haben.
Leider sind meine akzeptierenden Zustände nicht mehr ganz so gut
sichtbar, aber die, die hier diesen breiten Rand haben, sind die
akzeptierenden Zustände.
Wir haben den gebaut über die Nerode-Relation, deswegen ist der
natürlich minimal.
Was man aber machen kann, ist einfach die akzeptierenden Zustände
verändern.
Und jetzt kann man sich überlegen, muss der Automat ja nicht mehr
minimal sein.
Oder zum Beispiel, auch wenn man eine Potenzmengen-Konstruktion macht
aus einem nicht-deterministischen Automat, der Automat muss nicht mehr
minimal sein danach.
Wir würden aber ganz gern immer mit minimalen Automaten arbeiten,
deswegen müssen wir die minimieren und dazu haben wir in der Vorlesung
den Algorithmus kennengelernt.
Und zwar geht der Algorithmus davon aus, er sucht Zustände, die nicht
gleich sind und alle, die dann noch übrig bleiben, also die gleich
sind, die kann man kombinieren.
Hier haben wir jetzt mal eine Tabelle gemacht, wo wir eben das
markieren können.
Zu jeder Zustandskombination gibt es einen Eintrag, hier zum Beispiel
BAB und BBA.
Und hier steht dann entweder was drin, wenn sie nicht gleich sind oder
nichts drin, wenn sie gleich sind.
Und wenn da was drin steht, dann schreiben wir da immer den Zeugen
rein, also ein Wort, das wenn man es in dem einen Zustand eingibt, in
einem Endzustand landet und in einem anderen Zustand eingibt, nicht im
Endzustand landet.
Gut, also fangen wir mal an.
Endzustände sind schon mal ganz einfach.
Das ist jetzt das Erste, was wir machen.
Jede Kombination von einem Endzustand zu einem Nicht-Endzustand, da
schreiben wir immer direkt mal das leere Wort rein.
Genau, gut, dann geht es weiter.
Wir schauen jetzt für jedes dieser Kästchen im Endeffekt an, können
wir was reinschreiben, das ein Zeichen länger ist.
So, wir vergleichen BBB, BBA.
Die Ziele, da wissen wir noch nicht so viel drüber, die könnten alle
gleich sein, also können wir noch nichts reinschreiben.
Wir vergleichen hier, also ich gebe im Endeffekt hier diese erste
Spalte runter.
Auch hier, die Ziele könnten theoretisch noch alle gleich sein, da
können wir noch nichts reinschreiben.
Das machen wir ein bisschen, bis wir hier unten auf diese Zelle kommen
und sehen hier, wenn wir in BAA ein A eingeben, dann landen wir in
einem Endzustand.
Wenn wir in BBB ein A eingeben, dann landen wir nicht in einem
Endzustand.
Das heißt, diese zwei Zustände sind auf jeden Fall unterschiedlich.
Und zwar, weil dieser Endzustand hier unterschiedlich ist zu diesem
BBA hier.
Also hier kommen wir in BBA und hier kommen wir in den Endzustand,
hier sehen wir, die zwei sind unterschiedlich.
Also was wir machen ist, wir haben hier das A genommen und wir hängen
das einfach dran an den Zeugen, den wir hier schon haben.
Also hier wissen wir, AAA und BBA sind unterschiedlich, weil sie sich
beim Epsilon anders verhalten.
Also nehmen wir hier das Zeichen, das wir hier gebraucht haben und
hängen dieses hier an.
Das ist jetzt gerade noch etwas witzlos, aber später macht es ein
bisschen was aus.
Gut, jetzt will ich euch nicht quälen und alle anderen hier weiter
abgehen, das ist ziemlich langsam alles.
Und wir zeigen einfach, BAA ist der einzige Zustand, der zu einem
Endzustand führen kann.
Und jeder andere Zustand führt mit einem A eben nicht zu einem
Endzustand.
Das heißt, alle sind anders als BAA.
Und beim ersten Durchgang ist das alles, was wir finden.
Also haben wir eben diese ganzen A´s hier eingetragen und sagen, BAA
ist jetzt mal anders als alle anderen.
Dann gehen wir weiter.
Beim zweiten Durchlauf hier sind wir ganz glücklich und finden direkt
was.
Also wenn wir in BBB ein A eingeben, kommen wir zu BBA und wenn wir in
BBA ein A eingeben, kommen wir zu BAA.
Wir wissen aber schon von hier, dass BAA und BBA unterschiedlich sind.
Das heißt, wir können das hier direkt einfügen.
Und zwar machen wir wieder, bei einem A sind wir hier zu dem anderen
Zustand gekommen wie hier.
Also hängen wir ein A vorne dran an das, was hier steht, also an das
A, das uns hier zu einem anderen Zustand geführt hat.
Und wenn wir uns das jetzt anschauen, okay, wenn wir in BBB AA
eingeben, landen wir in BAA, sind also nicht akzeptierend.
Wenn wir in BBA zwei A´s eingeben, landen wir im akzeptierenden
Endzustand.
Das heißt, hier haben wir eben wirklich immer diese Zeugen, die wir in
dem Algorithmus auch verwendet haben.
Gut, ich will euch wieder nicht quälen, wir machen mal die ganze
zweite Iteration durch.
Hierbei sehen wir, dass BBA anders sind als diese, die jetzt blau
markiert sind.
Weil die beide mit dem A in diesen BAA-Zustand kommen, während alle
anderen mit einem A eben nicht in diesen BAA-Zustand kommen.
Also nicht in den Zustand, den wir jetzt schon unterschieden haben.
Genau.
Wir markieren das also hier.
Dass ich die jetzt schon gleich gefärbt habe, ist eigentlich nicht so
wichtig.
Wir können eigentlich noch nicht sagen, dass die sich genau gleich
verhalten.
Wenn wir es jetzt hier uns genau anschauen, dann sehen wir, dass die
sich gleich verhalten.
Also sie gehen beide mit einem A zu BAA und sie gehen beide mit einem
B zu BAB.
Das heißt, die sind wirklich gleich.
Aber im Algorithmus müssten wir sie noch weiterhin anschauen und
überlegen, sind die nicht vielleicht doch anders.
Aber hier färbe ich sie jetzt schon mal gleich ein, weil wir im
Endeffekt gesehen haben, dass sie gleich sind.
Und jetzt kommt nochmal eine Iteration.
In dieser Iteration finden wir jetzt nichts mehr.
Also wir gehen durch alle leeren Kästchen durch, überlegen, ob man
durch Anhängen von einem Zeichen zu unterschiedlichen Sachen kommen
kann.
Hier finden wir jetzt nichts mehr.
Und sobald wir einmal bei einer ganzen Iteration nichts finden, wissen
wir, dass wir fertig sind.
Das war auch ein kurzer Beweis aus der Vorlesung.
Die Idee ist so ein bisschen, es kann keine Zeugen der Länge 5 geben,
wenn es nicht auch Zeugen der Länge 4 gibt.
Weil ich ja dann zwischendurch in Zuständen landen würde, die sich
nicht unterscheiden.
Und dann später wieder in einem Zustand lande, der sich unterscheidet,
das geht nicht.
Also wenn die Wege unterschiedlich verlaufen, dann verlaufen sie die
ganze Zeit unterschiedlich und nicht irgendwann zusammen und gehen
wieder auseinander.
Das ist so ein bisschen die Intuition für den Beweis, muss man nochmal
in die Vorlesungsfolien schauen.
Gut, das wäre jetzt einmal das Ganze durchgelaufen.
Ich persönlich finde dieses Verfahren, immer diese ganze Tabelle
anzuschauen oder immer alle leeren Stellen anzuschauen, ein bisschen
umständlich.
Und deswegen, dann gibt es noch ein anderes Verfahren.
Achso, einmal muss man den Automat noch hinmalen.
Normalerweise ist das immer Pflicht bei solchen Aufgaben.
Gut, dann gibt es noch ein anderes Verfahren, das möchte ich an diesem
Graph kurz vorstellen.
Es macht im Endeffekt dasselbe, aber erleichtert so ein bisschen das
Bookkeeping, welche Sachen ich jetzt anschauen muss und welche schon
gleich sind und welche nicht gleich sind.
Wir machen dieselbe Tabelle, aber zusätzlich betrachten wir noch so
eine Aufteilung der Zustände und werden die immer weiter aufspalten.
Als erstes, wie vorher auch, Endzustände sind was Besonderes.
Endzustände spalten wir direkt vom Rest auf und fügen hier auch wieder
die ganzen Epsilon ein in die Tabelle.
In dem Fall ist jetzt der Endzustand Q0 und der unterscheidet sich von
allen anderen Zuständen.
Die anderen schreiben wir erstmal zusammen in eine Gruppe und färben
die in einer Farbe ein.
Jetzt können wir uns mit diesen Gruppen hier überlegen, was passiert
für diese Zustände, wenn wir ein A eingeben.
Und die Idee ist halt, Q3 geht für ein A in den Endzustand, alle
anderen bleiben irgendwie in dieser großen Gruppe hier.
Ich habe mal alle Pfeile eingezeichnet, alle anderen bleiben hier in
dieser Gruppe hier, Q3 geht raus.
Das heißt Q3 verhält sich anders als alle anderen Zustände in dieser
Gruppe.
Wir müssen also die Gruppe aufspalten in Q3 und alle anderen Zustände.
Dann mache ich das Ganze jetzt noch für ein B.
Also ich füge hier überall die As ein, weil bisher haben wir nur ein A
verwendet, um diese Gruppe aufzuteilen.
Gut, dann machen wir jetzt das Ganze für ein B, überlegen uns wieder
für jeden Zustand, wo gehen die Pfeile hin.
Und hier sieht man eben, Q1 und Q6 zeigen beide auf Q3, während die
anderen wiederum hier in dieser Gruppe drin bleiben.
Wir müssen also wieder diese Gruppe aufspalten und haben dann eine
Gruppe Q1, Q6 und eben diesen Rest von der Gruppe.
Das Interessante ist, dass Zustände, die hier schon einzeln stehen,
müssen wir überhaupt nicht mehr betrachten, weil die können sich ja
von nichts mehr abspalten.
Wir haben jetzt diese Gruppe hier aufgespalten.
Ich hoffe, man sieht das von den Farben her gut.
Das eine ist so ein helleres Grün, das andere ist ein bisschen
dunkleres Grün.
Hier muss man ein bisschen aufpassen, hier muss man jetzt nicht
zwangsweise B A eintragen, es kann sein, dass man manchmal nur B
einträgt.
Also wenn es jetzt hier zum Beispiel einen Pfeil gegeben hätte, der zu
Q0 geht, dann hätte man nur B eintragen müssen, da muss man ein
bisschen aufpassen.
Man muss sich anschauen, warum diese Ziele hier sich unterscheiden.
Hier ist es so, die Ziele unterscheiden sich, weil wir im Vorschritt
hier Q3 abgespalten haben.
Deswegen müssen wir zuerst ein B eingeben, um zu Q3 zu gehen und dann
ein A eingeben, um zu Q0 zu gehen, um uns zu unterscheiden.
Während es hätte auch hier einen Pfeil geben können, der zu Q0 geht,
dann hätten wir den Zustand nochmal ganz extra abspalten können
und hätten dann nur das B gebraucht.
Also man muss hier ein bisschen aufpassen, mit was für Zeugen man
reinschreibt.
Aber im Endeffekt ist es relativ einfach.
Gut, wir machen das Ganze einfachstur weiter.
Wir machen Pfeile.
Hier ist es jetzt so, aus dieser Dreiergruppe gehen alle in diese
Zweiergruppe bis auf die Q4, die bleibt in dieser Gruppe drin.
Das heißt, sie verhält sich anders als alle anderen, wir werden sie
abspalten.
Aus dieser Q1, Q6-Gruppe gehen beide Pfeile hier zu Q4, also in diese
größere Gruppe rein.
Wir müssen noch nichts tun.
Gut, wir haben also das Q4 jetzt abgespalten und jetzt machen wir das
Ganze nochmal, diesmal für B.
Wir machen die Pfeile, wir sehen, die Zweiergruppen verhalten sich
jeweils gleich.
Entweder sie gehen beide in einen anderen Zustand oder sie bleiben
beide in derselben Gruppe drin.
Das heißt, es ändert sich nichts.
Und in dem Verfahren müssen wir das jetzt nochmal machen, weil wir
haben noch nicht gesehen, dass bei einem A sich auch nichts ändert.
Jetzt machen wir das Ganze nochmal für A, es ändert sich wieder
nichts.
Und sobald sich die Anzahl der Terminalsymbole schrittelang nichts
verändert hat, sind wir fertig.
Also in dem Fall sind es jetzt, solange sich zwei Schritte nichts
geändert hat, also einmal für ein B und danach für ein A sich nichts
geändert hat, sind wir fertig.
Also hintereinander müssen die Schritte natürlich sein.
Wenn man jetzt mehr Terminalsymbole hätte, müsste man das natürlich
für jedes Terminal noch einmal prüfen, dass sich nichts verändert.
Also ich fange normalerweise alphabetisch durch, man kann keinen
Fehler machen.
In dem Fall war es jetzt natürlich schön, dass sich zuerst dieses...
also das Ergebnis ist auch ein bisschen konstruiert.
Also hier war erstmal ein B-Pfeil und als ich mir das Beispiel
überlegt habe und es hat alles länger gedauert, dann habe ich ihn
umbenannt und alles war schneller.
Also klar, es gibt einen schlaueren Anfang und es gibt einen
schlechteren Anfang.
Ein Tipp von mir ist, schaut euch an, was für Übergänge in den
Endzustand reingehen.
Weil unterscheiden kann man ja immer nur mit Pfaden, die zum
Endzustand hinführen.
Könnten wir?
Wenn wir jetzt hier einen Pfeil von Q1 nach Q3 hätten mit einem A,
dann wären sie in unterschiedlichen Dingern.
Wenn wir jetzt hier zwei Zustände hätten, die mit einem A zu Q0 gehen,
wären sie in der gleichen Gruppe.
Wir müssen hier nicht strikt abwechselnd, wenn wir das nicht machen
wollen, aber man macht es sich damit deutlich schwieriger, was diese
Zeugen hier angeht.
Ihr müsst damit rechnen, dass eine Frage irgendwann kommt oder dass in
der Klausur so eine Zeugentabelle gegeben ist und ihr die ausfüllen
müsst.
Und wenn man hier jetzt AA macht, dann macht es für die Zeugen das
später deutlich schwieriger.
Weil hier mussten wir jetzt nur überlegen, müssen wir den Schritt
vorher verwenden oder nicht.
Also müssen wir hier BA schreiben oder nur B.
Also haben wir diesen ersten Schritt verwendet.
Also wenn ihr euch daran erinnert, hier gehen die Pfeile zu Q3, wenn
sie zu Q0 gegangen wären, hätte ich gesagt, dass man nur B angeben
muss.
Solche Entscheidungen werden immer schwieriger, je weniger regelmäßig
ihr das macht.
Also dieses Verfahren, ich finde es einfach ein Tick praktischer, weil
man nicht diese Tabelle anschauen muss.
Und ich finde, diese Tabelle lenkt ein bisschen ab von dem Graph, den
man tatsächlich anschaut.
Während hier zeichnet man immer die Pfeile ein, was es so ein bisschen
graphmäßiger macht.
Aber es ist natürlich ein Layer on top auf diesem hier.
Und wenn dieses hier gefragt ist, kann es sein, dass man durch dieses
Verfahren das ein Tick schwieriger macht.
Und es kann durchaus sein, dass dieses hier gefragt wird.
Aber genau, überlegt euch einfach, welches Verfahren für euch am
besten ist.
Und wenn ihr die Verfahren beide gut anschaut und die vergleicht und
versteht, was zwei Verfahren unterschiedlich macht, dann lernt ihr
auch ganz, ganz viel über diese Automatenminimierung selber.
Das heißt, es lohnt sich, finde ich, die beiden Verfahren anzuschauen
und die zu vergleichen auch.
Gut, wir sind jetzt fertig.
Wir haben gesagt, diese zwei sind gleich, diese zwei sind gleich.
Wir zeichnen noch einmal den Automat hin.
Und dann ist man eigentlich fertig mit Minimierung.
Und ich gehe weiter an Logans für die Chomsky Normalform.
Gut, dann will ich die Chomsky Normalform mal einfach an einem
Beispiel durchrechnen.
Aber vielleicht erstmal noch mal ganz kurz zur Erinnerung.
Eine Grammatik ist in Chomsky Normalform, wenn jede Produktion
entweder ein Nicht-Terminal auf zwei andere Nicht-Terminale ableitet
oder auf ein einziges Terminal.
So wie das da steht, ist jetzt natürlich Epsilon nicht in der Sprache
drin.
Und man kann eben diese Ableitung vom Startsymbol auf Epsilon
zulassen.
Dann darf das Startsymbol aber auf keiner rechten Seite mehr
vorkommen.
Aber den Fall ignorieren wir jetzt erstmal.
Hier ist mal eine Beispielgrammatik mit fünf Nicht-Terminalen und drei
Terminalen.
Das Startsymbol kann auf Groß-A abgeleitet werden oder Klein-A Groß-B
oder Klein-A Groß-C und so weiter.
Und wir wollen diese Grammatik jetzt mal in Chomsky Normalform
bringen.
So als Beispiel, wie man das auf dem Übungsblatt machen könnte oder in
der Klausur.
Das waren jetzt vier oder fünf Schritte, wie das gerade vorhin in der
Vorlesung erklärt wurde.
Der erste war, Epsilon-Produktionen zu entfernen.
Dazu wurde diese Menge vor Epsilon bestimmt.
Alle Nicht-Terminale, die in beliebig vielen Schritten überhaupt mal
auf den Epsilon abgeleitet werden können.
Und dann wurden Produktionen von der Form ein Nicht-Terminal auf ein
Nicht -Terminal aus V-Epsilon und irgendwas anderes genommen.
Und zusätzlich die Regel ohne dieses Nicht-Terminal eingefügt.
Das heißt, wenn vorher Alpha-Y-Beta da stand, kommt jetzt noch die
Regel X nach Alpha-Beta dazu.
Das muss man eben so oft durchmachen, bis da alle Ersetzungen
vorgenommen sind.
Und dann als letztes noch alle Ersetzungsregeln, alle Produktionen,
die auf ein Epsilon ableiten, entfernen.
Und dann ist die Grammatik Epsilon-frei.
Das ist in dem Fall jetzt schnell gemacht, denn diese Grammatik ist
schon Epsilon-frei.
Aber im allgemeinen Fall muss man das halt machen.
Und auf dem Übungsblatt sind auch Epsilon-haltige Grammatiken.
Der zweite Schritt ist, zyklische Einheitsproduktionen zu ersetzen.
Also Einheitsproduktionen sind diese Produktionen der Form Nicht
-Terminal auf ein einziges Nicht-Terminal.
Und wenn wir uns jetzt diese Grammatik genauer anschauen, sehen wir,
dass es hier einen Zyklus gibt, von S nach A auf B auf S.
Und so kann man sich den ungefähr anschauen, wenn man sich mal die
ganzen Einheitsproduktionen hinschreibt, die Abhängigkeitskette.
Und diese Zusammenhangskomponente hier werden wir jetzt einfach
kontrahieren, indem die Nicht-Terminale auf dem Kreis vereinigt
werden.
Dann sieht die Grammatik so aus.
Also alle Produktionen von A und B werden jetzt an das S noch mit
drangehängt.
Deswegen hat das jetzt hier eine längere Liste der Produktionen.
Und natürlich können die Vorkommnisse von A und C hier auch durch S
ersetzt werden.
Die lassen sich ja beliebig im Kreis ableiten.
Und dann kommen wir hier bei diesem heraus.
Das sieht jetzt tatsächlich sogar etwas einfacher aus als vorher.
Und wir kümmern uns als nächstes um die nichtzyklischen
Einheitsproduktionen.
Es gibt hier nämlich immer noch zwei nichtzyklische
Einheitsproduktionen.
Und das ist im Grunde einfach nur Inlining von diesen Regeln.
Diese umgekehrt topologische Reihenfolge heißt im Grunde nur, dass man
da die Abhängigkeiten auflösen muss.
Also wenn man jetzt zuerst hier das C inlinen würde, dann müsste man
danach nochmal das D inlinen.
Und das ist dann irgendwie unnötig kompliziert.
Deswegen fängt man mit dem D an.
Und kopiert einfach diese Regeln hier rein.
Und kopiert dann diese Regeln da oben rein.
Und dann sieht das Ganze so aus.
Jetzt sind fast nur noch tatsächlich zugelassene Produktionen da.
Aber die sind auch zu lang und haben gemischte rechte Seiten.
Das ist der vierte Schritt.
Ich habe jetzt mal das Entfernen gemischter rechter Seiten und langer
Produktionen zusammengefasst.
Denn die sind beide sehr einfach.
Da muss man sich dann eben nur neue Nicht-Terminale definieren und das
irgendwie zusammenfassen.
Ob man da jetzt die linkesten beiden Nicht-Terminale immer zu einem
neuen Symbol zusammenfasst oder irgendwelche anderen, ist gar nicht so
wichtig.
Ich mache das normalerweise so, dass ich möglichst wenig neue Nicht
-Terminale definieren muss.
Auch einfach, weil die Grammatik dann besser auf die Folie passt.
Und am Ende kommt dann eben genau das hier raus.
Also jetzt wurde es im letzten Schritt von da oben zu hier unten noch
mal deutlich unübersichtlicher gefühlt.
Aber das ist jetzt tatsächlich die Chomsky-Normalform.
Wir haben hier unten Produktionen, die nur diese einzelnen Terminale
erzeugen, um eben diese gemischten Produktionen hier loszuwerden.
Aber ansonsten sind alle Regeln der Form zwei Nicht-Terminale oder ein
Terminal.
So sieht dann also unsere finale Grammatik in Chomsky-Normalform aus.
Gibt es dazu irgendwelche Fragen?
Dann würde ich vielleicht noch ganz gerne was zum Übungsblatt sagen,
zum aktuellen.
Da sind zwei Zusatzaufgaben drauf.
Die zweite davon gibt zehn Bonuspunkte und ein Eis für eine korrekte
Lösung.
Die ist etwas spannender.
Das Blatt ist leider noch dabei.
Ja, also auch bei den beiden Zusatzaufgaben, die Punkte zählen
natürlich nicht zu den Maximalpunkten, die dann wiederum für die
Berechnung an Klausurbonuspunkten berechnet gebraucht werden.
Also wir haben ja das System, dass für 25, 50 und 75 Prozent der
Übungspunkte gibt es immer einen Klausurbonuspunkt.
Und die Zusatzaufgaben sind dazu da, dass ihr euch verbessern könnt
gegenüber dem, was sonst normalerweise auf den Übungsblättern drauf
ist.
Das heißt, die werden für diese Grenzenberechnung nicht mit
einbezogen.
Aber die Punkte, die ihr da erreicht, zählen natürlich trotzdem.
Ja, bei der zweiten Zusatzaufgabe, da geht es darum, aus einem nicht
deterministischen Automaten direkt den minimalen deterministischen
Automaten zu konstruieren, ohne Umweg über die
Potenzmengenkonstruktion und auch ohne exponentielle Zeit
möglicherweise zu brauchen.
Also es gibt Automaten, die haben N Zustände als nicht
deterministische Automat, haben dann exponentiell viele Zustände im
Potenzmengenautomaten und der minimale deterministische Automat hat
wiederum nur N Zustände.
Da ist zum Beispiel,
ja kann man ein Beispiel machen, Wörter der Länge mindestens 3, kann
man einen nicht deterministischen Automaten konstruieren, der eine
Schleife im Startzustand hat mit dem gesamten Alphabet und dann drei
Zustände, noch weitere, die rübergehen.
Genau, ich kann den mal aufmalen.
Achso und vielleicht nebenher so ein bisschen das Interessante an dem
Problem ist natürlich, wir haben die Automatenminimierung gerade eben
gesehen, die lief ja immer so ein bisschen ab, dass man von den N
Zuständen ausgeht, während die Potenzmengenkonstruktion ja genau
andersrum vorgeht.
Die geht von den Startzuständen aus oder von dem Startzustand und
allem, was von dem Startzustand aus mit Y Übergängen erreichbar ist.
Und dieser neue Algorithmus müsste eben die so vereinen, dass man das
schön machen kann.
Also die Problematik ist halt, dass wenn die von der gleichen Richtung
ausgehen würden, dann könnte man die Minimierung gleichzeitig mit der
Potenzmengenkonstruktion mitmachen.
Da sie das nicht tun, ist es schwerer.
Also oben ist der nicht deterministische Automat, in der Mitte
angedeutet das, was man aus der Potenzmengenkonstruktion kriegt und
unten ist der minimale deterministische Automat.
Also der Unterschied hier ist tatsächlich nur, wo diese Schleife
sitzt, ob die hier sitzt oder hier.
Das ist der einzige Unterschied zwischen den Automaten.
Und gesucht ist ein Algorithmus, der aus dem hier, das hier macht, in
Laufzeit polynomiell in der Anzahl Zustände der beiden.
Ohne eben diesen exponentiellen Umweg hier in der Mitte.
Genau.
Also der Algorithmus soll es auch nicht nur für diesen Automat tun,
sondern...
Das ist nur ein Beispiel, wofür der nützlich sein könnte.
Achso und die Abgabe von dieser Zusatzaufgabe, die könnt ihr am besten
auf ein extra Blatt packen.
Die braucht ihr auch gar nicht an das Übungsblatt drankackern, weil
die müssen wir dann korrigieren.
Das wollten wir unseren Tutoren nicht zumuten.
Und ihr dürft sie auch zu dritt abgeben, aber nur diese eine Aufgabe.
Da kriegen auch alle drei ein Eis, ja.
Du darfst von mir aus auch Programmcode abgeben.
Solange der Algorithmus erkennbar ist, es für uns klar ist, dass der
die richtigen Laufzeiten hat, ist von mir aus da auch irgendwie was
getechtet.
Allerdings, wenn ihr jetzt sagt, ihr habt als Gruppe sinnvoll
zusammengearbeitet und die Gruppe ist größer als drei, dann müssen wir
mal schauen.
Ich hätte gesagt, wenn man Mitarbeit bei allen erkennt, können wir es
zwei Gruppen getrennt abgeben mit jeweils einem einzelnen Aufschrieb.
Also solltet ihr zu mehr als drei zusammenarbeiten wollen.
Ich weiß nicht, wie sinnvoll es ist.
Gibt es noch irgendwelche Fragen zu dieser Zusatzaufgabe?
Ich meine, die Epsilon-Übergänge kann man ja ohne Zustandserhöhung
entfernen, von daher sind die irrelevant.
Also es reicht die eingeschränkten NEAs ohne Epsilon-Übergänge zu
betrachten.
Genau.
Also die Frage war, ob Epsilon-Übergänge in dem nicht
-deterministischen Automat drin sein dürfen oder nicht.
Und die Antwort dazu ist, dass es für die Aufgabe wenig Unterschied
macht, weil man in linearer Zeit einen Epsilon-NEA in einen nicht
-deterministischen Automat umbauen kann, der gleich viele Zustände hat
und dieselbe Sprache erkennt.
Insofern ändert es an dieser Aufgabe wenig.
Wir haben gesagt, es gibt für alle drei Leute ein Eis.
Wenn eine Dreiergruppe das abgibt, kriegen alle drei ein Eis.
Jeweils ein Eis.
Und die Laufzeit darf natürlich auch polynomiell in der Alphabetgröße
sein.
Genau, also einfach die Laufzeit muss irgendwie polynomiell in der
Beschreibungskomplexität von der Eingabe und der Ausgabe sein.
Gut, dann wenn es keine Fragen mehr gibt, wäre es das von unserer
Seite für heute.