Ja, dann einen schönen guten Morgen.
Letztes Mal habe ich schon angekündigt, dass es heute um Prozessoren,
eigentlich nur um einen Prozessor gehen würde.
Und zwar, als Prozessor hatten wir ja die Mima kennengelernt.
Was eigentlich...
Die Mima ist eigentlich eine ganz vereinfachte Maschine.
Deswegen der Name Minimalmaschine, deswegen Mima.
Und das, obwohl das sieht ja aus wie ein Spielzeug im Vergleich zu
einem...
Können Sie bitte etwas leiser werden?
Ja, also im Gegensatz zu einem realen Prozessor sieht das ein bisschen
vereinfacht aus.
Aber da können wir uns ganz gut anschauen, welche...
Was die ganze Mechanik jetzt, wie das Ganze funktioniert.
Die kann jetzt Werte laden aus einem Speicher.
Also es gibt Speicherzugriff.
Ich kann Werte laden und speichern.
Ich muss Befehle holen.
Ich muss die auch verarbeiten.
Es gibt auch Operationen mit Arithmetik und Bit-Operationen und so
weiter.
Also das ist alles vereinfacht.
Aber da kann man sich gute Ideen verstehen.
Man kann sich gute Ideen da aneignen.
Und zwar...
Wir arbeiten mit zwei Speichern.
Zuerst brauchen wir im Prozessor selber eine Art Speicher.
Wir müssen die Zwischenergebnisse der Berechnungen irgendwo lagern.
Das geht anders nicht.
Heute ist es ziemlich laut.
Danke.
Nachdem wir was berechnet haben, möchten wir das auch irgendwo
speichern.
Im Prozessor selber haben wir vielleicht bei der MIMA nur einen
Akkumulator.
In einem echten Prozessor haben wir sogenannte mehrere Register.
Aber es gibt nur ähnlich viele davon und ganz wenig im Vergleich zu
dem Hausspeicher, was riesig groß werden kann.
Bei der MIMA haben wir natürlich...
Bei dem Hausspeicher kann man sich das ausrechnen, dass wir 3 MB
Speicherplatz haben.
Und am Akkumulator können wir nur irgendwie 3 Byte speichern.
Wir haben viel, viel mehr.
Und dann muss man irgendwie damit arbeiten, damit leben.
Das ist das.
Wenn man jetzt mit der MIMA was machen muss, dann muss ich dieser
Maschine jetzt Befehle geben.
Dann kann ich ein Programm schreiben.
Das Programm besteht aus diesen Befehlen.
Es gibt mehrere Arten davon.
Letztes Mal hatte ich schon ein bisschen eingeleitet, mit Verundung,
Negierung usw.
von Bits.
Schauen wir uns das mal an.
Das sind die ersten Befehle.
Auf der nächsten Folie gibt es ein paar mehr.
Aber im Prinzip, was kann ich machen?
Ich kann jetzt Konstanten laden.
Das ist das LDC Befehl.
Ich kann jetzt Werte aus dem Speicher holen, Werte da speichern.
Es gibt auch sogenannten indirekten Zugriff.
Das heißt, ich arbeite mit einer Stelle im Speicher nicht, als ob das
ein Wert wäre.
Sondern ich tue so, als ob der Wert, das da gespeichert ist, eine
Adresse ist.
Und dann hole ich indirekt, was in dieser Adresse steht.
Die Adresse steht im Speicher.
Dann hole ich, was in dieser Adresse steht.
Dann greife ich dazu.
Das sagt mir, du gehst in Adresse 42.
Dann gehe ich in Adresse 42 und hole ich den Wert, das in Adresse 42
liegt.
Es ist nützlich für eine Aufgabe auf diesem Blatt.
Auf dem Blatt Prozession 6.
Und dann habe ich natürlich auch Arithmetik, jetzt Additionen mit zwei
Komplementzahlen.
Ich habe auch diese ganze Bit-Operation von letztes Mal.
Das, was ich schon letztes Mal motiviert hatte, was nützlich da sein
kann.
Und es gibt noch ein paar mehr, wie angekündigt.
Zuerst gibt es das Equal-Befehl.
Das ist nützlich für meine Sprungbefehle insbesondere.
Also wenn ich jetzt an einer Stelle stehe und ich will jetzt sagen,
ist dieser Wert, was ich habe, dann gleich, was ich in meinem Speicher
stehen habe.
Dann kann ich das vergleichen.
Und wenn das gleich ist, dann werden alle Einsen gesetzt.
Und wenn nicht, dann werden alle Nullen gesetzt.
Und man könnte jetzt erwarten, die wahre Wahrheit sollte durch ein
einzelnes Bit dargestellt werden.
Letztes Mal hatte ich das auch gesagt.
Man stellt sich vor, dass eine Eins steht für wahr und eine Null steht
für falsch.
Und dann hätte man vielleicht erwartet, ja, da gibt es nur ein Bit
irgendwo, das sagt wahr.
Aber hier, das ist nützlich.
Egal welches Bit das ist, das wird eine Eins sein.
Warum nicht?
Und auch ist das nützlich für meine Sprungbefehle.
Bei einem Sprungbefehl, der bedingte Sprung, da schaue ich mir genau
an, was die erste Stelle ist, von dem Akkumulator.
Wenn es steht im Akkumulator, was negativ ist, dann will ich springen
zu einer anderen Stelle im Programm.
Es gibt auch den unbedingten Sprung, da springe ich egal, was der
aktuelle Zustand des Prozessors ist.
Aber es gibt auch diesen bedingten Sprung, da kann ich jetzt mein
Programm verzweigen.
Also ich habe etwas berechtigt, dann komme ich zu einer Stelle, dann
schaue ich mir an, gilt diese Bedingung?
Und dann wird weder weiter Befehle geladen, es wird nicht gesprungen,
oder die Bedingung gilt doch, dann springe ich.
Das wird verzweigt da.
Und natürlich haben wir noch etwas, das signalisiert, dass die
Berechnung zum Ende ist, damit wir sicher sein können, der Prozessor
ladet jetzt nicht weiter Befehle und zerstört alles, was wir gemacht
hatten.
Um das ein bisschen zu illustrieren, man kann ja, man hat, damit
arbeitet man ja, man hat 20-Bit-Adressen und die Werte sind jetzt 24
-Bit lang.
Also dass man jetzt nicht 24-Bit-Adressen hat, ist technisch, ist
eigentlich, die Begründung dafür ist eine technische Begründung, ich
muss irgendwie auch meine Befehle irgendwie kodieren und dafür brauche
ich vier Bits.
Und deswegen die Bits, die übrig bleiben von den 24, sind 20 Bits.
Also ist vielleicht für uns jetzt, in dieser Vorlesung nicht so
wichtig, wenn Sie Rechnerorganisationen und so weiter hören, da werden
Sie nochmal von dieser Geschichte erzählt bekommen.
Genau, dann haben wir, sagen wir mal drei Adressen im Speicher und
dann können wir irgendwie Sachen damit tun, wir können den Wert X
laden, wir können dann, mit was in Y steht, eine Operation XOR
durchführen und dann wieder in Z speichern.
Das ist ganz einfach.
Also von oben nach unten verarbeitet natürlich.
Dann kann man jetzt sich auch überlegen, will ich jetzt einen Wert
inkrementieren, ich will eine 1 darauf addieren, wie kann ich das
machen?
Dann lade ich mir diesen Wert A und addiere ich 1 drauf.
Da muss man wirklich in die Spezifikation genau gucken, was die
Addition macht.
Und die Addition hier bei der MIMA, das ist nicht so, dass die
Addition eine Konstante als Parameter bekommt, sondern sie bekommt
eine Adresse.
Das heißt, diese 1 ist eigentlich eine Adresse und dann werden sie,
wenn sie das machen, dann addieren sie den Wert zu A, was an der
Adresse 1 steht.
Das ist nicht, was wir wollen.
Wir wollen sondern eine 1 darauf addieren und deswegen müssen wir
jetzt das Spieß umdrehen.
Wir müssen zuerst die 1 laden und dann addieren wir A drauf.
Dann können wir A wieder speichern.
Das ändert sich nicht.
Das sieht man immer wieder gerne.
Das ist ein üblicher Fehler.
Natürlich können wir nicht nur grundlegende Sachen wie Zahlen
addieren, realisieren.
Wir können auch kompliziertere Dinge machen.
Das Titel von dieser Folie ist schon verdächtig.
Links und rechts sollen als zwei Programmstücke verstanden werden.
Ich habe einen Wert x und ich habe Stellen y und z.
Wenn ich jetzt 1 lade und nicht x darauf addiere, das hatten wir auf
der letzten Folie, sondern das Verunden mit der 1, dann habe ich wie
letztes Mal diese letzte 1, diese letzte Ziffer ausgewählt.
Das kann ich jetzt in y speichern.
Und rechts passiert etwas Ähnliches.
Ich habe eine 1 geladen.
Dann negiere ich alle Bits.
Die werden alle umgekippt.
Das heißt, es steht dann 1 überall bis auf die letzte Stelle.
Vorher standen 0 überall und dann die 1 auf der letzten Stelle.
Dann umgekehrt ist es andersherum.
Und dann verunde ich das mit dem x und rotiere ich das.
Das ist das, was ich gerade erzählt hatte.
Wir haben diese Masken für die Verundung, wie letztes Mal.
Und dann für die linke Seite werde ich das Modulo berechnen.
Ich habe die letzte Ziffer von x ausgewählt.
Das hatten wir uns letztes Mal angeschaut.
Und rechts habe ich eine andere Maske.
Aber wir hatten bei letzter Übung auch gesehen, wenn ich das mache und
dann rotiere, dann habe ich eine ganzheitliche Division durch 2
gemacht.
Wenn das x jetzt positiv war.
Also wenn das negativ war, würde das nicht so ganz gut gehen.
Wenn man weiß, das ist negativ, dann kann man das negieren.
Zwei Komplemente von der Negation bilden, dann durch 2 dividieren und
dann wieder negieren.
Das ist nicht so schön, deswegen lassen wir das.
Und dann haben wir diese Operation, irgendwie Addition und so.
Und jetzt Division durch 2 zumindest können wir das realisieren.
Und es ist nicht so kompliziert.
Das heißt, wir können vielleicht auch echte Programme, die Sie in Java
oder C geschrieben haben, dann vielleicht bei der MIMA realisieren.
Und als erster Schritt dafür vielleicht wäre, dass man ganz
grundlegende Strukturen aus diesen Sprachen zu der MIMA bringt.
Und vielleicht das ganz Grundregende wäre jetzt Kontrollstrukturen.
Vielleicht kennen Sie das nicht unter diesem Namen.
Aber das kennen Sie bestimmt schon, wenn Sie Programmieren hören.
Also das sind einfach diese If-Then-Strukturen oder If-Then-Else und
Waldschleifen, Vorschleifen und so weiter.
Also der Programm wird irgendwie verarbeitet und dann diesen Fluss der
Verarbeitung können Sie dann steuern durch diese Strukturen.
Deswegen der Name Kontrollstruktur.
Und in der MIMA haben wir eigentlich schon zwei kleine eingebaut.
Das sind die zwei Sprungbefehle.
Also ich kann an einer Stelle sagen, das geht nicht jetzt weiter in
den nächsten Adressen, sondern ich gehe jetzt in eine andere Adresse
weiter mit dem unbedingten Sprung.
Oder bedingter Sprung, das war diese Verzweigung.
Das ähnelt einem If, Verzweigen.
Deswegen ist das auch kein Wunder, dass wenn man das realisieren will,
dann auch ich das so irgendwo brauche.
Hier natürlich ein vereinfachtes Beispiel.
Also die Bedingung dafür, das If ist ganz einfach.
Ich will jetzt irgendwie zwei Werte vergleichen.
Und dann, ich weiß ja, ich brauche eine Verzweigung, deswegen muss ich
dieses JTMN Befehle verwenden.
Negativer Sprung.
Und das heißt, es wird gesprungen, wenn die Bedingung nicht erfüllt
ist.
Oder wenn der Ma1 gleich der Ma2 ist, dann stehen überall Einsen.
Und wenn ich das legiere, dann springe ich genau dann, wenn das
ungleich war.
Man muss sich ein bisschen klar machen, dieses JTMN arbeitet
eigentlich, wenn die Zahl, wenn das im Akkumulator negativ ist, dann
wird gesprungen.
Das ist ein bisschen kontraintuitiv.
Aber hier, was ich machen kann, damit diese bedingte Anweisung auch
schön realisiert wird, ist, dass ich springe über diesen Block S zum
Block U, wenn die Bedingung nicht erfüllt ist.
Das ist, was ich mache.
Und dann habe ich diese Werte verglichen und wenn das doch der Fall
ist, dann wird weiter mit S verarbeitet und am Ende mit U.
Und wenn das doch nicht der Fall war, dann wird über S gesprungen.
Das ist, was dieses JTMN zum Effekt bringt.
Man kann das hier ein bisschen erweitern, dann noch ein S-Teil dazu
bringen.
Und zwar, wenn das S genommen wird, dann verarbeite ich von F durch
den JTMN durch, dann komme ich zu dem W-Teil, zum S.
Und wenn ich fertig bin, dann muss ich zu diesem U-Block springen,
deswegen mache ich diesen Sprung da.
Und wie vorher, wenn ich das S nicht haben will, wenn die Bedingung
verletzt wird, dann springe ich direkt zu dem L-Teil.
Dann werde ich automatisch T und dann direkt mit U weitermachen.
Das ist, damit man das kompakter realisieren kann.
Wenn die Bedingung gilt, dann springe ich in S und wenn nicht, dann
mache ich mit T durch.
Das würde auch gehen, aber vielleicht würde ich dann eine Einweisung
oder mehr brauchen.
Das ist irgendwie Geschmackssache, wie ich das realisiere, wie das
alles genau ist.
Und die Wahlschleife, da muss ich wieder dieses Block S wieder und
wieder ausführen, soweit die Bedingung erfüllt ist.
Und dann was ich mache, wenn die Bedingung nicht erfüllt ist, dann
springe ich direkt zu dem T-Block.
Wenn nicht, dann mache ich eine Durchführung von S.
Dann springe ich weiter zum Anfang vom Wahlblock.
Dann wiederhole ich einfach.
Dann werde ich automatisch die Bedingung nochmal prüfen.
Dann hat man das.
Letztes Mal hatte ich auch dieses Links-Rotieren eingeführt.
Wir können den Akkumulator nach rechts rotieren, aber vielleicht
wollen wir das auch nach links rotieren.
Wie könnte man das realisieren?
Vielleicht ganz einfach, ich wiederhole rechts rotieren 23 Mal.
Das hatten wir auch vorher.
Wenn ich 24 Mal das Rotieren ausführe, ich habe ein 24-Bit langes
Font, dann wird nichts passieren.
Wenn ich einen Schritt vorher aufhöre, dann werde ich das nach links
rotiert haben.
Aber hier, das ging ja auch besser, als 23-mal die gleiche Anweisung
auszuführen.
Und nämlich, ich kann diesen Trick mit der Division durch 2 verwenden.
Wenn ich eine ganzheitliche Division durch 2 mache, dann habe ich
schon diese ganzen Bits von 22 bis...
Also ich mache nicht die Division durch 2, als würde ich jetzt eine
Division durch 2 machen, aber ich rotiere nicht.
Dann habe ich die allen Bits bis auf das letzte ausgefüllt und dann
schaue ich mir an, dann speichere ich das in Y, so als Zwischenwert
und dann muss ich jetzt irgendwie das letzte Bit auch anschauen, was
das ist.
Und wenn das eine 1 ist, dann muss ich das dann zu diesem Wert
addieren, weil dieser Wert jetzt hat eine 0 ganz links.
Wenn das doch nicht der Fall ist, dann bin ich fertig, dann kann ich
anhalten und eine 1 addieren, das hatten wir auch vorher
kennengelernt, wie das geht.
Das ist dann dieser B-Teil, das hat jetzt einfach eine 1, damit dieser
X 23 dann wieder rekonstruiert wird.
Dann wäre es das für die Übung, ich bedanke mich für die
Aufmerksamkeit und schöne Vorlesung.
So, ja, schönen guten Tag.
Irgendwo...
Kommen wir zur Vorlesung.
Da sind wir inzwischen bei kontextfreien Grammatiken.
Also ich habe Ihnen schon gezeigt an einem Beispiel, das ist halt auch
der Formalismus, mit dem man zum Beispiel große Teile der Syntax von
so gängigen Programmiersprachen einfach festlegt.
Deswegen ist es sinnvoll sowieso, dass man sich das anguckt.
Und wir müssen in Kürze dann auch noch wieder irgendwelche Syntax
festlegen und Sie werden sehen, das ist mit kontextfreien Grammatiken
viel bequemer als mit irgendwelchen anderen Formalismen.
Also eine kontextfreie Grammatik, da hat man zwei Alphabete,
sogenannte Nicht-Terminalsymbole und sogenannte Terminalsymbole.
Was einem am Ende interessiert, sind Wörter aus lauter
Terminalsymbolen.
Also hier in diesem Beispiel klein a, klein b.
Und dann gibt es eben diese Nicht-Terminalsymbole, das sind so
Hilfssymbole.
Eins davon ist auch immer ausgezeichnet als Startsymbol.
Also wenn man sowieso nur eins hat, muss das natürlich das Startsymbol
sein.
Und was man dann noch hat, sind Ersetzungsregeln, wirklich rein
syntaktisch, überhaupt nicht an Bedeutung denken.
Immer ein Nicht-Terminalsymbol darf man ersetzen durch eine Folge von
anderen Symbolen, bunt gemischt Terminal- und Nicht-Terminalsymbole.
Darf auch das leere Wort sein, also wie hier x darf ich ersetzen durch
das leere Wort und x darf ich ersetzen durch a, x, b.
Und dann kann man immer so Ableitungsschritte machen.
Man fängt letzten Endes, was einen interessiert, immer mit dem
Startsymbol an.
Und dann darf ich das x hier, das einzige, was hier steht, ersetzen
durch a, x, b.
Dann entsteht eben aus diesem x a, x, b.
Dann darf ich das Gleiche wieder machen, dieses x hier in der Mitte
ersetzen durch a, x, b.
Dann steht da eben a² xb².
Dann darf ich das x in der Mitte zum Beispiel nochmal ersetzen.
Dann habe ich a hoch 3, xb hoch 3.
Also die ersten zwei a´s, weil sie schon da standen.
Dann das a, xb durch die Ersetzung und hinten die zwei b´s, die da
schon standen.
Und wenn ich dann x durch das leere Wort ersetze, dann habe ich a hoch
3, b hoch 3.
Und man schreibt also immer so einen Doppelpfeil, wenn man aus einem
Wort durch eine Ersetzung zu dem nächsten Wort hinter dem Doppelpfeil
kommt.
Und wenn man sagen will, ja, ich komme von einem Wort zu einem
anderen, dann nicht unbedingt in einem Ableitungsschritt, sondern in
endlich vielen.
Dann erlaubt man sich da auch ein Sternchen an dem Pfeil dran zu
schmalen.
Und das heißt dann, in einer beliebigen Anzahl Schritte, sei es nur 0
oder 1 oder 2 oder 3 oder wie viel auch immer.
Und wenn man genau sagen will, wie viele Ableitungsschritte, dann
erlauben wir uns auch zum Beispiel an diesem Ableitungspfeil da als
Exponent die Zahl der Schritte dran zu schreiben.
Und diese Grammatik hier erzeugt dann also, habe ich Ihnen so
angedeutet, genau die Wörter, die von der Form sind.
Eine gewisse Anzahl A´s und dahinter genau die gleiche Anzahl B´s.
Und wir werden später noch sehen, mit dem sozusagen, was wir bisher so
naiv hatten, um formale Sprachen mithilfe von Vereinigung,
Konkatenation, Konkatenationsabschluss aus einfachen Sprachen
zusammenzusetzen, können Sie sowas nicht bauen, geht nicht.
So, wenn man mehrere Produktionen hat mit der gleichen linken Seite,
dann schreibt man nicht immer die linke Seite immer wieder hin,
sondern schreibt X-Pfeil und dann durch senkrechten Strich getrennt
die verschiedenen möglichen rechten Seiten, die Sie einsetzen dürfen
für das Nicht-Terminalsymbol.
Und dann haben Sie auch diese Interpretation für das, was Sie in der
Java -Syntax sehen.
Und da haben halt die Nicht-Terminalsymbole dann sinnigerweise
irgendwelche plausiblen Namen, die einem irgendwas darüber sagen, was
man aus diesem Nicht-Terminalsymbol ableiten kann.
Also meinetwegen aus dem Nicht-Terminalsymbol-Block kann man dann eben
alles ableiten, was ein sogenannter Block in Java ist.
Und ich habe Ihnen auch noch gesagt am Ende der letzten Vorlesung,
also wenn man genau hinguckt bei Java oder auch bei vielen anderen
Programmiersprachen, es gibt halt Dinge, die möchte man gerne
ausdrücken, also die gehören zur Syntax der Programmiersprache, aber
man kann sie nicht mithilfe von kontextfreien Sprachen ausdrücken.
Dafür ist der Formalismus zu schwach.
Also zum Beispiel sowas, eine benutzte Variable muss vorher deklariert
sein.
Das können Sie nicht in den Formalismus kontextfreie Grammatik
reinpressen.
Nicht alles, was ableitbar ist in der Java-Grammatik, ist auch
wirklich legales Java.
Aber jedenfalls wesentliche Teile findet man da schon wieder.
Und wenn Sie dann irgendetwas einem Java-Compiler geben, was der
tatsächlich als erstes macht, ist, er guckt, das, was hier steht, kann
man das in der Grammatik ableiten und er baut dann so etwas wie den
Ableitungsbaum.
Was ist der Ableitungsbaum?
Damit kommen wir jetzt zu den neuen Dingen.
Hier zur Abwechslung mal eine andere Grammatik, ein Nicht
-Terminalsymbol X, das können Sie ersetzen durch zwei Xe oder Sie
können es ersetzen durch Klammer auf, X, Klammer zu und Klammer auf
und Klammer zu sind die Terminalsymbole.
Und Sie können X ersetzen durch das leere Wort.
Dann kann man solche Ableitungsfolgen hinschreiben.
X kann ich ersetzen durch zwei X, dann habe ich also nach einem
Ableitungsschritt zwei X.
Dann, wenn ich jetzt zum Beispiel mich dafür entscheide, das linke von
den beiden X zu ersetzen durch Klammer auf, X, Klammer zu, dann kriege
ich eben Klammer auf, X, Klammer zu und dahinter das X, das da schon
stand.
Dann kann ich mich entscheiden, das rechte von den beiden X zu
ersetzen durch zwei X, dann habe ich das.
Dann kann ich wieder mich dafür entscheiden, das hintere X ersetzen
durch Klammer auf, Klammer zu, Klammer auf, X, Klammer zu und so
weiter und so weiter.
In jedem Schritt ein X wird ersetzt.
Kann man tun, kommt irgendwas raus.
Aber ich kann solchen Zeichenfolgen nicht viel abgewinnen.
Man kann es halt auch nicht von der Struktur her leicht erfassen, was
da eigentlich passiert.
Deswegen erstens, kontextfreie Grammatiken heißen ja, so habe ich
Ihnen gesagt, weil Sie ein Nicht-Terminalsymbol immer ersetzen können
durch irgendeine rechte Seite, egal was links und rechts davon steht.
Also wenn Sie jetzt ein Wort haben, wo zweimal zum Beispiel hier
zweimal das gleiche, also zweimal Nicht-Terminalsymbol vorkommt, das
linke Vorkommen können Sie ersetzen und dann können Sie hinterher das
rechte Vorkommen ersetzen.
Aber Sie können es auch in der umgekehrten Reihenfolge machen, denn
was außenrum passiert, der Kontext, ist ja völlig irrelevant.
Die Ersetzung ist möglich, egal ob da immer noch das gleiche steht wie
einen Schritt früher oder nicht.
Also die Reihenfolge, in der Sie was ersetzen, ist egal.
Und deswegen bei so Ableitungsfolgen das Erste, was man merkt ist,
wenn schon sowas hingeschrieben werden muss, dann bitte mache ich es
doch systematisch und ersetze immer von den ganzen Nicht
-Terminalsymbolen, die da vielleicht stehen, immer das, was am
weitesten links steht als erstes.
Das gibt dann, Überraschung, eine sogenannte Linksableitung, wenn Sie
immer das am weitesten links stehende Nicht-Terminalsymbol ersetzen.
Also wenn Sie hier immer wieder jetzt auch rot anmalen, welches X wird
ersetzt, dann von allen Xen, das ganz links ist rot.
Nicht wie da oben mal vorne, mal hinten, sondern immer ganz links.
Und was können Sie damit ableiten?
Das Gleiche wie vorher, nicht mehr und nicht weniger.
Also mehr natürlich nicht, denn es sind ja auch Ableitungen und auch
nicht weniger, weil Sie eben immer umsortieren können.
Das ist dann vielleicht schon mal ein bisschen hilfreicher und analog
zu Linksableitungen definiert man auch Rechtsableitungen.
Da ersetzen Sie halt immer nicht das möglichst weit links stehende,
sondern das möglichst weit rechts stehende Nicht-Terminalsymbol.
Und noch schöner wird es, wenn Sie sich das als Baum hinmalen.
Und dann entsteht also sowas hier und das nennt man dann einen
Ableitungsbaum.
Da fängt man also an mit dem Startsymbol an der Wurzel.
Und wenn Sie dann eine Ersetzung machen, zum Beispiel X wird ersetzt
durch 2X, dann malen Sie unter das Symbol, das ersetzt wird, die
beiden Symbole, die die rechte Seite sind, XX.
Und dann machen Sie von dem Symbol, das ersetzt wird, zu jedem Symbol
der rechten Seite, die Sie benutzen, einen Strich, eine Kante nach
unten.
Also hier X wird ersetzt durch XX.
Und dann das linke X wird ersetzt durch Klammerauf, X, Klammerzu.
Klammerauf, X, Klammerzu sind drei Symbole, deswegen von dem X, das
ersetzt wird, drei Kanten gehen nach unten zu den drei Symbolen.
Und das X wird wieder ersetzt durch Klammerauf, X, Klammerzu.
Und das X in der Mitte hier wird ersetzt durch das leere Wort.
Und das rechte X wird vielleicht nochmal ersetzt durch 2X.
Und dann das linke durch Klammerauf, X, Klammerzu.
Das rechte Klammerauf, X, Klammerzu.
Und dann jedes durch das leere Wort.
Und dann haben Sie hier so einen Baum, so eine Wurzel oben, unten die
Blätter.
Und was steht an den Blättern?
Also entweder Terminalsymbole oder das leere Wort, falls das auch auf
der rechten Seite irgendwo vorkommt.
Solange da ein Nicht-Terminalsymbol ist, sind Sie noch nicht fertig
mit der Ableitung.
Weitermachen.
So, das nennt man den Ableitungsbaum.
Und da sieht man ein bisschen besser sozusagen, in Anführungszeichen,
wie das abgeleitete Wort aus Terminalsymbolen aufgebaut ist.
Also wenn das jetzt hier nicht so ein einfaches Klammerauf, Klammerzu
-Zeug wäre, sondern ein Java-Programm, da wäre halt das Startsymbol an
der Wurzel, hieße halt Java-Programm.
Und dann, ich weiß nicht, also das ist jetzt fantasiert.
Wir ersetzen das durch, vorne steht als erstes irgendein Nicht
-Terminalsymbol, Deklarationen.
Und hinten steht ein Nicht-Terminalsymbol, Anweisungen.
So ist das nicht in Java, aber ja.
Und dann wird so die Struktur langsam aufgebrochen.
Und Sie sehen in dem Baum auch grob, wie Ihr Programm aufgebaut ist.
Und tatsächlich, wenn Sie etwas dem Java-Compiler geben, was der als
erstes konstruiert, also er guckt, ist es ableitbar und wenn ja, er
konstruiert, ja nicht genau, aber sowas ähnliches wie den
Ableitungsbaum.
Das wird tatsächlich gebastelt von einem Programm.
Und übrigens, das Programm, das überprüft, ob Ihr Text ein legales
Java -Programm ist, dieser Syntax-Überprüfer und Ableitungsbaum-Bauer,
der ist nicht zu Fuß programmiert, der es automatisch erzeugt.
Mithilfe eines Programms, da stecken Sie nur die Grammatik rein und
raus plumpst das Programm, das die Syntax-Analyse macht.
Also Syntax-Analyse hat man mittlerweile ziemlich gut im Griff, stark
automatisiert.
Und da gibt es dann übrigens zwei Sorten von Syntax-Analyse, die dann
hinterher veranstaltet wird, die so ein bisschen angelehnt ist an die
beiden Dinge, die ich Ihnen letztes Mal erzählt habe.
Die eine Sorte versucht, den Ableitungsbaum zu konstruieren, sozusagen
von unten nach oben.
Und die andere Sorte versucht, den Ableitungsbaum zu konstruieren von
oben nach unten.
Diese Grammatik, x kann ich ersetzen durch 2x oder Klammer auf, x
Klammer zu oder y, das erzeugt das, was wir schon kennen, das sind
diese wohlgeformten Klammerausdrücke aus irgendwelchen Hausaufgaben
oder aus der Vorlesung oder beidem.
Also es ist locker gesagt, das, was Sie kriegen, wenn Sie bei
arithmetischen Ausdrücken alles, was mit Arithmetik zu tun hat,
weglassen, nur die Klammern übrig bleiben.
Und das sind also ganz wichtige Beispiele für kontextfreie Sprachen,
ohne dass wir das jetzt hier weiter ausführen können, aber falls Sie
mal irgendwo eine Vorlesung über formale Sprachen hören, werden Sie
merken, oh ja, also alle kontextfreien Sprachen, können Sie aus so
Sprachen, wo es nur um so ordentliche Klammerungen geht, erzeugen,
indem Sie nur noch wenig dran rumfummeln.
Apropos arithmetische Ausdrücke und sowas, hier ist eine einfache
kontextfreie Grammatik so einfach, dass man sie nicht benutzt für
arithmetische Ausdrücke.
Also stellen Sie sich vor, wir hätten nur drei mögliche konstante
Operanden, 1, 2 und 3 und Pluszeichen, Minus, Stern, Durch und
Klammern.
Dann könnte man ja solche Produktionen hier nehmen.
S kann ich ersetzen durch T.
Also T ist irgendwie so eine einfache Variante von S und aus S will
ich also alle arithmetischen Ausdrücke ableiten können.
Oder es ist S plus T oder S minus T oder S mal T oder S durch T oder
ein T kann sein, ein S in runden Klammern, geklammerter Ausdruck oder
eine 1 oder eine 2 oder eine 3.
Und wenn Sie dann so ein Wort nehmen wie 3 minus 2 minus 1 ohne
Klammern, dann hat das einen Ableitungsbaum.
Das ist der, den Sie da links sehen und die Grammatik ist so gebaut,
dass dieses 3 minus 2 minus 1 tatsächlich nur einen Ableitungsbaum
hat, nicht zwei verschiedene.
Deswegen macht man hier noch diese Unterscheidung mit S und T.
Was sehen Sie da?
Also sozusagen in dem Ableitungsbaum her, sieht das also so aus, dass
irgendwie das 3 minus 2, das ist irgendwie in einem Unterbaum und dann
gibt es ja noch das Minus und die 1.
Also irgendwie von der Struktur her sieht das ein bisschen so aus wie
3 minus 2 in Klammern und dann noch minus 1.
Da fällt mir ein, ich habe vorhin vergessen, was zu sagen.
Ich gehe noch mal ein bisschen zurück.
Bei so einem Ableitungsbaum, wie findet man da das Wort, das da
insgesamt abgeleitet wird?
Na ja, Sie gehen da von der Wurzel erstmal immer nach links, nach
links, nach unten bis zum ersten Blatt und dann immer so hoch und
immer möglichst früh, möglichst weit runter und wenn es unten nicht
mehr weiter geht, gehen Sie wieder hoch und dann den nächsten Ast
runter und dann laufen Sie da so durch den ganzen Baum durch,
sozusagen von links nach rechts, sammeln Sie alle Blätter in dem
Ableitungsbaum, also alle Terminalsymbole und alle Epsilons auf und
wenn Sie dann in der Reihenfolge, in der Sie sie finden, nebeneinander
schreiben, haben Sie das abgeleitete Wort.
So, und hier zum Beispiel also 3-2-1, Ableitungsbaum für dieses Ding.
So ein bisschen was Analoges, wie bei arithmetischen Ausdrücken,
können Sie haben bei so etwas hier, ich glaube, das ist auch
syntaktisch korrektes Java, if in runden Klammern irgendeine
Bedingung, also für B1 und B2 stellen sich irgendwelche legalen
Bedingungen vor, x gleich 0 oder 2 gleich 3 oder so, if in Klammern
eine Bedingung, dann Statement 1, else Statement 2 und S1 und S2 sind
einfache Zuweisungen, einfach eine Zuweisung, y kriegen wir 3 oder so
etwas, dann ist das legales Java und das bedeutet auch ganz eindeutig
was, weil auch da die Grammatik von Java, so wie hier oben die für die
arithmetischen Ausdrücke so gebaut ist, dass es nur einen
Ableitungsbaum gibt, das möchte man gerne, wenn der Ableitungsbaum
etwas über die Struktur eines Programms sagt, dann sollte es für ein
Programm auch nur einen Ableitungsbaum geben, es sollte irgendwie klar
sein, was ist die Struktur, die gemeint ist und dann, wenn Sie das
aber ganz naiv angucken, if Bedingung 1, if Bedingung 2, else S1, else
S2, dann ist ja erstmal nicht klar, dieses else, ist das das else vom
zweiten if oder das else vom ersten if?
Und in Java ist es halt irgendwie festgelegt und wenn mich nicht alles
täuscht, ich hoffe es kann mir jemand bestätigen, das else gehört zum
nächsten if, zum zweiten hier, kann mir das jemand bestätigen?
Haben Sie sowas gelernt?
Nicht?
Doch, einer nickt.
Ah, prima, gut.
Also die Grammatik ist dann so gebaut, dass das eben festgelegt ist,
allerdings schöner ist es natürlich, also finde ich persönlich, wenn
man da nicht raten muss oder so oder was wissen muss und also diese
Mehrdeutigkeit, diese potenzielle, also wenn Sie mal nach dem Begriff
dangling else suchen, dann finden Sie da was, ist weg, sobald man am
Ende von einem if auch noch irgendwas hat, was einen erkennen lässt,
hier ist das if zu Ende.
Und dann sieht man auch, das zweite if ist das vor dem else zu Ende
oder danach.
Was man mit solchen Ableitungsbäumen noch machen kann, also wenn zum
Beispiel der Compiler sie denn dann schon mal hat, wenn Sie hier zum
Beispiel so einen arithmetischen Ausdruck haben und die Blätter, also
die Werte, das sind alles Konstanten, da stehen keine Variablen und
Sie wissen noch nicht, welche Werte die haben, dann können Sie so
einen arithmetischen Ausdruck mit lauter Konstanten, den kann auch
gleich der Compiler, wenn er unter Umständen ein bisschen vorsichtig
ist, auswerten, indem Sie einfach von unten nach oben so Werte
hochgeben, also wenn hier aus T abgeleitet wird, die drei, dann im
ersten Schritt kann man sagen, ach so, erst mal die Blätter, sie
bedeuten die naheliegenden Zahlen.
Und dann können Sie die nach oben weiterreichen, aber wenn unter T
hier nur die 3 steht, dann T steht für den Wert 3 auch und hier T für
den Wert 2, für den Wert 1.
Und dann wenn aus S hier ganz links das T abgeleitet wird, dann das S
steht sozusagen auch für den Wert 3.
Und dann haben Sie hier oben drüber ein S, da sehen Sie, der linke
Nachfolger steht für den Wert 3, der rechte für den Wert 2 und es geht
um Minus, dann können Sie den Wert für das S oben drüber ausrechnen,
das ist dann 1.
Und dann haben Sie da eine 1 und ein Minuszeichen und ein 1 und dann
können Sie oben für die Wurzel auch direkt ausrechnen, dass da 0
rauskommt.
Dann haben Sie den arithmetischen Ausdruck sozusagen ausgewertet,
indem Sie einfach in dem Baum von unten nach oben Dinge hochgegeben
haben.
Und solche Dinge, von den Blättern von unten nach oben, was hochgeben,
das können Sie nicht nur machen, wenn arithmetische Ausdrücke
ausgewertet werden könnten, weil da lauter Konstanten sind.
Solche Dinge können Sie auch für kompliziertere Aktionen des Compilers
machen.
Wenn ich schon ein Codestück habe für den Teil des Programms und ein
Codestück habe für jenen Teil des Programms, dann kann ich jetzt auch
den Code für die ganze Weilschleife zusammensetzen und so.
Da können Sie so von unten nach oben Codestücke zusammensetzen und am
Ende haben Sie ein ganzes Programm.
Also sowas passiert einfach in einem Compiler.
Das sehen Sie dann irgendwann vielleicht mal in der Compiler
-Vorlesung.
Diese Grammatik von eben wollen Sie für arithmetische Ausdrücke nicht
wirklich haben, denn der Ableitungsbaum für 3 plus 2 mal 5 sieht so
aus.
Da wird also das 3 plus 2 in einen Unterbaum gepackt und dann mal 5.
Das entspricht nicht der Intuition.
Man sagt ja, Multiplikation bindet stärker.
deswegen in Wirklichkeit Grammatiken für arithmetische Ausdrücke und
natürlich ist in Java so eine Teilgrammatik drin für arithmetische
Ausdrücke, sind so gebaut, dass der Ableitungsbaum nicht so aussieht,
wenn Sie da keine Klammern gesetzt haben in 3 plus 2 mal 5, sondern
dass der Ableitungsbaum so aussieht, dass das 2 mal 5 in einem
Unterbaum ist und oben drüber außenrum das 3 plus.
Wie bequem
kontextfreie Grammatiken sind, das habe ich jetzt vergessen, sieht
man, wenn man mal sich anguckt, wie könnte ich denn jetzt zum Beispiel
die Syntax von aussagenlogischen Formeln hinschreiben.
Zur Erinnerung,
welches Kapitel war das?
Aussagenlogik?
Eigentlich definiert hatten wir aussagenlogische Formeln mit Hilfe von
4 Abbildungen, die aus kleinen Formeln große basteln und dann haben
wir da irgendetwas iteriert und immer Mengen von immer größeren
Formeln vereinigt und gesagt, ja, das sind aussagenlogische Formeln.
Und Sie können sich das ja nochmal angucken und vergleichen mit dem,
was wir jetzt machen und auch versuchen, da die Analogie zu sehen.
Jetzt schreiben wir einfach mal eine kontextfreie Grammatik für
aussagenlogische Formeln hin, also einfach für syntaktisch, wie sieht
eine aussagenlogische Formel aus.
Da müssen Sie jetzt ein bisschen aufpassen, denn wir haben diesen
Pfeil für, das ist eine Produktion und in aussagenlogischen Formeln
darf aber auch so ein Pfeil vorkommen, bringen Sie die nicht
durcheinander.
Was sind die Terminalsymbole, die vorkommen dürfen in
aussagenlogischen Formen, Klammern nicht und oder Pfeil und so ein
paar Aussagevariablen, endlich viele.
Und jetzt statt dieses ganzen Durcheinanders hier, was wir da das
letzte Mal veranstaltet haben, stehen hier einfach ein paar
Produktionen in einer kontextfreien Grammatik und es gibt nur ein
Nicht -Terminalsymbol groß X und X dürfen Sie ersetzen durch eine
Aussagevariable oder durch Klammer auf nicht X Klammer zu oder durch
Klammer auf X und X Klammer zu oder so oder so.
Und das sind alle Produktionen fertig.
Die Wörter nur aus Terminalsymbolen, also nur aus Aussagevariablen,
den Konnektiven und Klammern, die Sie ableiten können, sind genau die
aussagenlogischen Formeln.
Und die Syntax passt in drei Zeilen oder sowas und fertig.
Und wenn man ein bisschen netter sein will, nennt man das Nicht
-Terminalsymbol vielleicht nicht groß X.
Schöne Namen für Variablen sind immer sinnvoll.
Wenn Sie das ALF für aussagenlogische Formeln nennen, dann sehen die
Produktionen ein bisschen länger aus, aber vielleicht Sie sagen ein
bisschen mehr.
Aber das sind genau die gleichen Produktionen, wie hier nur statt X
steht da aussagenlogische Formeln.
So.
So einfach geht jetzt Syntax zum Beispiel von sowas festzulegen.
Fertig.
Gut.
So, diese Beispiele mit arithmetischen Ausdrücken, aussagenlogischen
Formeln und kleinen Schnipseln aus Java hat Sie hoffentlich mehr oder
weniger davon überzeugt, dass kontextfreie Grammatiken nützlich sind.
Und wie gesagt, die sind so nützlich, man kann dann sogar die
Programme, die die Syntaxanalyse machen, ist etwas ableitbar, ist
etwas korrekt.
Diese Programme kann man automatisch erzeugen aus der Grammatik.
Da muss man gar nichts mehr selber programmieren.
Also, kontextfreie Grammatiken aus dem Startsymbol, sie leiten Wörter
ab, die nur aus Terminalsymbolen bestehen.
Das gibt dann, die Menge aller solcher Wörter ist die erzeugte formale
Sprache.
Und also für mich die angenehmste Art und Weise, etwas zu Papier zu
bringen, ist ein Ableitungsbaum zu malen.
Das finde ich am leichtesten zu erfassen.
Naja, und dann gibt es halt die üblichen Aufgaben.
Also entweder man gibt ihnen eine kontextfreie Grammatik und man fragt
sie ja, was erzeugt die denn alles an Wörtern so?
Oder umgekehrt, man gibt ihnen eine Menge von Wörtern und sagt so,
jetzt machen sie mal eine Grammatik, die genau diese Wörter und keine
anderen erzeugt.
Das sind immer zwei Aufgaben.
Erstens, man erzeuge die Wörter, die man haben will und zweitens, man
vermeide irgendwelchen Unsinn auch noch mit zu erzeugen.
Immer nur die, die man haben will.
So, das sind kontextfreie Grammatiken.
Und damit kann man Dinge tun, also zum Beispiel einen Großteil der
Syntax von Programmiersprachen festlegen, wenn auch nicht alles.
Und wo eine Grenze ist, etwas, was man nicht mit kontextfreien
Grammatiken machen kann, das gucken wir uns dann gleich im letzten
Abschnitt noch an.
Nicht, dass Sie glauben, das ist jetzt dann das Ende und danach kommt
nichts mehr.
Und vorneweg haben wir aber wieder mal noch so einen Einschub, so ein
bisschen allgemeinerer Formalismus, so ein bisschen Abstraktion
dessen, was wir gerade bei kontextfreien Grammatiken gemacht haben,
weil man es auch später, also schon in dieser Vorlesung ein zweites
Mal brauchen kann und in anderen Vorlesungen sowieso.
Es geht jetzt noch mal um Relationen.
Und zwar stellen Sie sich jetzt einfach mal vor binäre Relationen,
also zweistellige Relationen.
Also das heißt, Sie haben eine Relation R zum Beispiel, die ist eine
Menge von Paaren, nicht unbedingt alle, aber manche Paare aus M1 kreuz
M2, also die erste Komponente aus M1, die zweite aus M2.
Das kann man sich so hinmalen, indem man für M1 und M2 so kringel
hinmalt mit Pünktchen für die Elemente da drin und ein Pfeil von einem
Element in M1 zu einem aus M2, wenn das Paar halt in der Relation drin
ist.
Also stellen Sie sich vor, man hat eine Relation R, Teilmenge von M1
kreuz M2 und man hat eine zweite Relation S von Teilmenge von M2 kreuz
M3.
Die heißen jetzt hier formal M1, M2, M3, die Mengen, das darf
natürlich alles die gleiche Menge sein, das ist nicht verboten.
Das Wichtige ist jetzt hier nur bei R und S.
Die zweite Menge bei R ist die erste Menge bei S.
Und wenn Sie S hinmalen, können Sie also wieder so in Bildchen Pfeile
von Elementen in M2 zu Elementen in M3 malen.
Und dann definiert man etwas, das heißt das Produkt der Relationen und
schreibt S kringel R und das lese ich auch wieder wie schon bei
Funktionskomposition und das ist einfach die Verallgemeinerung jetzt
auf Relationen S nach R im Zweifelsfalle.
Das sind jetzt Paare aus M1 kreuz M3 und man nimmt die Paare X, Z, wo
das X in M1 und das Z in M3 ist, mit der Eigenschaft, also R haben Sie
hier die Pfeile, S haben Sie die Pfeile und wenn es Ihnen jetzt
gelingt ein Y zu finden, sodass Sie in R von X nach Y kommen und in S
von diesem gleichen Y nach Z, dann sagen Sie X, Z ist in S kringel R.
Also wenn Sie hier von dem Element oben links über das ganz rechts in
M2 zu dem in der Mitte von M3 kommen, dann in S kringel R ist eben von
oben links nach unten in der Mitte.
So.
Das ist Relationenprodukt und das ist einfach, also wir haben ja
eingeführt Abbildungen als spezielle Relationen und dafür haben wir
schon Komposition von Funktionen definiert und das passt genau
zusammen mit dem hier.
Können Sie sich nochmal angucken, das ist einfach die
Verallgemeinerung für Relationen.
Bei Relationen, also manchmal schreibt man ja das Relationssymbol
zwischen die beiden Dinge, sie schreiben nicht 5, 7 aus kleiner gleich
Relation, sondern sie schreiben 5 kleiner gleich 7.
Also mit anderen Worten, X steht in Relation S kringel R zu Z, genau
dann wenn es ein Y gibt mit X, R, Y und Y, S, Z.
Beobachtung, nur so am Rande, man kann damit harmlos rechnen, wenn Sie
noch eine dritte Relation T haben von M3 nach M4 und Sie machen hier
also einmal T nach S in Klammern nach R und andererseits T nach in
Klammern S nach R, dann ist das die gleiche Relation.
Also man kann da immer fröhlich Klammern verschieben, macht keinen
Unterschied und man kann sie auch weglassen.
Wir hatten schon die identische Abbildung bei Funktionskomposition.
Wenn Sie das als Relation hinschreiben, ist das natürlich die Menge
aller Paare X, X, Funktionswert von X ist wieder X.
Und das sind die neutralen Elemente, jetzt nicht nur bei
Funktionskomposition, auch bei Relationenprodukt, jede Relation R
kringel Identität auf der ersten Menge von R ist wieder R und analog
auf der anderen Seite.
Das ist ganz harmlos, da muss man nicht groß was auswendig lernen, das
ist natürlich, das macht man automatisch.
Und eine Relation, die wir gerade hatten bei kontextfreien
Grammatiken, war ja aus einem Wort in einem Ableitungsschritt, ich
kann ein nächstes Wort erhalten.
Und dann wollten wir gerne drüber reden, ja nicht in einem Schritt,
sondern in mehreren Schritten, in zwei Schritten, in drei Schritten,
in irgendeiner Anzahl Schritten.
Und das haben wir da erstmal ad hoc für ein Ableitungsschritt
hingeschrieben.
Das können Sie jetzt allgemein für Relationen hinschreiben.
Also wenn R irgendeine Relation ist, die jetzt eine Teilmenge ist von
M kreuz M, also zweimal das Gleiche, die gleiche Menge M, so dass Sie
dann auch so etwas wie R kringel R hinschreiben können.
Dafür muss ja die zweite Menge, also das M gleich der ersten Menge des
anderen Faktors sein.
So und dann definiert man immer gerne R hoch 0 ist die Identität und
dann induktiv R hoch i plus 1 ist R hoch i kringel R.
Und das passt genau zur Definition von Funktionskompositionen, können
Sie nachgucken.
Das ist einfach das Gleiche, sonst würde man da nicht, wenn das etwas
völlig anderes wäre, würde man nicht die gleiche Notation verwenden.
Und R hoch i sagt Ihnen sozusagen, also Sie kommen von einem Element,
in dem Sie i mal immer zu einem nächsten Element gehen, das jeweils in
Relation steht zum vorhergehenden, Sie kommen zu dem da hinten in i
Schritten.
Und dann in Analogie zum Ableitungspfeil Stern mich interessiert die
Anzahl Schritte nicht mehr, definiert man R-Stern und das ist dann
auch einfach die Vereinigung der R hoch i.
Irgendeine Anzahl von Schritten für i aus N0.
Und dieses R-Stern für eine Relation R nennt man die reflexiv
-transitive Hülle von R.
So, ja, da muss man jetzt wieder ein bisschen Gefühl dafür entwickeln,
also nehmen wir ein einfaches Beispiel, also als Grundmenge nehmen wir
die nicht-negativen ganzen Zahlen N0 und nehmen wir eine Relation R
auf, also Teilmenge von N0 kreuz N0, nämlich R sei die Menge aller
Paare der Form eine Zahl N und die nächstgrößere Zahl N plus 1.
Also salopp gesagt, R erlaubt Ihnen von einer Zahl zur einsgrößeren
Zahl zu gehen.
Die stehen in Relation, alle N, N plus 1.
Was ist dann R-Kringel-R?
Jetzt einfach Definition von Relationen Produkt hingeschrieben, noch
nichts nachgedacht.
Das ist die Menge aller Paare N, M mit der Eigenschaft, es gibt ein K,
sodass N K aus ersten Faktor, R, rechten Faktor und K M aus linken
Faktor, auch R.
Also N K aus R heißt K ist N plus 1.
In R steht die zweite Komponente ist genau eins größer als die erste,
also wenn N K in R ist, ist K N plus 1 und wenn K M in R ist, ist M K
plus 1.
Also da muss K N plus 1 sein und M K plus 1 mit anderen Worten M muss
N plus 2 sein.
K ist N plus 1 und noch eins drauf.
Das heißt R-Kringel-R sind alle Paare der Form N N plus 2.
R hoch 0 war definiert stumpf als Identität, also R hoch 0 sind alle
Paare N, N.
R hoch 1 kann man nachrechnen, ist einfach R, wieder so wie man es
erwartet.
Also R hoch 1 sind alle Paare N, N plus 1.
R hoch 2 sind alle Paare N, N plus 2.
Ja und dann können Sie Induktion machen, R hoch I ist alle Paare der
Form N, N plus I.
Und was ist dann R-Stern?
Die Vereinigung aller dieser Paare hier N, N oder N, N plus 1 und N, N
plus 2, N, N plus 3, N, N plus 4.
Das heißt es sind alle Paare, wo die zweite Komponente größer gleich
der ersten ist.
Also R-Stern ist dann einfach die Menge aller Paare N, N mit N kleiner
gleich M.
Das ist einfach die kleiner gleich Relation.
Dann haben Sie das hier mal hingeschrieben zum Beispiel als reflexiv
transitive Hülle.
Warum heißt das Ding reflexiv transitive Hülle von R?
Das hat drei Gründe, nämlich erstens es ist reflexiv, zweitens es ist
transitiv und zweitens es ist die Hülle.
Also was soll das bedeuten?
Erstens, wann heißt eine Relation reflexiv?
Das ist jetzt einfach eine Definition und die ist wichtig, die taucht
auch noch mehrfach auf hier und anderswo.
Eine Relation heißt reflexiv, wenn für jedes X, also eine binäre
Relation auf einer Menge M, wenn für jedes X gilt, X steht in Relation
zu sich selber.
Also wenn Sie ans kleiner gleich denken, jede Zahl ist kleiner gleich
sich selber, ist reflexiv.
Aber zum Beispiel die Relation echt kleiner ist nicht reflexiv.
Es ist nicht so, dass jede Zahl echt kleiner als sie selber ist.
Es gibt auch nicht reflexive Relationen.
Das ist Reflexivität, Transitivität und Reflexivität können Sie salopp
so sagen, also was heißt salopp oder kurz, die Identität ist Teilmenge
von R.
X, X ist in der Identität sind alle Paare X, X und wenn das Teilmenge
von R ist, dann ist also X, X in R für jedes X und das ist genau das,
was hier steht.
Transitivität können Sie auch kompakt so hinschreiben, R Kringel R ist
Teilmenge von R.
Mit anderen Worten, wann immer etwas hier in der linken Seite drin
ist, das heißt, wann immer X in Relation zu Y steht und Y in Relation
zu Z, dann ist ja X, Z in der linken Relation.
Dann muss auch das in der rechten Relation sein, also dann muss auch X
in Relation zu Z stehen.
Also eine Relation ist transitiv, wenn für alle X, Y und Z aus M gilt,
wenn X in Relation zu Y steht und Y in Relation zu Z, dann X in
Relation zu Z.
Beispiel kleinergleich, wenn X kleinergleich Y ist und Y kleinergleich
Z, dann in der Tat ist X kleinergleich Z.
Deswegen kleinergleich ist transitiv.
Oder Ableitungsrelation, wenn Sie aus Wort W1, Wort W2 ableiten
können, in irgendeiner Anzahl Schritten und wenn Sie aus Wort W2 ein
Wort W3 ableiten können, in irgendeiner Anzahl Schritten, dann können
Sie auch aus Wort W1 das Wort W3 ableiten, in irgendeiner Anzahl
Schritten.
Die ist dann halt ein bisschen größer.
So.
Ja, und jetzt R-Stern, die reflexiv-transitive Hülle.
Warum heißt die so?
Erstens, sie ist reflexiv.
Also die Behauptung ist, R-Stern ist immer eine reflexive Relation.
Die Definition gerade war, Identität ist Teilmenge davon.
Jo, das stimmt.
Identität ist ja einfach R hoch 0 und R-Stern war die Vereinigung
aller R hoch i, also insbesondere R hoch 0 ist dabei.
Also ist das erfüllt, also ist R-Stern reflexiv.
Dann kann man sich überlegen, Klammer auf, beweis durch Induktion,
Klammer zu, für alle i und j aus N0, R hoch i kringel R hoch j ist
immer R hoch i plus j.
Für den Fall j gleich 1 ist das nahezu die Definition von R hoch i und
also der Induktionsanfang ist fast geschenkt und dann der
Induktionsschritt, naja, schreibt man halt hin mit Assoziativität von
Relationen im Produkt.
Und wenn man das hat, dann kann man auch leicht sehen, dass R-Stern,
also die reflexiv-transitive Hülle, diese Relation immer transitiv
ist, denn, also stellen Sie sich vor, was muss man zeigen, wenn xy in
der Relation ist und yz, dann ist auch xz in der Relation.
Also, wenn xy aus R-Stern ist, R-Stern ist die Vereinigung aller
dieser R hoch i, wenn xy da drin ist, dann ist also das Par xy in
irgendeiner von diesen Potenzen, in irgendeinem R hoch i drin.
Also, wenn es in R-Stern ist, dann in einem R hoch i, anders kommt man
da nicht rein.
Genauso yz, wenn das in R-Stern ist, dann ist das in irgendeinem R
hoch etwas, sagen wir R hoch j.
So, und wenn xy in R hoch i ist und yz in R hoch j, dann xz ist in R
hoch i Kringel R hoch j.
Das ist, wenn wir das glauben, R hoch i plus j und das ist natürlich
auch Teilmenge von R-Stern und dann haben wir das xz in R-Stern ist,
transitiv.
So, und warum heißt das reflexiv transitive Hülle?
Naja, also hier ist ein Regensturm, den brauchen wir heute vielleicht
noch oder schon, wie es aussieht.
Also, da ist eine Hülle außenrum, die kann man leicht abmachen, aber
leider ganz schlecht immer wieder außenrum machen, weil die so eng
ist.
Die ist nicht besonders groß, grad groß genug, dass der Schirm
reinpasst.
Und seinen Dienst erfüllt, ihren Dienst erfüllt die Hülle.
Also, so eine Hülle ist nicht besonders groß, die ist möglichst klein,
so dass sie die Hülle ist für das, was sie umhüllen soll und die
Eigenschaften hat, die man gerne möchte.
Behauptung, R-Stern ist möglichst klein, so dass erstens das ganze R
drin ist, der Regenschirm ist drin in der Hülle und zweitens es
erfüllt, diese Hülle hat die Eigenschaften, die man gerne möchte,
nämlich es ist reflexiv und transitiv.
Also Behauptung ist, R-Stern ist tatsächlich die kleinste Relation,
die alles enthält, was in R ist und reflexiv ist und transitiv ist.
Also insbesondere, wenn R selber schon reflexiv und transitiv ist,
dann sollte R-Stern gleich R sein.
Und wenn R selber noch nicht reflexiv oder noch nicht transitiv oder
keines von beiden ist, dann sollte nur möglichst wenig dazu genommen
sein, so dass sich gerade eben aus dem R etwas Größeres ergibt, was
gerade reflexiv und transitiv ist.
Und das ist so.
Also Behauptung R-Stern, also erstens, R-Stern ist größer als R, denn
R ist R hoch 1, das ist bei R-Stern mit dabei, und es ist reflexiv und
es ist transitiv.
Also salopp gesagt, es ist schön und der Regenschirm passt rein, jetzt
muss man sich auch überlegen, dass es nicht unnötig groß ist.
Kein großer Seesack, wo ich halt locker einen Schirm reinstecken kann,
sondern möglichst klein.
Wie zeigt man das?
Wenn man irgendwas hat, wo der Regenschirm reinpasst, also wenn man
eine beliebige Relation hat, die reflexiv ist und transitiv ist und
ganz R ist drin, dann sogar die reflexiv-transitive Hülle ist so
klein, die passt dann auch noch in S rein.
Also die reflexiv-transitive Hülle ist das kleinste Ding, wo Sie den
Regenschirm reinkriegen.
Und wie beweist man das?
Man muss dann noch zeigen, wenn S R enthält und reflexiv und transitiv
ist, dann sogar R-Stern ist drin und das wissen Sie, sobald Sie
wissen, dass jedes R i Teilmenge von S ist.
Und wie macht man das?
Induktion und für i gleich 0 und i gleich 1 banal und so.
Und dann R i plus 1 ist ja R i kringel R und nach
Induktionsvoraussetzung R i ist Teilmenge von S und nach der anderen
Voraussetzung R ist Teilmenge von S, also ist das Teilmenge von S
kreuz S und weil das transitiv ist, ist das Teilmenge von S und Sie
sind fertig.
Gut.
Also das, was man hier kriegt, denken Sie nochmal an kontextfreie
Grammatiken und Ableitbarkeit von Wörtern aus dem Startsymbol oder so.
Also Sie kriegen auch in einem gewissen Sinne also die formale
Sprache, die von der kontextfreien Grammatik erzeugt wird, in
irgendeinem Sinne, das ist das kleinste Ding, was Sie kriegen können,
was irgendeine nette Eigenschaft hat.
Und wenn Sie sich noch ein bisschen früher erinnern, formale Sprachen
und Gleichungssysteme, die Lösungen sind nicht eindeutig, ja im
Allgemeinen nicht, aber die formale Sprache, die eine Grammatik
erzeugt, das liefert Ihnen sozusagen die kleinste, die in
Anführungszeichen natürliche Lösung für das Gleichungssystem.
Da sind jetzt viele Händewedeleien noch dabei und Anführungszeichen,
das kann man präziser machen, sehen wir vielleicht am Ende der
Vorlesung noch.
Und wenn nicht hier, dann sehen Sie es woanders.
Gut.
Also und das Beispiel schlechthin für reflexiv-transitive Hülle ist
Ableitbarkeit bei kontextfreien Grammatiken.
Und Sie sollten halt so ein bisschen üben, dann über Reflexivität,
Transitivität nachzudenken, irgendwie zu beweisen, eine Relation hat
so eine Eigenschaft und vielleicht mal ein Bildchen zu malen, um zu
sehen, wie sieht das denn aus.
Das geht natürlich nur für wenig Elemente, also nicht, wenn die
Grundmenge unendlich ist, aber immerhin.
Gut.
So.
Und dann kommen wir jetzt zu dem letzten Abschnitt, wo ich Ihnen schon
mal zeigen will, dass man mit kontextfreien Grammatiken auch nicht
alles machen kann.
Und ich habe ja vorhin gesagt, was man zum Beispiel mit kontextfreien
Grammatiken nicht schön ausdrücken kann, ist sowas wie in einem
Programm alle Variablen, die irgendwo benutzt werden, müssen vorher
deklariert sein.
Genau das, dass man das nicht mit kontextfreien Grammatiken machen
kann, das werden wir nicht beweisen, aber jetzt seien Sie mal ein
bisschen flexibel, sowas ähnliches.
Also
betrachten wir die folgende formale Sprache, eine gewisse Menge von
Wörtern, in denen As, Bs und Cs vorkommen dürfen.
Ich habe die LVV genannt und die Wörter, die dazu gehören, sind alle
Wörter, die so aussehen.
Da steht ein C und zwar in der Mitte und davor steht irgendein Wort
aus As und Bs, irgendein Wort V und hinter dem C muss genau das
gleiche Wort V aus As und Bs nochmal stehen.
Also interpretieren Sie das jetzt vielleicht so ein bisschen
großzügig, als vor dem C steht die Variable so als Deklaration und
dahinter taucht sie jetzt dann nochmal auf und nur das.
Also zu der formalen Sprache gehören nur diese Wörter, genau ein C
genau in der Mitte und davor und dahinter genau das gleiche Wort aus
As und Bs.
Und wir wollen zeigen, es gibt keine kontextfreie Grammatik, die genau
diese formale Sprache erzeugt.
Geht nicht.
Da muss man argumentieren über alle unendlich vielen kontextfreien
Grammatiken.
Und es wird ein bisschen länglich.
Also nochmal, die Wörter, die dazugehören, in der Mitte ein C und das,
was davor steht aus As und Bs, also zum Beispiel A, A, B, A, muss
dahinter exakt genauso nochmal stehen.
Es können auch nur As oder nur Bs sein.
Ja, B hoch 3, C, B hoch 3, ist in Ordnung.
Was nicht in Ordnung ist, ist, wenn vor dem C was anderes steht als
dahinter.
Also vorne steht A, A, B, A, hinten steht A, A, B, B, das ist böse.
Wenn vor und hinter dem C unterschiedlich lange Wörter stehen, dann
erst recht können die nicht gleich sein.
Natürlich, wenn nicht mal die Länge passt.
Und es dürfen auch nicht mehrere Cs vorkommen.
Es muss immer genau eins sein.
Und es darf auch nicht sein, dass gar kein C da ist.
Das ist auch böse.
Also ich hoffe, Sie haben eine Vorstellung von den Wörtern, die wir
haben wollen.
Genau ein C, genau in der Mitte, davor und dahinter, exakt das
Gleiche.
Behauptung, genau diese Wörter und nur die mit einer kontextfreien
Grammatik zu erzeugen, geht nicht.
So, wie machen wir das?
Also erstens, wir machen uns klar, oder ich behaupte, dass man gar
nicht alle kontextfreien Grammatiken angucken muss, sondern nur
manche.
Das sind dann immer mal ein paar weniger, es sind immer noch unendlich
viele, aber weniger.
Von den verbleibenden Grammatiken, die haben eine schöne Eigenschaft
und die benutzen wir dann, um zu zeigen, wenn man so eine Grammatik
hat, genau die Wörter erzeugen aus LVV, das kann nicht klappen.
Erstens, ohne dass wir das beweisen wollen, Mitteilung.
Wenn Sie eine kontextfreie Grammatik haben, die irgendeine formale
Sprache erzeugt und das leere Wort gehört nicht dazu, zu den erzeugten
Wörtern.
Alle Wörter, die erzeugt werden, enthalten mindestens ein
Terminalsymbol.
Dann kann es sein, obwohl Sie nicht das leere Wort am Ende erzeugen,
dass Sie zwischendrin manchmal irgendwelche Nicht-Terminalsymbole
durch das leere Wort ersetzen.
Dann können Sie aber diese Grammatik immer umbauen, und das kann man
automatisieren, das ist kein Hexenwerk, aber dass Sie die gleiche
formale Sprache mit einer anderen kontextfreien Grammatik erzeugen und
da bei keiner Produktion ist die rechte Seite das leere Wort.
Jede Produktion ersetzt ein Nicht-Terminalsymbol durch etwas, was
wieder mindestens ein Symbol ist.
Also in jedem Ableitung ist Schritt, das wird höchstens länger, nie
kürzer.
Es kann nur länger werden, nicht kürzer.
Eine Grammatik, die so ist...
Achso, und unser LVV ist so, das leere Wort gehört nicht dazu, weil
wir immer mindestens das C in der Mitte haben.
Und deswegen also es reicht, wenn wir uns auf solche Grammatiken
beschränken, die nennt man epsilonfrei, keine Produktion hat das leere
Wort als rechter Seite, und nur die müssen wir uns angucken, und wenn
wir für die epsilonfreien beweisen können, keine erzeugt LVV, dann
sind wir schon fertig.
Und keine erzeugt LVV heißt, jede epsilonfreie, kontextfreie Grammatik
erzeugt etwas, was nicht LVV ist.
Das ist das, was wir beweisen müssen.
Und dann müssen wir jetzt nur noch die epsilonfreien angucken.
Hurra.
So, und wenn man jetzt nur noch epsilonfreie Grammatiken angucken
muss, dann hat man es ein bisschen leichter.
Dann gilt nämlich das hier.
Das ist jetzt etwas länglich, die Aussage füllt immerhin einen Gußteil
der Folie, aber das, was da steht, ist auch nicht hochkompliziert.
Also, nehmen Sie an, Sie haben eine kontextfreie Grammatik und das
leere Wort kommt in keiner Produktion vor.
Wenn Sie ableiten, es wird höchstens länger, nie kürzer.
Die Grammatik hat endlich viele Produktionen.
Jede rechte Seite hat irgendeine Länge.
Da steht mal ein Symbol, mal drei Symbole, mal zwei Symbole.
Und da gibt es eine maximale Länge der rechten Seiten von diesen
endlich vielen Produktionen.
Diese maximale Länge, die vorkommt, nennen wir die mal klein l.
Das ist die größte Länge einer rechten Seite irgendeiner Produktion.
Behauptung.
Wenn Sie jetzt irgendein k größer gleich null nehmen und Sie nehmen
ein Wort, das mehr als L hoch K Symbole enthält.
Wenn Sie jetzt was ableiten können aus irgendeinem Nicht
-Terminalsymbol, das dieses Wort enthält mit mehr als L hoch K
Symbolen und vielleicht noch irgendwas links und rechts, irgendein X
und ein Y.
Dann, wenn Sie sich den Ableitungsbaum hinmalen, aus dem Nicht
-Terminalsymbol X das Wort W und noch so ein bisschen schnick schnack
außen rum.
Von der Wurzel des Ableitungsbaumes von dem X zu den Terminalsymbolen
in diesem langen Wort W mit mehr als L hoch K Symbolen, da gibt es
mindestens einen Weg, der ist ziemlich lang.
Da kommen mindestens K plus 1 Nicht-Terminalsymbole vor.
Und zwar solche Nicht-Terminalsymbole, wo es sich immer echt
verzweigt.
Also es kann ja auch Nicht-Terminalsymbole geben, die ersetzen Sie nur
durch ein Nicht-Terminalsymbol wieder.
Aus X wird Y.
Das interessiert einen nicht.
Also wenn Sie ein langes Wort, wenn Sie was ableiten können, was ein
langes Teilwort enthält, dann in der Ableitung zu dem mindestens einem
Symbol Sie müssen sich ziemlich oft verzweigen, sonst kann das nicht
klappen.
Stellen Sie sich vor, Sie haben diesen Ableitungsbaum für X, W, Y und
W ist ganz lang.
Das erste, was wir machen ist, wir streichen das X und das Y und
alles, was da hinführt.
Was übrig bleibt, ist jetzt nicht mehr ein Ableitungsbaum, der
Grammatik, aber immer noch so ein Baum.
Habe ich hier hingemalt, da oben ist immer noch die Wurzel, die runden
Kringel, das sind sozusagen die Nicht-Terminalsymbole und die Blätter,
das sind die Terminalsymbole und das sind auch alles Terminalsymbole,
kein Blatt ist das leere Wort, weil wir das nicht haben, alles Y-frei.
So, dann haben Sie so ein Ding.
Jetzt gibt es in diesem Baum Nicht-Terminalsymbole, die werden ersetzt
durch etwas, was länger ist als ein Symbol.
Also zwei oder drei oder hier an der Wurzel habe ich mal so getan, als
wäre die rechte Seite vier Symbole lang.
Also die Nicht-Terminalsymbole, die mindestens zwei Nachfolger haben,
die habe ich jetzt mal schwarz gemalt und dann gibt es noch Nicht
-Terminalsymbole, die haben nur einen Nachfolger, die habe ich weiß
gelassen.
Aus X wird Y, aus Y wird Z oder irgend sowas.
Und jetzt diese ganzen weißen Nicht-Terminalsymbole hier, diese
längeren Pfade, wo sich nicht viel tut, die entfernen wir jetzt
einfach mal.
Dann bleibt noch sowas übrig.
Dann bleiben nur noch die schwarzen Nicht-Terminalsymbole übrig, wo
sich bei jedem etwas verzweigt und unten die Blätter, die ganzen
Terminalsymbole.
Das ist immer noch ein Baum, wenn auch schon längst kein
Ableitungsbaum mehr, aber es ist ein Baum.
Und jetzt haben wir nur noch die schwarzen, das heißt an jedem Nicht
-Terminalsymbol es verzweigt sich in mindestens zwei Nachfolger oder
drei und maximal L.
L ist die größte Länge von rechten Seiten.
So, das haben wir jetzt.
Jetzt stellen Sie sich mal vor, diese Pfade von der Wurzel zu
irgendeinem Terminalsymbol hätten alle höchstens eine Länge K.
Wie könnte das aussehen?
Wenn K gleich 1 ist, dann müssen Sie also gleich im ersten Schritt zu
lauter Terminalsymbolen kommen.
Von der Wurzel zu den Blättern nur ein Nicht-Terminalsymbol, also die
Wurzel und gleich danach die Blätter sind Terminalsymbole.
Wenn Sie auf dem Weg zum Blatt nur ein Nicht-Terminalsymbol haben
können, dann das längste, was Sie ableiten können, sind Wörter der
Länge L, also jetzt hier in Beispiel 4.
Wenn Sie erlauben, dass Sie auf dem Weg zu den Terminalsymbolen zwei
Nicht -Terminalsymbole sehen, dann maximal, was Sie erzeugen können,
sind Wörter der Länge L mal L, L².
Größeren Verzweigungsgrad kriegen Sie nicht hin, weil L das Maximum
ist, was Ihre Grammatik hergibt.
Und dann machen Sie halt auf jedem Pfad möglichst oft möglichst große
Verzweigungen.
Und wenn die Pfade alle höchstens zwei lang sein dürfen, ist das das
Beste, was Sie hinkriegen.
Also wenn Sie nur ein Nicht-Terminalsymbol auf jedem Pfad haben
dürfen, dann können Sie nur Wörter der Länge L hoch 1 ableiten.
Wenn Sie zwei haben, L hoch 2.
Wenn Sie K haben, höchstens Wörter der Länge L hoch K.
Und wenn Sie jetzt aber ein Wort haben wollen, dessen Länge größer ist
als L hoch K, dann muss es mindestens einem Pfad geben, wo Sie K plus
1 Nicht-Terminalsymbole haben.
Gut.
Und das ist das Wesentliche, was wir gleich benutzen werden.
Jetzt wollen wir den wesentlichen Beweis machen.
Also wenn wir jetzt irgendeine Grammatik haben, kontextfrei und
epsilonfrei, das ist ohne Beschränkung der Allgemeinheit, Behauptung,
die erzeugt irgendeine formale Sprache, L von G, Behauptung immer, L
von G ist nicht das LVV.
Nicht genau die Wörter mit einem C in der Mitte und rechts davon das
gleiche Wort V.
Also gut.
Wie beweisen wir das?
Hier ist irgendeine kontextfreie Grammatik.
Das Einzige, was wir wissen, epsilonfrei.
Und jetzt müssen wir beweisen, für diese konkrete Grammatik, sie ist
ja beliebig gewählt, sie erzeugt nicht genau LVV.
Also es gilt nicht L von G gleich LVV und L von G gleich LVV heißt LVV
ist Teilmenge von L von G und L von G ist Teilmenge von LVV.
Das ist nicht der Fall.
Das müssen wir beweisen.
Das ist äquivalent dazu, dass entweder nicht LVV Teilmenge von L von G
ist oder nicht L von G Teilmenge von LVV ist.
Das ist das, was wir beweisen müssen.
bis hierher in dieser Argumentation, wir haben überhaupt nichts
Magisches getan.
Das ist einfach nur Umformulierung, was haben wir eigentlich als
Aufgabe.
So das ist das, was wir zeigen müssen.
Nicht LVV Teilmenge von L von G oder nicht L von G Teilmenge von LVV.
Und jetzt machen wir eine Fallunterscheidung und jetzt bitte bringen
Sie das nicht durcheinander mit den beiden Zeilen, die hier als
letztes im Moment noch stehen.
Es gibt jetzt nur zwei Möglichkeiten.
Nämlich LVV ist nicht Teilmenge von L von G oder LVV ist Teilmenge von
L von G.
Eins von beidem ist der Fall.
Auf jeden Fall.
So.
Erster Fall.
LVV ist nicht Teilmenge von L von G.
Oh ja, dann sind wir fertig.
Dann kann nicht LVV gleich L von G sein.
Das war leicht.
Bleibt also nur der andere Fall.
LVV ist Teilmenge von L von G.
Also was haben wir jetzt?
Wir haben eine beliebige kontextfreie Grammatik, epsilonfrei.
Und jetzt müssen wir noch was tun, aber jetzt haben wir wieder eine
zusätzliche Information.
Wir dürfen annehmen, also die Grammatik erzeugt jedenfalls alle Wörter
aus LVV.
Das haben wir jetzt zusätzlich als Hilfsmittel, können wir einsetzen
und müssen jetzt aber zeigen, die andere Inklusion geht kaputt.
Die Grammatik erzeugt nicht nur solche Wörter, sondern auch ein Wort,
das nicht in LVV ist.
Und dann haben wir jetzt wieder weniger Grammatiken, die wir angucken
müssen.
Jetzt müssen wir nur noch die angucken, die epsilonfrei sind.
Und wir können uns darauf beschränken, dass sie jedenfalls alle Wörter
aus LVV erzeugt.
Und das müssen wir jetzt irgendwie einsetzen, um zu beweisen, sie
erzeugt dann aber auch was, was nicht in LVV ist.
Also gut.
Das ist das, was jetzt noch übrig bleibt.
Also wir müssen zeigen, die Grammatik erzeugt ein Wort, das nicht in
LVV ist.
Irgendein Wort W-Strich.
Für jede kontextfreie Grammatik G mit bla bla bla.
Da wird es jetzt wahrscheinlich nicht das gleiche Wort W-Strich für
alle Grammatiken tun.
Da wird man jetzt also bei der Wahl des Wortes W-Strich irgendwie
einfließen lassen, mit welcher Grammatik hat man es denn zu tun.
Was kann man einfließen lassen?
Also konkret welche Produktionen die Grammatik benutzt, das weiß man
nicht.
Da könnte man jetzt natürlich auch noch versuchen, irgendwas
herauszufinden, weil ja alle Wörter aus LVV erzeugt werden, aber das
tun wir nicht.
Was wir ansonsten wissen ist, die Grammatik hat eine gewisse Anzahl
Nicht -Terminalsymbole.
K-Stück.
Und die Produktionen, die rechten Seiten von den Produktionen, die
haben eine maximale Länge der rechten Seiten.
Klein l.
Und jetzt, das fällt jetzt vom Himmel für Sie.
Aber da ist jetzt halt der Trick.
Also wenn k die Anzahl der Nicht-Terminalsymbole in der Grammatik ist
und l die längste Länge einer rechten Seite von den Produktionen, dann
betrachten wir jetzt mal das Wort w a hoch 1 plus l hoch k plus 1 und
b hoch 1 plus l hoch k plus 1 und dann ein c und dahinter das gleiche
Wort nochmal.
Also dieses Wort ist aus LVV.
Vorne steht etwas und dann genau ein c in der Mitte und dahinter
nochmal das gleiche.
Gut.
Und wir wissen, unsere Grammatik erzeugt alle Wörter aus LVV, also es
gibt einen Ableitungsbaum für dieses Wort.
Und wir wissen, dieses Wort offensichtlich hat eine Länge, die ist
größer als l hoch k.
Und dann wissen wir, nach dem Lemma von eben, in dem Ableitungsbaum
für dieses Wort w von der Wurzel zu den Terminalsymbolen in w, da muss
es mindestens einen Pfad geben, auf dem k plus 1 nicht Terminalsymbole
vorkommen.
Länge größer als l hoch k.
Also auf einem Weg zu mindestens einem Symbol k plus 1 nicht
Terminalsymbole.
Und jetzt sind wir am entscheidenden Punkt.
Überlegen Sie mal kurz, was jetzt offensichtlich der Fall sein muss.
Versuchen Sie mal noch nicht an die Mensa zu denken.
Merken Sie was?
Hand hoch, wer merkt was?
Sagen Sie es mal laut.
Na doch, es kann schon sein.
Aber wir haben nur k verschiedene nicht Terminalsymbole.
Und wenn wir jetzt auf diesem Weg zu einem Terminalsymbol k plus 1
nicht Terminalsymbole haben, dann muss eins doppelt vorkommen.
Na gut, kommt es halt doppelt vor.
Da, also da ist außenrum irgendetwas und dann gibt es ein nicht
Terminalsymbol und das taucht zweimal auf, auf dem Weg zu irgendeinem
Terminalsymbol in dem großen Wort.
Das gibt es für mindestens ein Terminalsymbol und jetzt suchen wir uns
mal ein Terminalsymbol, wenn Sie da von unten nach oben gucken, wie
weit müssen Sie zurückgehen, wo Sie möglichst früh das zweite
Vorkommen sehen.
Also das Ganze möglichst weit unten.
Sondern gestatten Sie mir noch
Ach ne, noch fünf Folien, das prügel ich jetzt nicht durch.
Das war es für heute, das nächste Mal schauen wir mal, was daraus
folgt. Dankeschön.