So, einen schönen guten Morgen.
Nehmen Sie Platz.
Machen Sie es sich bequem.
Wir legen los.
Wir waren letztes Mal stehen geblieben bei den Befehlen, den
Maschinenbefehlen der minimalen Maschine.
Die minimale Maschine als Beispiel einer von Neumann-Architektur, die
alles das kann, was auch ein normaler Rechner so kann, aber mit
möglichst wenig Komponenten und mit einem möglichst geringen
Befehlssatz auch auskommen kann.
Wir waren letztes Mal stehen geblieben bei den Datentransportbefehlen,
hatten die uns angeschaut.
Wir hatten sowas gesehen, wie man Konstanten laden kann, wie man
Adressenwerte aus Adressen laden kann, wie man Werte an Adressen
wieder abspeichern kann, jeweils Transport aus dem Akku und in den
Akku.
Wir hatten uns nochmal vergegenwärtigt, dass so ein Wert im Speicher
der MIMA, der ist selber 24 Bit lang und der kann entweder ein Befehl
sein oder er kann Daten sein.
Wenn er ein Befehl ist, dann sind nur die letzten 20 Bit eventuell
sowas wie eine Konstante, die ich mit Load-Constant laden kann, weil
die ersten vier Bit dann entsprechend den Befehl kodieren, diesen Load
-Constant -Befehl.
Und da das Ganze also in Zweierkomplementdarstellung ist, die MIMA
arbeitet in Zweierkomplementdarstellung, heißt das insbesondere, dass
wir also bei Load-Constant aufpassen müssen.
Da können wir nicht einfach jede beliebige Konstante laden, sondern
wir können nur das laden, was man im Zweierkomplement darstellen kann
mit einer Zahl, die hat 24 Bit und die ersten vier Bit von links
gerechnet, die sind alle Null.
Dann gab es noch diese Befehle zum indirekten Laden und indirekten
Speichern.
Das heißt, ich schaue bei dem Befehl nach an einer Adresse im Speicher
und diese Adresse, die da bei einer Adresse im Speicher und der Wert
an dieser Adresse, der ist selber wieder eine Adresse.
Und diese Adresse, die dann an der Stelle im Speicher steht, die nehme
ich, um entweder von dort zu laden oder dahin zu speichern.
Einfaches, simples Beispiel, wir haben wieder den Akku und zwei Zellen
aus dem Speicher hier geschrieben und wenn jetzt zum Beispiel an der
Stelle 46 im Speicher steht 81, dann macht Load Value 46, lädt die 81
in den Akku.
Wenn ich aber sage, Load Indirect Value 46, dann guckt er an der
Stelle 81 im Speicher, was steht denn da?
Und da steht die 25 und das wird dann in den Akku transportiert.
Neben solchen Datentransport-Dingen kann man natürlich auch
arithmetische und logische Operationen ausführen.
Dafür ist die arithmetische logische Einheit, die ALU, da.
Bei der Arithmetik kann man addieren.
Da gibt es den Befehl Add, dem übergibt man eine Adresse und dann wird
der Wert, der an der Adresse im Speicher steht, auf den Wert, der im
Akku steht, drauf addiert und das ganze Ergebnis dann entsprechend
wieder im Akku abgelegt.
Oder ich habe logische Operationen.
Das sind dann bitweise, werden dort die bool'schen Funktionen
ausgeführt.
Eine 1 entspricht dem Wert wahr, eine 0 entspricht dem Wert falsch und
dann wird für jedes einzelne Bit an diesen 24 Stellen jeweils diese
Operation durchgeführt.
Wenn ich sage z.B.
end address, dann wird der Wert an der Adresse genommen und bitweise
mit dem Wert im Akku per bool'schen und verknüpft.
Bei oder per bool'schen oder, bei per XOR, bei exklusiven oder.
Ich hatte mal schon erwähnt, was das ist und dass das insbesondere
auch das gleiche ist wie Addition Modulo 2.
Das kommt auf dasselbe hinaus.
Und deswegen kann man basierend auf dem XOR ein Addierwerk bauen.
Das heißt, wenn ich zwei Werte mit XOR bitweise vergleiche, dann ist
dasselbe noch keine Addition, weil jeweils die beiden einzelnen Bits
addiert werden Modulo 2.
Da gibt es dann eventuell einen Übertrag.
Wenn ich also 1 und 1 addiere, habe ich halt einen Übertrag.
Der wird jetzt erstmal bei dem bitweisen XOR noch nicht betrachtet.
Man könnte jetzt aber ein kleines Programm schreiben, das sowas wie
Add macht, wenn man halt diesen Übertrag entsprechend mit betrachtet.
Einfaches Beispielprogramm.
Ich lade mir eine konstante 0 in den Akku.
Dann addiere ich das drauf, was an der Speicherstelle 46 steht.
Das ist die 11.
Dann addiere ich das drauf, was an der Speicherstelle 47 steht.
Das ist die 22.
Kommt 33 raus.
Dann addiere ich das, was an der Speicherstelle 48 steht.
Das ist die 33.
Kommt 66 raus.
Dann addiere ich das, was an der Speicherstelle 49 steht.
Das ist die 44.
Kommt 110 raus.
Einfaches Beispiel.
Dann kann ich als nächstes das ganze Ergebnis meiner Addition halt
wieder irgendwo abspeichern und kann so auf relativ einfache Art und
Weise eine Addition durchführen.
Dann gibt es auch einstellige Operationen auf dem Akku.
Zum Beispiel das Voolsche NOT.
Das hatten wir ja kennengelernt als einstellige Funktionen.
Das invertiert jeweils bitweise die Bits im Akku.
Ist dasselbe wie ein exklusives oder mit 11111.
Insbesondere ist das auch der erste Schritt, wenn ich zum Beispiel
etwas negieren möchte.
Wenn ich also zum Beispiel eine Zahl negieren möchte, dann kann ich
das zum Beispiel so machen, dass ich erstmal NOT rechne und dann eins
drauf addiere.
Dann hätte ich sowas wie eine Negation einer Zahl im Zweierkomplement
implementiert.
Und dann kann ich Bits noch verschieben, rotieren lassen.
Ich kann sie nach rechts rotieren lassen, wobei dann das Bit, das
rechts rausfällt aus dem Akku, vorne wieder reingesteckt wird.
Da kann man sich jetzt überlegen, für welche Operationen könnte man
vielleicht sowas verwenden.
Für was wäre sowas vielleicht sinnvoll.
Was könnte es mir bringen, wenn ich Bits hin und her rotiere.
Was könnte das für machen.
Das denken wir erstmal nur in positiven Zahlen, nicht unbedingt gleich
in negativen Zahlen.
Was bedeutet das, wenn ich da so hin und her rotieren lasse.
Das ist eine Multiplikation beziehungsweise eine Division mit 2 und
natürlich dann bei der Division eine Ganzzahldivision.
Das heißt, Reste werden nicht betrachtet, aber wenn ich halt nach
links rotiere, dann wäre das sowas wie mal 2 und wenn ich nach rechts
rotiere, ist das sowas wie eine Division durch 2.
Aber jetzt kann man sich überlegen, bei negativen Zahlen muss man
eventuell aufpassen, weil ja dann da was passiert.
Da müsste man sich also was überlegen.
Wie könnte ich da also Zahlen mit beliebigen Vorzeichen rotieren.
Kann man sich mal überlegen.
Einfache Aufgabe für zu Hause.
Dann gibt es Vergleichsoperationen.
Ich kann schauen, ist der Wert im Akku gleich einem Wert an einer
Stelle im Speicher.
Falls der gleich ist, wird der gesamte Akku auf alle Bits auf 1
gesetzt und falls die nicht gleich sind, wird der gesamte Akku auf 0
gesetzt.
Das heißt, der Akku ist ein Zweier-Komplement-Darstellung.
Minus 1 oder entsprechend 0.
Das ist jetzt so ein bisschen konterintuitiv.
Warum denn jetzt negativ und nicht positiv.
Das kann man bei manchen so typischen Sachen, die man macht,
Programmen, die man schreibt, das Ganze manchmal ein bisschen
einfacher machen.
Die Befehle in so einer MIMA, hatten wir schon gesagt, werden in der
Regel linear durchgeführt.
Also wenn ein Programm im Speicher liegt, dann nehme ich mir den
ersten Befehl, führe den aus, dann erhöhe ich den Zeiger in meinem
Instruction Address Register um 1, springe also an die nächste
Speicherzelle, führe den Befehl aus und so weiter und so fort.
Ist erstmal ausreichend für was Minimales, aber wenn man ein bisschen
kompliziertere Sachen machen will, ist das eigentlich nicht
ausreichend.
Wenn man also irgendwie Sachen haben will, die abhängen von
irgendwelchen Ergebnissen und das soll halt den Programmfluss
beeinflussen, dann reicht diese lineare Ausführung dieser einfach
immer der Reihe nach nicht mehr aus.
Und dafür gibt es dann auch entsprechende Befehle, die halt dann den
Wert im Instruction Address Register manipulieren.
Es gibt zum Beispiel den einfachen Sprung, wo ich einfach sage, okay,
jetzt bitte die Befehlsausführung an der Adresse, die ich hier angebe,
fortführen.
Wenn ich also ein Programm habe, das geht halt der Reihe nach durch,
bis ich dann irgendwann zu einem Jump-Befehl komme, da geht eine neue
Adresse und dann wird das Programm hinten an der anderen Stelle halt
weiter durchgeführt.
Das ist manchmal ganz nützlich, aber fehlt noch was, wenn ich wirklich
so bedingte Sachen machen will.
Das heißt, im Augenblick hängt das Ergebnis der Befehlsausführung noch
nicht von dem Ergebnis ab.
Ich kann zwar die Befehlsausführung woanders hart verdrahtet weiter
führen lassen, aber ich brauche noch was, um das vom Ergebnis abhängen
zu machen.
Also wenn man so eine einfache Schleife zum Beispiel hat, ich lade
eine 1, dann wird der Wert an der Speicherzelle da 11101 drauf addiert
auf die 1, dann wird das wieder zurückgeschrieben.
Das heißt, ich habe den Wert an der Speicherstelle da 11101 um 1
erhöht und dann sage ich springen wieder zurück da an die Stelle, wo
ich das LoadConstant 1 mache.
Das wäre dann eine Schleife, die immer 1 drauf addiert auf die
Speicherstelle im Zweierkomplement und das Programm hält dann hier
auf.
Das ist eine Endlosschleife.
Will man so etwas?
Nein.
Wenn man jetzt hier in der theoretischen Informatik bleibt und in den
Grundbegriffen der Informatik, wo man so die Grundlagen der
theoretischen Informatik kennenlernt, dann wollen wir das eigentlich
erstmal per se nicht.
Für uns, das werden Sie dann später kennenlernen, ist ein Algorithmus
immer endlich, muss immer in endlicher Zeit anhalten.
Ansonsten nennen wir es nicht Algorithmus.
Das ist ein relativ grundlegender Algorithmenbefehl.
Wenn Sie aber an bestimmte Programme denken, keine Ahnung,
Ampelsteuerung, dann wollen Sie nicht, dass die aufhört, sondern die
muss unendlich weiter, lange weiterlaufen.
Da gibt es keine Abbruchbedingungen, dass das irgendwann mal aufhört.
Das fällt halt noch nicht unter den Algorithmenbegriff, wie wir ihn
hier in der Vorlesung verwenden werden.
Deswegen, ja klar, wenn man praktisch programmiert, kann man sowas
wollen.
Hier bei uns in der Vorlesung wollen wir das erstmal nicht.
Und deswegen und auch allgemein, weil es für die Programmausführung
nützlich ist, gibt es halt noch einen Sprung, der dann bedingt ist.
Da hängt es dann davon ab, was an der Stelle im Akku steht, ob ich
jetzt an die Adresse, die ich dem Jump-Befehl angebe, hinspringe oder
ob ich mit dem Befehl direkt nach dem Jump-Befehl weitermache.
Der heißt halt Jump-if-negative.
Der springt an die Adresse, die ich ihm angebe, dann, wenn das
höchstwertige Bit im Akku auf 1 gesetzt ist.
Oder anders ausgedrückt, in zweier Komplementdarstellung, wenn im Akku
eine negative Zahl steht.
Und damit kann ich dann anfangen, solche Sprünge auszuführen.
Und das passt sehr gut zusammen mit der Art und Weise, wie wir zum
Beispiel Equal definiert haben.
Wenn es gleich ist, dann soll halt minus 1 im Akku stehen und wenn es
nicht gleich ist, soll es halt 0 stehen.
Das ist sozusagen dann komplementär dazu.
Da kann man sich vorstellen, dass man dann so mit Gleichheitsabfragen
halt das hinkriegen kann, dass wenn irgendwas gleich ist, dann führe
ich bitte den Sprung aus.
Einfaches Programm.
Ich lade mir den Wert an der Stelle 12 in den Akku.
Dann gucke ich, ist es der gleiche Wert wieder an der Stelle 13.
Dann mache ich den bestimmten Sprung.
Falls also M12 und M13 den gleichen Wert hatten, gibt es halt diesen
Sprung da an die weiter hinten Adresse.
Und wenn nicht, dann wird halt weiter gemacht bei dem, was hinter
diesem Jump-not-equal kam.
Manchmal verwendet man auch noch einen Befehl Halt.
Normalerweise, wenn wir hier so Programme hinschreiben, verzichten wir
da gerne drauf.
Wenn das Programm zu Ende ist, dann ist halt das Programm zu Ende.
Wenn wir also nicht mehr Befehle aufgeschrieben haben, dann gehen wir
davon aus, dass das Programm anhält.
Wenn man das irgendwie explizit machen will, dann kann man noch den
Befehl Halt hinschreiben.
Der soll halt sagen, okay, Programmausführung zu Ende.
Hier geht es nicht mehr weiter.
In einem Rechner, in einem richtigen Rechner wird das natürlich nicht
passieren.
In einem richtigen Rechner läuft immer ein Programm.
Da läuft zumindest mindestens das Betriebssystem immer weiter.
Das heißt also, dass ein Rechner wirklich tatsächlich komplett anhält.
Das ist dann nur dann der Fall, wenn Sie den Rechner sozusagen
ausschalten.
Ansonsten läuft halt, wie gesagt, immer irgendein Programm weiter.
Wenn man das, wie gesagt, irgendwie explizit machen will, dass jetzt
Schluss sein soll mit diesem Programm, das sich jetzt gerade
hingeschrieben ist, dann kann man einfach den Befehl Halt
hinschreiben.
Wenn jetzt diese MIMA einen Befehl ausführt, dann passiert das in drei
Phasen.
Ich muss also den Befehl einmal aus dem Speicher holen.
Dann muss ich das Steuerwerk anschauen, den Befehl.
Also worum geht es jetzt?
Was macht er überhaupt?
Da hatten wir schon gesagt, es gibt Befehle, bei denen steht in den
ersten 4-Bit, was gemacht werden soll.
Und es gibt Befehle, da steht in den ersten 6-Bit-Phans, glaube ich,
was gemacht werden muss.
Das heißt, da muss erst mal geschaut werden.
Ist das jetzt gemäß Präfix von der Kodierung?
Muss ich 4-Bit, die ersten 4-Bit mir rausholen?
Muss ich mir die ersten 6-Bit rausholen?
Und dann muss ich halt den Befehl ausführen.
Und wenn der Befehl dann halt eine Operation ist, führe ich die
Operation über die ALU aus.
Oder wenn es halt ein Datentransportbefehl ist, dann führe ich halt
den Datentransport mit Hilfe des Speicherwerks aus.
Und das, was da ausgeführt wird, das Steuerwerk, was das Steuerwerk da
macht, ist, dass es selber wieder kleine Programme ausführt.
Sogenannte Mikroprogramme, die im Steuerwerk kodiert sind und die dann
über die Steuerleitungen unter Zuhilfenahme gegebenenfalls des
Datenbusses die entsprechenden Operationen durchführen.
Das war das, was wir hier mit so roten Pfeilen eingezeichnet haben.
Da haben wir zum einen die Pfeile, die halt rausgehen.
Das sind halt diese Steuersignale, die gehen zum Beispiel an die ALU
oder die gehen auch zum Teil an den Speicher.
Damit werden halt Arbeitsweise von ALU und Speicher durchgeführt.
Und dann gibt es halt so Signale, die gehen rein.
Das sind sogenannte Meldesignale.
Da kommen immer die ersten 6-Bit zum Beispiel rein, damit ich den
Befehl korrekt dekodieren kann.
Sie sehen schon da, ich glaube, diese XY und Z-Register hatten wir
bisher noch nicht eingezeichnet.
Die sind halt notwendig, wenn ich solche Befehle durchführen möchte,
wie zum Beispiel dieses ADD.
Wenn ich ADD etwas mache, dann wird ja auch der Akku irgendwie auf den
was drauf addiert und das Ergebnis wieder im Akku abgelegt.
Das heißt, ich brauche also irgendwie so einen Zwischenspeicher und
das sind gerade diese XY-Register.
Dann wird also erstmal was aus dem Akku in X übertragen und dann
gegebenenfalls zum Beispiel aus dem Speicher etwas in Y übertragen.
Dann wird das mit dem ADD-Befehl durchgeführt, dann wird das Ergebnis
in Z abgespeichert und dann zum Schluss das Ergebnis aus Z wieder
zurück in den Akku übertragen.
Das ist so im groben Sinne so ein Mikro-Programm, das durchgeführt
wird, wenn zum Beispiel addiert wird.
Und wie sieht das jetzt mal am Beispiel von Befehlen aus, wenn wir uns
jetzt die Befehls-Holphase anschauen?
Wie gesagt, es geht um das Holen des Befehls aus dem Speicher plus es
gehört auch noch dazu, wo mache ich als nächsten Befehl weiter.
Und das hängt unter Umständen halt auch von dem Ergebnis der
Befehlsausführung ab, wenn es halt ein Sprung oder ein bestimmter
Sprung ist.
Also Befehls-Holphase, das Erste, was ich machen muss, ich muss mir
den Befehl aus dem Speicher holen.
Dafür schaue ich halt im Instruction-Address-Register nach, wo soll
denn der nächste Befehl herkommen.
Das gebe ich rüber ins Speicher-Address-Register.
Dann wird aus dem Speicher der Wert geholt.
Und jetzt sehen Sie hier, wenn man oben auf die Titelzeile guckt, auf
die Überschrift guckt, da sind zwei Takte, da passiert nichts.
Da ist der Takt A2, da wird der Speicher aus dem Speicher-Address
-Register der Adresswert an Speicher übergittelt.
Dann im Takt 3 ist das immer noch der Fall und erst im vierten Takt
kommt dann das Ergebnis zurück ins Speicher-Daten-Register.
Das ist etwas, um anzudeuten, dass das Holen von Daten aus dem
Speicher oder das Reinschreiben von Daten in den Speicher in der Regel
eine langsame Operation ist.
Langsamer ist, als wenn ich zum Beispiel direkt mit den Registern
arbeite.
Das ist etwas, wenn Sie sehr hardware-nah programmieren.
Etwas, wo Sie dann irgendwann mal lernen, darauf wirklich getrimmt zu
sein, möglichst Operationen auf dem Hauptspeicher zu vermeiden und,
wenn es irgendwie geht, im Register zu arbeiten.
Wenn Sie noch mit relativ hardware-nahen Sprachen arbeiten und das
kann auch schon sowas wie C sein.
C ist ja auch eine relativ hardware-nahe Sprache.
Dann gibt es da durchaus noch Mechanismen, mit denen Sie versuchen
können zu beeinflussen, ob Daten direkt aus dem Speicher geholt werden
oder ob die nach Möglichkeit irgendwo in Registern vorbehalten werden,
um halt dieses langsame Sachen aus dem Speicher holen und zur ALU
befördern irgendwie zu vermeiden, weil das unter Umständen die
Ausführung vom Programm sehr langsam machen kann.
Jetzt ist also der Wert, den ich aus der Adresse im
Speicheradressregister holen wollte, im Speicherdatenregister und wird
dann übertragen entsprechend an das Instruction Register.
Dann, nächster Punkt ist, wo ist denn der nächste Befehl?
Und das hängt jetzt natürlich ab, was jetzt im Instruction Register
drinsteht.
Wenn das so ein normaler Befehl ist, der halt nicht die
Programmsteuerung beeinflusst, dann muss ich einfach eins aufaddieren
auf dieses Instruction Address Register.
Das heißt, der Wert, der im Instruction Address Register steht, der
kommt halt in dieses Zwischenspeicher von dem X.
Dann brauchen wir eine Eins, die wir draufaddieren wollen.
Die tun wir halt in das Y rein.
Und jetzt sehen Sie auch schon, warum es halt ein Register gibt, das
konstant Eins ist, dass Sie auf so einen Wert im Instruction Address
Register eine Eins draufaddieren wollen.
Das passiert sehr, sehr, sehr, sehr, sehr häufig.
Deswegen lohnt es sich, das Zeug dann nicht aus dem Speicher zu holen
und dann irgendwo im Speicher eine Eins drinstehen zu haben, sondern
deswegen lohnt es sich, ein Register zu haben, das nichts anderes
macht, als dass da konstant Eins drinsteht.
Dann werden die beiden Werte addiert, kommen in dieses
Zwischenregister Z und dann fließt das Ergebnis wieder in das
Instruction Address Register.
Das hat dann auch wieder ein paar Takte gedauert und jetzt haben wir
schon mal die neue Adresse im Instruction Address Register drinstehen.
Anders ist das halt, wenn Sie so etwas wie einen bedingten Sprung
haben, dann holen Sie halt auch wieder erst mal...
wenn Sie also einen bedingten Sprung haben, dann müssen Sie, also wenn
Sie einen Jump machen, dann müssen Sie halt diesen Wert aus dem
Speicher Adress Register rausholen.
Das Ganze kann man halt parallelisieren auch, also wenn Sie hier sowas
haben, wie ich hole den nächsten Wert aus dem Instruction Address
Register raus, dann kann ich noch auf dem alten Wert schon mal eine
Eins drauf machen und rein speichern und auf die Art und Weise kann
man sich so ein bisschen Rechenzeit ersparen, wenn man das macht.
Also schon, es waren nicht sechs Bits, sondern es können auch die acht
Bits des Instructions... also die ersten acht Bits werden geholt und
dekodiert.
Dann wird das entsprechende Mikroprogramm rausgeholt, je nachdem, was
da drin steht.
Wie gesagt, das sieht halt so aus.
Unter Umständen muss man halt noch was aus dem Akku holen, wenn man
also sowas hat wie diesen Jump Not Equal, dann muss man halt auch
vergleichen, was steckt im Akku drin, um halt entscheiden zu können,
welches Mikroprogramm jetzt ausgeführt werden soll und dann wird das
entsprechend durchgeführt.
Jetzt am Beispiel von Load Value und Jump schauen wir uns jetzt
erstmal mal an, wie das konkret aussieht.
Diese Befehlsausführungsphase, also das aus dem Instruction Register
bei Load Value steht ja drin, ich muss den Wert irgendwo aus einer
Adresse holen, das heißt die niederwärtigen 20 Bit kodierende Adresse
im Speicher, die fließt also in das Speicheradressregister, dann wird
das rausgeholt, fließt wieder in das Speicherdatenregister, fließt in
den Akku und dann würde als nächstes halt wieder die nächste
Befehlsholphase starten.
Und für Jump sieht es halt so aus, dass ich halt einfach den Wert, den
ich im Instruction Register drin stehen habe, der die Adresse des
nächsten Befehls kodiert, das muss ich einfach ins Instruction Address
Register durch übertragen.
Das, was da vorher drin stand, überschreiben und damit habe ich schon
den unbedingten Sprung ausgeführt.
Damit kann man jetzt mit diesen paar wenigen Befehlen, die man hat,
kann man jetzt im Prinzip jedes beliebige Programm schreiben.
Das ist nicht so komfortabel wie in einer höheren Programmiersprache,
aber alles was so ein normaler Rechner kann, kann jetzt auch mithilfe
von solchen MIMA-Befehlen geschrieben werden.
Hier ist halt das Beispiel, das Aufsummieren einer Liste von Zahlen.
Da wird halt angenommen, dass wir irgendwo so ein Array haben, das
heißt es gibt irgendwo fünf Adressen mit Werten und die wollen wir
entsprechend aufaddieren.
Jetzt hat man natürlich das Problem, sowas wie ein Array gibt es
nicht.
Das heißt also diese komplexen Datenstrukturen müsste man halt
entsprechend auch in der MIMA kodieren und das geht auch.
Wir haben ja kennengelernt, wie man so bestimmte Arten von Speichern
per Funktion definieren kann und genauso kann man Datenstrukturen per
Funktion definieren und diese Funktionen, die man dann ausrechnen
muss, die kann man alle mit diesem MIMA-Befehlen ausrechnen.
Wir machen es uns an der Stelle jetzt einfach und sagen, wir wissen
halt wie die Adressen heißen, wo diese fünf Werte liegen, an der
Adresse Liste von 0 bis Liste von 4.
Was wir aber machen ist, wir kennen nicht alle Adressen, sondern was
wir kennen ist die Adresse von 0, also da wo Liste von 0 liegt, den
Wert kennen wir und wir gehen davon aus, dass dann die Werte halt an
den nächsten vier weiteren Speicheradressen entsprechend liegen.
Was wir jetzt also machen ist, wir wollen erst mal schauen, den Wert
an der Liste 0.
Dann laden wir uns jetzt erst mal eine konstante 0 und speichern den
Wert an der Adresse Summe.
Das heißt also, die Summe initialisieren wir auf 0 und dann besorgen
wir uns noch einen Zähler.
Den initialisieren wir auch mit 0.
Das heißt, wir haben immer noch 0 im Akku liegen.
Wir können also den Wert wieder in einer Speicherzelle, wir nennen sie
Count, ablegen und dann laden wir uns die Adresse, wo der erste Wert
liegt, also der Adresse an der Liste von 0 entspricht.
Den kennen wir halt irgendwoher, deswegen laden wir den als Konstante
und speichern dann diesen Wert in einer Variable ab, die nennen wir
Referenz.
Das heißt also, die Idee ist jetzt, in der Summe soll immer die
aktuelle Summe sein, so viele Elemente wie wir aufsummiert haben.
An dem Count steht halt immer drin, an welchem Listen-Element wir sind
und in Ref steht immer drin, an welcher Adresse liegt denn das Listen
-Element, das wir als nächstes draufsummieren wollen.
Also, die drei Variablen haben wir uns dadurch initialisiert.
Die Variable entspricht hier entsprechend einer Speicheradresse und
dann können wir mithilfe der bedingten Sprünge entsprechend dieses
Array durchgehen.
Wir gehen davon aus, dass wir wissen, wie lang diese Liste ist.
Das steht an der Speicheradresse Längen, da steht drin, wie viele
Werte da drin sind und dann fangen wir halt an.
Wir wissen, in Ref steht drin, wo der nächste Wert, den wir
aufsummieren wollen, drin liegt.
Können wir also mit Load Indirect Value und mit Ref übergeben den Wert
an der Stelle, auf den Ref sozusagen zeigt, in den Akku laden.
Dann können wir die Summe drauf addieren.
Dann speichern wir die Summe wieder ab.
Damit ist also die Summe dann entsprechend aufgebaut und jetzt müssen
wir den Zähler um 1 erhöhen, damit wir wissen, auf welches
Speicherelement wir wollen oder welches Speicherelement wir als
nächstes abarbeiten wollen.
Das heißt, wir erhöhen die Variable Counter um 1 und dann müssen wir
noch zum nächsten Speicherwert drüber liegen.
Wir wissen, dass die einzelnen Werte, die wir aufsummieren,
hintereinander im Speicher stehen.
Das heißt, was in Ref steht, müssen wir auch noch entsprechend um 1
erhöhen und wissen dann, dass wir dann auf das Element mit Index 1 in
der Liste haben.
Und jetzt müssen wir noch abprüfen, haben wir schon alle Elemente, die
wir aufsummieren wollen, auch wirklich aufsummiert.
Das heißt, wir schauen uns nochmal den Counter an.
Überprüfen ist der Counter gleich der Länge.
Wenn die gleich sind, steht da drin Minus 1.
Und dann wissen wir, sind wir fertig, können wir damit weitermachen,
was danach kommen soll.
Im Regelfall nichts.
Das heißt, das Einzige, was man hier immer beachten muss, das sind
immer beliebte Fehler, dass man die Indizes und die Anfang und den
Ende der Liste richtig hinbekommt.
Die Liste selber soll halt fünf Werte haben.
Das heißt, in Len steht halt die Zahl 5.
Wir fangen aber an, bei 0 zu addieren.
Und jetzt ist es wichtig, dass im Counter halt immer drin steht, nicht
wie viele Elemente haben wir bereits aufaddiert, sondern was ist der
Index des nächsten Elementes, das wir werden drauf addieren wollen.
Und wenn der 5 ist, dann wissen wir, da haben wir alles abgearbeitet,
dann können wir das entsprechend sein lassen.
Und ansonsten, wenn das nicht equal ist, dann wird halt diese
Addierschleife weiter durchlaufen.
Der Zähler erhöht sich immer, bis er dann irgendwann auf 5 ist.
Dann gibt dieser Vergleich entsprechend, also 5, der Vergleich ergibt
minus 1 und dann weiß ich, kann ich aufhören.
Also, das ist die einfache Art und Weise, wie diese MIMA funktioniert.
Und was Sie jetzt auf den Übungsblättern ein bisschen üben werden,
ist, dass Sie so einfache MIMA-Programme werden schreiben können, dass
Sie einfache MIMA-Programme werden lesen können und dass Sie auch so
die Grobstruktur der MIMA auch immer kennen und wissen, es gibt eine
Befehlsholtphase, es gibt eine Befehlsausführungsphase, wie wird denn
berechnet, wo der nächste Befehl, der nächste Befehl sein soll.
Und auch wenn es kein echter Rechner ist, sollten Sie immer im
Hinterkopf behalten, dass dieses bisschen, was Sie da haben, alles das
kann, was auch ein richtiger Rechner kann.
Es kann halt ein bisschen schwierig sein, da die Programme zu
schreiben, die könnten halt schon ein bisschen kompliziert aussehen,
aber das kann in der Regel die meisten Sachen machen, die ein normaler
Rechner auch so ausführen kann.
Gut, so viel dazu.
An dieser Stelle in der Vorlesung kommt jetzt so ein kleines
Einschubkapitel.
Das hat den Namen Dokumente.
Das dient nochmal dazu, um nochmal ein bisschen zu rekapitulieren, was
haben wir denn bei formalen Sprachen gehabt und was hat das vielleicht
mit echten Dokumenten zu tun?
Wie kann ich das, was ich bei formalen Sprachen mache, auch wirklich
anwenden?
Und insbesondere sehen wir jetzt anhand dieser Dokumente dann auch,
dass wir irgendwann an eine Stelle kommen, wo wir mit den Methoden,
die wir bisher hatten, um formale Sprachen zu definieren,
Mengenoperatoren, induktive Definitionen, an irgendeiner Stelle
plötzlich nicht mehr weiterkommen.
Dass wir also mit den Sachen, die wir haben, nicht beliebige formale
Sprachen definieren können.
Und dafür brauchen wir dann was anderes.
Und das wird dann entsprechend das nächste Kapitel sein, das Kapitel
über formale Grammatiken, wo wir dann ein weiteres Werkzeug
kennenlernen, um weitere Arten von formalen Sprachen definieren zu
können.
Als Beispiele für Dokumente schauen wir uns kurz ein bisschen XHTML an
und ein bisschen Latex.
Und was Sie dabei auch noch nebenbei so ein bisschen lernen, ist eine
dringende Empfehlung, wenn Sie wissenschaftliche Arbeiten schreiben.
Sie werden irgendwann in nicht allzu ferner Zukunft, in Ihrem Studium,
in die Lage kommen, dass Sie werden etwas Wissenschaftliches schreiben
müssen.
Es kann eine Ausarbeitung für das Pro-Seminar sein oder spätestens,
wenn Sie dann bei der Bachelorarbeit angelangt sind, werden Sie ein
größeres wissenschaftliches Dokument verfassen.
Jetzt ist natürlich die Frage, wie schreiben Sie das?
Da ist jetzt die große Frage, machen wir mal eine Umfrage.
Wenn Sie heute an Ihrer Stelle anfangen müssten, Ihre Bachelorarbeit
zu schreiben, wer würde dafür zum Beispiel Word verwenden?
Wer würde sowas wie Open Office verwenden?
Wer verwendet etwas anderes?
Was verwenden Sie?
Sie verwenden Latex.
Wer von Ihnen hat bisher schon Latex schon mal verwendet?
Das sind erfreulich viele, weil meistens, wenn man noch ins Studium
reinkommt, bis zum Studium hat man meistens keine Berührungspunkte mit
Latex.
Alle anderen, die jetzt noch ihre Ausarbeitung mit Word schreiben
würden, würde ich empfehlen, dass Sie sich mal Latex anschauen.
Insbesondere, wenn Sie halt im naturwissenschaftlichen, mathematischen
Informatikbereich sind, kommen Sie mit sowas wie Word nur bedingt
weiter und es gibt durchaus solche Sachen wie Latex, die da
Mechanismen bieten, die gerade das Erstellen von wissenschaftlichen
Arbeiten deutlich einfacher machen.
Wenn man halt mit dem Rechner umgeht, Sie haben halt die ganze Zeit
mit Dokumenten zu tun.
Sie schreiben irgendwelche Artikel, Briefe, was auch immer.
Sie haben überall, gut hier ist ein Beispiel, Kochrezepte,
Zeitungsartikel, Vorlesungsskripte, E-Mails, Tweets, WhatsApp
-Nachrichten, SMS, das sind alles Inschriften, die Folien sind alles
Inschriften, die irgendwie in der Regel heutzutage mit dem Rechner
erstellt werden.
Wenn man jetzt als Leser anschaut und ein Dokument liest, dann kann
man so jetzt ganz grob drei unterschiedliche Aspekte an einer
Inschrift und an einem Dokument hervorheben, die vielleicht von
Interesse wären.
Zum einen interessiert sich natürlich der Inhalt des Textes, aber beim
Erfassen des Inhalts des Textes ist halt auch die Struktur des Textes
von Bedeutung und sein Erscheinungsbild, seine äußere Form.
Und diese drei Dinge ist das, was man beachten muss, wenn man auch ein
Dokument erstellt, wenn man eine Inschrift beschreibt.
Beispielsweise, wenn man jetzt diese Bullet-Point-Liste, diese
Stichwort -Liste mit den drei Stichpunkten nimmt, dann kann ich der
eine andere Form geben, ohne dass sich was am Inhalt ändert.
Also, statt Inhalt klein und rot, schreibe ich es halt schwarz und
groß geschrieben, damit man weiß, was so da die Stichpunkte sind.
Aber die Struktur ist das Gleiche.
Ich habe immer noch eine Stichwort-Liste mit drei Bullets und ich habe
immer noch den gleichen Inhalt, der da übermittelt wird.
Ich kann auch die Struktur ändern.
Ich kann also aus dieser Bullet-Point-Liste, kann ich zum Beispiel
eine Komma-separierte Liste machen.
Ich habe immer noch den gleichen Inhalt.
Das Erscheinungsbild ist, wenn man mal von der Struktur absieht, weil
die Struktur wird ja auch durch Erscheinungsbild irgendwie deutlich
gemacht.
Im Großen und Ganzen wieder dasselbe wie oben, aber die Struktur hat
sich halt geändert.
Oder ich kann halt Struktur und Erscheinungsbild gleich lassen, aber
ich kann den Inhalt entsprechend ändern.
Dementsprechend ist es sinnvoll, wenn man Dokumente erstellt, dass man
vielleicht Struktur, Erscheinungsbild und Inhalt voneinander trennt.
Der Inhalt ist natürlich das, was am meisten interessiert.
Sie wollen in der Lage sein, den Inhalt aufzunehmen, außer wenn es
sich um Kunst handelt.
Bei Kunst ist dann häufig auch das äußere Erscheinungsbild das, was
Sie insbesondere interessiert.
Aber ansonsten haben halt Struktur und äußeres Erscheinungsbild und
Form die einzige Aufgabe, Sie dabei zu unterstützen, den Inhalt des
Dokumentes, den Sie lesen wollen, auch zu verstehen.
Dementsprechend, wenn wir Folien erstellen oder Skripte und so weiter,
machen wir uns auch Gedanken darüber, in welche Struktur bringe ich
die Inhalte der Vorlesung und dann, wie sieht die äußere Form aus, mit
der ich dann entsprechend eben die Inhalte der Vorlesung präsentieren
möchte.
Ich befinde mich in der glücklichen Lage, dass der Herr Worsch als
mein Vorgänger beim Halten der Vorlesung sehr viel Zeit investiert
hat, da vernünftige Struktur und Form zu geben, sodass ich das
glücklicherweise hauptsächlich einfach verwenden kann.
Also, wenn Sie mal später was schreiben und Sie wollen, und Ihnen
liegt was an dem Leser, Sie wollen, dass der Leser das auch versteht.
Tut der Poppes weh?
Ob der Poppes weh tut?
Was für ein Rücken tut weh?
Steckdosen gibt es leider nicht, sonst könnten wir noch ein Halskissen
machen.
Entschuldigung.
Also, wenn Ihnen was am Leser liegt, also wenn Sie wollen, dass der
Leser auch wirklich das Dokument versteht, machen Sie sich Gedanken
über die Struktur und versuchen Sie, eine vernünftige Struktur zu
finden und wenn Sie später mal eine Ausarbeitung schreiben, fangen Sie
frühzeitig an, sich über die Struktur auch der Ausarbeitung Gedanken
zu machen, weil häufig ist es so, dass wenn Sie sich mal über die
Struktur Gedanken machen, Sie auch mehr über den Inhalt Ihrer Arbeit,
Ihrer wissenschaftlichen Arbeit, die Sie durchführen wollen,
verstehen.
Wenn Sie mal eine vernünftige Struktur erstellt haben, wissen Sie zum
Beispiel häufig auch gleich, welche Experimente fehlen Ihnen noch,
welche Experimente sind überflüssig, welche Experimente sollte ich
überhaupt machen.
Also, eine gute Struktur zu finden, wenn man zum Beispiel eine
Ausarbeitung schreibt, ist ein sehr guter erster Schritt und dann halt
von unserer Seite aus immer benutzen Sie LaTeX, lassen Sie sich von
Ihren Kommilitonen, die schon LaTeX verwenden, überzeugen, dass das
gerade für Informatik bei wissenschaftlichen Ausarbeitungen sehr,
sehr, sehr hilfreich spielt.
Wenn wir jetzt Dokumente im Rechner verarbeiten, dann ist die Struktur
von großer Bedeutung für den Rechner, weil da hängt es davon ab, dass
die Struktur gewisser Syntax entspricht und eine korrekte Syntax hat,
weil der Rechner ist ja in irgendeiner Form dafür zuständig, dass
diese Struktur und ihr Inhalt auch korrekt dargestellt werden.
Also, das Wörtdokument, das Sie schreiben, muss dann auch hinterher
angezeigt werden und richtig ausgedruckt werden, so dass es richtig
aussieht.
Die Folien, die man erstellt, müssen halt entsprechend vom Rechner
aufs Projektersignal gegeben werden, so dass halt die Farben und das
Aussehen der Schrift und alles entsprechend richtig stimmt.
Und da, um das aus dem Dokument, das es anzeigen soll, das
entsprechend extrahieren zu können, braucht das Dokument eine
bestimmte Struktur mit einer korrekten Syntax, die das alles
beschreibt.
Und ein wichtiges Beispiel, wie das heutzutage häufig gemacht wird,
sind Auszeichnungssprachen.
Und auch so große Textverarbeitungsprogramme wie Word und Office
-Programme wie die Office Suite und Open Office etc.
verwenden inzwischen zum Abspeichern ihrer Dokumente in der Regel
Auszeichnungssprachen.
Als zwei Beispiele für Auszeichnungssprachen schauen wir uns ein
bisschen an, wie so Tabellen in XHTML dargestellt werden und wir
schauen uns ein bisschen an, wie Listen in LATIC dargestellt werden.
Also HTML, Hypertext Markup Language kennen Sie alle als
Auszeichnungssprache für Seiten aus dem World Wide Web.
Vielleicht an der Stelle, da Sie alle noch im ersten Semester sind, da
Sie Informatiker werden wollen, auch wenn Sie in der Allgemeinheit
immer normal sprechen, damit die Leute Sie nicht für komplett in der
Schuhe halten.
Seien Sie sich darüber bewusst, dass das, wenn Sie sich mit einer
Normalperson über so Dinge wie Internet und Computer und sowas
unterhalten, Sie da etwas verwenden, was nicht hundertprozentig
korrekt ist, sondern was man anders ausdrücken muss.
Wenn Sie also sagen, die Internetseiten sind in HTML geschrieben, dann
muss man sowas sagen, sowas wie Internetseiten gibt es nicht.
Sondern es gibt sowas wie ein Internet und ein Internet ist der
Verbund von ganz vielen Rechnern über die gesamte Welt verteilt und es
gibt auch nicht nur ein Internet, sondern es gibt viele Internets.
Das heißt, wenn man von einem Internet spricht, meint man, kann es
mehrere geben.
Also glaubt man nicht, aber es gibt sowas wie ein Internet 2 und es
gibt auch viele Unternehmen, die halten eigene Netzwerke vor, die
umspannen gegebenenfalls auch den Globus, aber von denen werden Sie
nie was hören und werden Sie nie sehen, wenn Sie jetzt nicht gerade in
der super geheimen Abteilung arbeiten, die sich um die Verteilung von
Datenströmen oder von Videos bei Produktionsanstalten und sowas
kümmern.
Also es gibt viele Internets.
Ein Internet ist einfach nur eine Kategorie von Netzwerk.
Dann gibt es das Internet, mit einem großen E geschrieben.
Das ist dieser Nachfolger vom Dapernet.
Das ist das, woran Sie angeschlossen werden, wenn Sie sich zu Hause
einen Internetanschluss holen.
Und das Internet bietet unterschiedliche Dienste an.
Es gibt unterschiedliche Dienste, die laufen alle über dem Internet.
Und einer dieser Dienste ist das sogenannte World Wide Web.
E-Mail wäre ein anderer Dienst.
Was gibt es denn noch, sowas wie
RTMP, Realtime Media, RTMSP, Realtime Media Streams.
Das wäre ein anderer Dienst.
Das sind alles unterschiedliche Dienste und einer dieser Dienste ist
das World Wide Web.
Und im World Wide Web werden Internetseiten übertragen, unter anderem
mit Hilfe von HTML oder HexHTML.
Also, www-Seiten als Dienst des Internets.
Früher HTML, inzwischen hauptsächlich verstärkt auf HexHTML.
Das ist sowas wie eine striktere Variante von HTML, weil auch wenn es
eine beste Syntax geben sollte, dadurch, dass das Internet so eine
Graswurzelbewegung ist, so chaotisch entstanden ist.
Es gibt keinen Diktator des Internets, der sagt, so sieht das
Protokoll aus, sondern man macht da so Request for Comments und dann
werden die halt diskutiert und dann läuft das Ganze im Prinzip, wenn
es einer umsetzt, dann wird daraus schleichend ein Standard.
Und HTML gab es halt auch als Request for Comment und dann wurde es
entwickelt, entwickelt und umgesetzt und dann gab es unterschiedliche
Browserhersteller und dann hat irgendwie Mozilla gesagt, wir machen
noch eine Erweiterung zum HTML und machen dann, was weiß ich, noch den
Tag und dann kann man das und Internet Explorer und Microsoft haben
gesagt, nö, wir wollen was anderes und dann gab es halt so so Dinge,
die waren nicht standardisiert und manches konnte der eine Browser,
manches konnte der andere Browser und dann ist die Sache, was ist,
wenn das Ganze syntaktisch nicht korrekt ist?
Da hat halt irgendeiner an der Webseite per Hand geschrieben und dann
fehlen halt irgendwie ein schließender Tag oder sowas.
Dann hat man das trotzdem interpretiert und halt geraten muss, zu sein
muss und dann hat das unterschiedlich ausgesehen.
Und dann hat man halt wieder ein bisschen versucht, da die Peitsche in
die Hand zu nehmen und das Ganze ein bisschen strikter zu machen,
damit dieser Wildwuchs aufhört und dann gab es halt XHTML als
striktere Variante, noch stärker formalisierte Variante für HTML.
Insgesamt XHTML als ein Sonderfall der Extended Markup Language und um
zu definieren, was ist syntaktisch korrektes XML und insbesondere
dann, was ist syntaktisch korrektes XHTML, gibt es halt sogenannte
Document Type Definitions, die dann festlegen, wie das syntaktisch
korrekt bitteschön auszusehen hat.
Und das ist jetzt ein kleiner Auszug aus dieser Document Type
Definition von XHTML, der festlegt, wie Tabellen bitteschön in XHTML
aufgebaut sein sollen.
Und dann sieht man, da gibt es halt sowas, auch irgendeine Syntax, in
der das Ganze geschrieben sein muss.
Das fängt irgendwie mal an mit spitzer Klammer und hört mit spitzer
Klammer auf.
Dann gibt es dieses Ausrufezeichen Element.
Damit kann man definieren, dass es jetzt ein Element geben soll, mit
folgendem Namen, zum Beispiel Table, und in diesem Element, das da
heißt Table, da können dann unterschiedliche Sachen drin sein.
Gibt es auch sowas wie eine Caption und ein T-Head, ein Table-Head,
Table -Footer, Table-Body, Table-Row.
Table-H steht, das ist der Column-Header.
Und dann gibt es noch sowas wie Table-Data.
Was soll das heißen?
Im Prinzip wird durch diese Document Type Definition nichts anderes
festgelegt als formale Sprachen.
Und die Document Type Definition selber verwendet wieder kleinere
formale Sprachen, um diese größere formale Sprache zusammenzubauen.
Table, Table-Head, Table-Row sind am Ende nichts anderes als Namen für
formale Sprachen.
Wenn da oben sowas wie ein Plus vorkommt, dann meint das den epsilon
-freien Konkatenationsabschluss.
Das Komma ist zum Beispiel das, was wir als Produkt formaler Sprachen
kennengelernt haben.
Also wenn da irgendwo zum Beispiel da oben steht Caption, T-Head, T
-Foot und so weiter, dann ist das so, Caption ist eine formale
Sprache, T-Head ist eine formale Sprache und Komma heißt, das Ganze
wird konkateniert.
Und dieses Fragezeichen dient dazu, um es optional zu machen.
Das heißt, dieses Fragezeichen sagt einfach, ich kann L hoch 0
vereinigen mit L hoch 1.
Das heißt, Caption-Fragezeichen kann aus der Sprache kommen, die
Caption ist, oder es kann das leere Wort sein.
Und deswegen ist es halt so wichtig, dass das leere Wort ist nicht
nichts, sondern kann Element sein einer formalen Sprache.
Wenn man sich jetzt sowas Einfaches anschaut, wie den TableBody, dann
heißt das im Prinzip nichts anderes als ein TableBody, der besteht
halt aus einem oder mehreren sogenannten TableRows.
Und in XHTML und in XML ist einfach festgelegt, wenn ich eine Sprache
anfangen lasse, dann kommt als erstes der Name dieser formalen Sprache
in Spitzenklammern.
Und wenn die formale Sprache aufhört, das Wort, das aus dieser
formalen Sprache kommen soll, dann hört das halt auf mit
Spitzenklammern, Schrägstrich Name des Elements Spitzenklammern zu.
Und dazwischen, dadurch, dass das ein Plus ist, also epsilonfreier
Konkatenationsabschnitt, gibt es halt mindestens eine Tabellenzeile,
in der Regel eher mehr.
Also ein Wort, das aus LTR plus kommt.
Und die erste Definition von Table sagt halt, es muss wieder mit Table
anfangen und dem schließenden Tag von Table aufhören.
Und dazwischen habe ich halt ein Wort, das aus der Konkatenation
dieser Sprache kommt.
Es kann also optional eine Überschrift haben.
Dann kann optional ein Tabellenkopf kommen.
Dann kann optional ein Tabellenfutter kommen.
Und dann kann optimal der Tabellenbody kommen.
Und zwar nicht nur ein Tabellenbody, sondern mindestens einer,
eventuell sogar mehrere.
Und da sieht man jetzt schon, dass Struktur und Erscheinungsbild sind
ja offensichtlich voneinander getrennt.
Weil wenn man jetzt hört, Tablehead oder Tablecaption.
Tablehead, klar, Header muss ja irgendwie normalerweise oben stehen.
Und Tablefoot, Tablefutter, der muss ja irgendwo unten stehen.
Warum kommt dann der Tablefutter nicht ans Ende, wenn der doch unter
der Tabelle stehen soll?
Diese Auszeichnung sagt überhaupt nichts darüber aus, wie das
hinterher dargestellt wird.
Wo die Überschrift der Tabelle hinkommt, wo die Fußzeile der Tabelle
hinkommt, wo die Caption der Tabelle hinkommt, wird dadurch nicht
festgelegt.
Das ist hinterher dann Aufgabe desjenigen, der dieses XHTML darstellt,
das so darzustellen, wie er das anhand der Struktur für richtig hält.
Wichtig ist, dass die Sachen jetzt einfach erstmal nur festgelegt
werden und danach, in welcher Reihenfolge die Sachen dargestellt
werden, das ist durch diese Spezifikation erstmal noch überhaupt nicht
vorgegeben.
Ich definiere nur Struktur, ich definiere kein Erscheinungsbild.
Das sieht dann zum Beispiel halt so aus, so kann eine Tabelle in XHTML
aussehen.
Fängt dann mit dem Table Tag an und dem schließenden Table Tag hört es
auf.
Dann kommt zum Beispiel ein Body, das heißt also so etwas wie ein
Futter, ein Header und eine Caption hat sie gar nicht.
Und jeder Body besteht halt aus einer Table Row und wenn man dann bei
Table Row nachschaut, dann kann das zum Beispiel aus solchen TD Table
Data Elementen bestehen.
Ähnlich funktioniert auch LATIC.
In LATIC wird auch erstmal in erster Linie Struktur und Inhalt des
Dokumentes definiert und dann irgendwo anders in zentraler Stelle wird
die Erscheinungsform dann definiert für bestimmte Elemente aus der
Struktur.
Besonders berühmt oder besonders beliebt ist LATIC insbesondere dann,
wenn man mathematische Formeln setzen muss.
Wenn man da schon mal ein Word gemacht hat, dann weiß man, dass das
ein Krampf ist und es sieht nicht notwendigerweise schön aus.
Also mathematische Formeln schön zu setzen ist nicht so einfach und
Sie haben in der Vorlesung schon festgestellt, mathematische Formeln
zu setzen ist für Informatik offensichtlich sehr wichtig.
Deswegen haben sich Informatiker schon sehr früh darüber Gedanken
gemacht, wie kann ich denn jetzt bitte schön mathematische Formeln
schön hinschreiben.
Also ganz ganz früher hat man halt Sachen noch getippt und wenn Sie
ganz alte Artikel lesen, da sind zum Teil die Formeln halt per Hand
noch reingeschrieben und dann irgendwie in die Vorlage per Hand
reingeklebt worden und dann kam das irgendwie in die Vervielfältigung.
Das ist natürlich dann nicht das, was einen Informatiker erfreut,
sondern das würde man gerne im Rechner schreiben und deswegen hat
Donald Knuth sich halt Latich-Tech und dann entsprechend Latich
ersonnen.
Und da gibt es dann halt auch so eine Auszeichnungssprache, da kann
man halt dann hinschreiben, eine mathematische Formel mithilfe so
einer Auszeichnungssprache, wo man halt die Struktur vorher gibt, dass
man halt eine 2 hat und von der 2 wird eine Summe abgezogen und die
Summe hat einen Index von bis und dann einen Inhalt, was in der Summe
drin steht und dann wird da zum Beispiel 2 hoch irgendwas gerechnet
und das Ganze ist dann hinterher gleich irgendwas anderem und dann
hört die Formel aus.
Und daraus wird dann entsprechend gemäß bestimmter Regeln das
eigentliche, tatsächliche Erscheinungsbild gemacht.
Und zum Beispiel sehen Sie hier so ein Erscheinungsbild, da sind die
Indizes, über die die Summe laufen soll, die stehen unter und über dem
Summenzeichen.
Ob die über oder unter dem Summenzeichen stehen soll, habe ich in der
Struktur nicht festgelegt.
Da habe ich nur festgelegt, es gibt halt einen Index von und einen
Index bis.
Und je nachdem, wie es halt intern nach den Regeln schön aussehen
wird, wenn ich zum Beispiel wenig Platz nach oben und unten habe, weil
das Ganze in einer Zeile soll, kann es auch passieren, dass diese
Indizes zum Beispiel rechts unten und rechts oben so seitlich neben
das Summenzeichen rutschen, damit man den Platz oben und unten spart,
wenn ich das zum Beispiel in einer Zeile mit Text abdrucken will.
Und darüber muss ich mir jetzt überhaupt keine Sorgen mehr machen, ob
jetzt der Index oben drüber stehen soll oder rechts oben und links
unten neben dem Summenzeichen.
Da kümmert sich das Textsatzprogramm drum.
Da brauche ich mich überhaupt nicht mehr drum zu kümmern.
So, Latex-Dokumente bestehen in der Regel aus Definitionen von
Strukturen.
Es gibt sowas wie Sektionen, das können sowas ähnliches wie Kapitel
oder Unterkapitel in einem Dokument sein.
Es gibt, man muss sich nicht mehr darum kümmern, welche
Abschnittsnummer oder so bekommt es.
Dieses Durchzählen der Abschnittsnummern wird automatisch gemacht.
Das ist auch dann schön, wenn Sie zum Beispiel andere Literatur
referenzieren.
Wenn man das mal per Hand gemacht hat, ist das ein ewig langes
Gefriebel, bis man so eine Literaturliste alles einheitlich aussieht
und nicht an jeder Stelle hinterher auf die richtigen Einträge in der
Literaturliste verweise.
Sowas kann Latex alles automatisch machen.
Da muss man sich nicht mehr drum kümmern.
Manchmal, nach bestimmten Druckvorlagen, muss zum Beispiel die
Überschrift in einem Paper immer in Großbuchstaben sein, aber wenn man
einen anderen Herausgeber hat, der hätte dann gerne, dass das nicht
immer in Großbuchstaben ist, sondern so, wie es hingeschrieben wurde.
Auch darüber muss man sich keine Sorgen mehr machen.
Das wird alles entsprechend an einer Stelle mal definiert, wie es
hinterher sein soll und man selber als Autor muss sich da entsprechend
gar nicht mehr drum kümmern.
Grundstruktur von so einem Latex-Programm ist, man muss angeben, was
für eine Art von Dokument es ist.
Ist es ein Buch, ist es ein Artikel, ist es so eine kürzere
Abhandlung, nennt man dann ein Report.
Dann gibt es so ein paar Hilfspakete, wenn man zum Beispiel möchte,
dass schöne Silbentrennung gemacht wird im Deutschen und so weiter,
kann man so ein paar Hilfspakete machen.
Man muss sich unglücklicherweise darum kümmern, in welchem Kodierung
das Dokument geschrieben ist.
Wenn man also irgendwie ein UTF-8-Dokument hat, dann muss man es halt
entsprechend auch mal angeben und dann fängt man an, Struktur und
Inhalt zu definieren, dass man halt sowas wie ein Auto hat, dann gibt
es einen Titel des Dokumentes, unter Umständen hat das Dokument ein
Erstellungsdatum und so weiter und so fort und dann sagt man
irgendwann, hier geht das eigentliche Dokument los.
Da soll bitte einmal der Titel gemacht werden und dann fangen wir an
mit dem ersten Kapitel, das kriegt eine Überschrift, da wird eine
kleine Formel rein und dann wird das alles so schön strukturiert,
Struktur und Inhalt hingeschrieben und dann ist irgendwann das
Dokument zu Ende.
Und eine Möglichkeit von Strukturen sind zum Beispiel solche
Aufzählungslisten.
Die nennen sich dann, das ist dann sogenannte Items und die Umgebung,
mit der man das definiert, nennt sich dann entsprechend Itemize.
Man sagt halt, okay, hier fängt eine Liste an, die Liste hat folgende
Einträge und welchen Eintragssatz mache ich immer, wenn ich den
beginnen lasse, mit dem Befehl Item, dann kommt halt, was in dem Item
drinsteht und dann irgendwann sage ich, okay, jetzt ist die Liste zu
Ende.
Und wenn daraus dann das Textsatzprogramm was macht, kann es zum
Beispiel daraus machen, sowas hier mit drei mit einem gewissen
Zeilenabstand übereinander aufgelistete Inhalte und das Ganze mit so
einem schwarzen kleinen Punkt davor.
Dass das ein schwarzer kleiner Punkt sein soll, das steht in der Liste
nicht drin, sondern das wird irgendwo irgendwann einmal zentral
festgelegt und alle Listen kriegen dann alle den kleinen schwarzen
Punkt und den gleichen Zeilenabstand und so weiter.
Wenn ich das mal ändern möchte und statt des kleinen schwarzen Punktes
ein rotes Quadrat haben möchte, muss ich das entsprechend nur an einer
Stelle mal im Dokument ändern und es wird automatisch halt auf alle
anderen Listen, die ich habe, angewandt.
Was wir jetzt halt gerne hätten ist, wenn wir uns mit Dokumenten und
der syntaktisch korrekten Definition oder der Definition von
Dokumenten als formale Sprache beschäftigen, was ist syntaktisch
korrekt, dann bräuchten wir jetzt also so eine Sprache für Itemize.
Also angenommen, wir haben mal eine Sprache für die Items, die nehmen
wir jetzt mal als gegeben an, da wollen wir uns nicht drum kümmern,
sondern wir wollen uns nur für das Itemize machen.
Dann könnte man zum Beispiel die formale Sprache Itemize so
definieren.
Okay, das fängt an mit dem Stichwort Beginn-Itemize, das hört auf mit
dem Stichwort End-Itemize und innen drin kann ein oder mehrere Items
sein.
Und dann komme ich irgendwo an ein Problem, nämlich es ist durchaus
erlaubt, dass so ein Item in einer Aufzählungsliste selber wieder eine
Aufzählungsliste ist.
Das heißt, diese Sprache L-Item müsste in der Lage sein, irgendwann
zwischendrin zu sagen, okay, da an der Stelle kannst du wieder einen L
-Itemize machen.
Das heißt, bei der Definition von L-Item, wenn ich das definiere, muss
ich irgendwann wieder Bezug nehmen auf die Sprache L-Itemize.
Und dann wird es unangenehm.
Das ist keine Induktion mehr, so wie wir es kennengelernt haben.
Beim induktiven Vorgehen hatte ich immer irgendwo einen
Induktionsanfang und dann wurde es halt größer.
Ich habe es über irgendwas laufen lassen und das ist hier nicht mehr
so einfach.
Das Ganze kann man jetzt halt als ein Gleichungssystem aufstellen.
Also L-Item ist irgendwas und drin kommt L-Itemize und L-Itemize ist
irgendwas und drin kommt L-Item.
Und wenn es sozusagen eine eindeutige Definition von L-Itemize geben
soll, dann muss ich dieses Gleichungssystem lösen können.
Es darf nur eine Lösung geben.
Die Frage ist jetzt also, ist das Gleichungssystem lösbar?
Ist es eindeutig lösbar?
Und da kommen wir jetzt eben an die Grenzen dessen, was wir bisher
gemacht haben.
Bisher haben wir halt mit Hilfe von Produktkonkretationsabschluss,
Schnitt und so weiter und so fort haben wir formale Sprachen
definiert, weil wir immer Größeres in Kleineres zerlegt haben.
Also irgendwas, was aus mehreren Bestandteilen besteht, haben wir
zusammengesetzt aus einfacheren Bestandteilen.
Nur jetzt haben wir halt das Problem, dass wir irgendwas Komplexes
haben und das Komplexe ist zusammengesetzt unter anderem aus komplexen
Dingern der gleichen Art.
Also Listen, die wieder Listen, unter anderem Listen enthalten können
als einen Listenpunkt.
Da beißt sich jetzt halt die Katze in den Schwanz.
Da haben wir jetzt eine echte Rekursion.
Ein typisches Beispiel, was so einer theoretischen Informatik immer
gerne betrachtet wird, wenn man sich mit solchen Problemen
beschäftigt, ist die Sprache der korrekt geklammerten Ausdrücke.
Und wenn mich jetzt mal nicht interessiert, was in den Klammern
drinsteht, sondern nur die Klammern selber und dass die Klammern immer
korrekt gesetzt sind, dass es also zu jeder aufgehenden Klammer auch
eine zu schließende Klammer gibt und dass Klammern auch ineinander
geschachtelt sein können, dann hätte ich halt sowas wie eine Sprache
aller korrekt geklammerten Ausdrücke.
Die fangen mit Klammer auf und Klammer zu an und innen drin steckt
wieder ein Wort aus der Sprache der korrekt geklammerten Ausdrücke.
Und da kommen wir jetzt eben an die Grenze, dass das mit dem, was wir
bisher gemacht haben, nicht mehr eindeutig machbar ist.
Ich kann zwar etwas definieren, was auch lösbar ist, aber es gibt
gegebenenfalls mehrere Sprachen und das wollen wir entsprechend nicht.
Also hier der kurze Einschub nur, Dokumente gibt innerhalb Struktur
Erscheinungsbild und wenn sie Dokumente schreiben, sollten sie sich
häufig darauf konzentrieren, was ist Struktur und Inhalt und das ganze
trennen von, wie wird es hinterher dargestellt, das sollte am besten
irgendwo zentral stehen und dass das ihnen dann hinterher ein Programm
schreibt.
Wenn sie unbedingt ein Wort schreiben wollen, geht das mit Wort auch.
Da muss man ein bisschen tiefer einsteigen.
Nur sie kommen dann irgendwann an Grenzen, wenn es um sowas wie
Literaturlisten geht oder auch mathematische Formen.
Aber auch Word hat inzwischen relativ ausgefeilte Dinge, mit der sie
zumindest das äußere Erscheinungsbild ihrer Struktur zentral
definieren können.
Gut, was machen wir jetzt also mit diesem Problem, dass wir an die
Grenze gelangt sind, wenn es darum geht, normale Sprachen zu
definieren.
Und was sie hier in der Vorlesung kennenlernen werden, ist das
Hilfsmittel der kontextfreien Grammatiken zur Definition formaler
Sprachen.
Also bisher hatten wir formale Sprachen nur mithilfe von einzelnen
Symbolen und halt diesen Mengenoperationen, Konkatenation und
Konkatenationsabschluss beschrieben.
Damit kann man manche Sprachen beschreiben, aber man kann insbesondere
auch beweisen, dass es Sprachen gibt, die man damit nicht beschreiben
kann.
Und hier haben sie mal noch ein weiteres Beispiel für die Definition
einer Struktur.
Ich bin ja auch froh, wenn es nicht mein Handy ist.
Für die formale Beschreibung einer Struktur und das ist jetzt aus der
Definition der Syntax von Java, aus der Java Language Specification.
Da gibt es halt sowas wie Blöcke und ein Block kann dann aus einem
oder mehreren Block-Statements bestehen und dann hat man ein Block
-Statement.
Das besteht entweder aus einem Block-Statement oder das besteht aus
Block -Statements, gefolgt von einem Block-Statement.
Und ein Block-Statement besteht dann halt aus einem Statement und
irgendwelchen anderen.
Und ein Statement kann entweder sein Statement mit anhängendem
Unterstatement oder ohne am Ende anhängendes Unterstatement und dann
besteht das wieder aus einem Block und so weiter und so fort.
Was man hier sieht ist, dass da offensichtlich ganz viel rekursiv
definiert wird.
Also so ein Block-Statement besteht aus Block-Statements und einem
Block -Statement selber aus Statements.
Aber dann ein Statement selber kann ein Statement without trailing
substatement sein und das kann wieder ein Block sein.
Das heißt, es ist nicht nur Rekursion auf einer Ebene, sondern es kann
sein, dass man erst mal ein bisschen weiter tiefer runtersteigen muss
in dieses Zerteil und dann landet man plötzlich wieder ganz oben, wo
man am Anfang eigentlich angekommen ist.
Das heißt, ich habe hier also sehr relativ komplizierte rekursive
Definitionen und die Frage ist, wie soll man solche Definitionen jetzt
interpretieren und ist das, was hinten dabei herauskommt, überhaupt
irgendwas Vernünftiges?
Und was wir jetzt machen ist, wir nehmen uns jetzt das Ding her und
damit wir erstmal allgemein nur das Problem sehen und die Art und
Weise sehen, wie da etwas definiert wurde, streichen wir ganz viele
Sachen weg.
Als erstes, geschweifte Klammern sind bei uns Mengen, das ist doof.
Nehmen wir statt geschweifter Klammer runde Klammern.
Dann, was da drin steht selber, ob da jetzt Blockstatement drinsteht
oder Block oder was auch immer, interessiert uns jetzt gerade an der
Stelle erstmal nicht.
Nennen wir es also einfach x.
Und dann haben wir das überstehen, x besteht aus etwas Klammer auf und
dann kommt wieder irgendein x Klammer zu.
Und da haben wir stehen ein x, das besteht entweder aus einem x oder
es besteht aus einem xx.
Und diese mehrschichtigen Rekursionen, die lösen wir jetzt halt
einfach dadurch auf, dass wir alles x nennen.
Und dann haben wir hier sowas wie ein Blockstatement, das kann aus x
bestehen oder irgendetwas anderem, nennen wir das irgendwas anderes,
jetzt einfach mal pauschal y.
Und dann haben wir das stehen, so ein Statement with training
substatement, das ist halt ein x, das besteht aus einem x.
Und da gibt es ein anderes x, das besteht wieder aus einem x.
Dadurch, dass wir jetzt also die ganzen Namen weggestrichen haben, aus
geschweiften Klammern machen wir mal einfach zahlbar eine runde
Klammer, haben wir jetzt aber im Prinzip schon gesehen, die Struktur
oder die Prinzipien, die dahinter stecken, wie wir etwas hier
definiert haben.
Und das sind im Prinzip vier Möglichkeiten, wie man etwas machen kann.
Ich kann erstmal sagen, ein x, aus einem x werde ein y.
Oder ich kann sagen, aus einem x wird ein xx.
Oder ich kann sagen, aus einem x wird eine Klammer auf, x Klammer zu.
Und was man implizit hernehmen kann, indem man sagen kann, ich darf
nur das machen, was ich vorher aufgeschrieben habe und sonst darf ich
nichts machen, um so einen Block zu konstruieren, heißt das implizit
und nichts anderes ist ein x.
Also nur ein x, das ich mit den Regeln, die ich dahin geschrieben
habe, bauen kann, ist ein x.
Und alles andere, das ich mit diesen Regeln nicht bauen kann, ist eben
kein x.
Und jetzt kann man halt versuchen, mit x so eine formale Sprache zu
assoziieren, mit diesen Regeln, diesen vier Regeln, die wir da
aufgestellt haben, in vier Klauseln.
Also x darf ein y sein, also muss in der formalen Sprache y sein.
Dann darf ein x ein xx werden.
Das heißt also, die formale Sprache, wenn sich selber konkateniert,
muss auch in der formalen Sprache dran sein.
Und dann darf ein x etwas sein, das zwischen so runden Klammern steht
und selber innen drin wieder ein x hat.
Das heißt, das ist also vereinigt mit der Konkatenation, runde Klammer
auf, der Sprache, runde Klammer zu.
Und jetzt ist die Frage, reicht das aus?
Ist das eine gültige Definition einer Sprache, die so x beschreibt,
die diesen vier Regeln, die diesen vier Klauseln entspricht?
Und diese Inklusion, die ist halt trügerisch.
Das funktioniert halt nicht mehr.
Die Tatsache, dass diese K1, 2, 3, die spiegeln wieder, dass das alles
Teilmengen von L ist.
Und diese Klausel K4, die spiegelt halt wieder diese umgekehrte
Teilmengeneigenschaft.
Und nur wenn beide erfüllt sind, dann ist L gleich wirklich dem, was
wir wollen.
Und das ist ja auch wiederum nichts anderes als eine Art Gleichung.
Und da ist die Frage, ist die Gleichung lösbar?
Wäre natürlich gut, weil dann haben wir die Sprache definiert und
können auch hinschreiben, was in der Sprache ist und ist sie
eindeutig?
Das ist halt das, was für das K4 wichtig ist.
Also wenn nichts anderes ein x sein darf, diese Sprache sein darf,
dann muss diese Lösung auch eindeutig sein.
Kann der mal sein Handy einfach abschalten, sonst schalte ich es ab.
Also die Gleichung ist lösbar.
Das kann man zeigen, dass die Gleichung lösbar ist.
Aber das Blöde ist, dass sie eben nicht eindeutig ist.
Damit haben wir unser Ziel halt entsprechend mit diesen Mitteln nicht
erreicht.
Sondern wir brauchen irgendwie eine Möglichkeit, die aus allen
möglichen Lösungen die Lösung heraus sucht, die wir haben wollen, die
wir eigentlich definieren wollen.
Jetzt zu zeigen, dass das Ganze lösbar ist, reicht es aus, wenn man
eine Lösung angibt.
Und eine Lösung kann man angeben, indem wir das Ganze wieder induktiv
definieren.
Eine Folge von induktiven Sprachen, die wir dann hinterher alle
einfach vereinigen.
Wir sagen halt, L0 sei halt das leere Wort, die Menge mit dem leeren
Wort y.
Und dann für jedes Li plus 1 sagen wir halt, das ist halt Li
konkateniert mit sich selber.
Und dann vereinigt mit Klammer auf Li Klammer zu.
Und ganz am Schluss bilden wir eben die Vereinigung über alle Li mit
dem i aus den L0 und behaupten, das erfüllt die Gleichung.
Das ist ein Vorgehen, das haben Sie schon so gesehen, weil nichts
anderes haben wir zum Beispiel verwendet, als wir die syntaktisch
korrekten Aussagen logischen Formen definiert haben.
Das haben wir auf genau die Art und Weise gemacht.
Die Frage ist, wie kann man jetzt also zeigen, dass L gleich dieser
Sprache ist.
Muss man halt wieder machen, dass man diese beiden Teilmengen Beweise
zeigt, dass man also zeigt, L ist Teilmenge von dieser Definition,
denn diese Definition ist Teilmenge von L.
Erstmal kümmern wir uns um das Y.
Das Y ist Element von jedem Li, denn Y ist Element von L0.
Und für alle i gilt halt, dass Li mit Li ist Teilmenge von Li plus 1,
gemäß der Definition.
Und dementsprechend ist, wenn Y also aus Li ist, dann ist auch Y Y aus
Li i und damit auch aus Li plus 1.
Das heißt also, das Y kann man induktiv zeigen, ist immer in allen
Li's enthalten.
Dann Li ist immer Teilmenge von Li plus 1, denn Y ist in Li enthalten.
Und dann ist insbesondere auch Li konkateniert mit der Sprache, die
nur Y enthält, in Li i enthalten und damit ist dann auch das Teilmenge
von Li plus 1, gemäß der rekursiven Definition.
Das heißt also, jedes Li ist auch Teilmenge von Li plus 1.
Wenn wir jetzt also zeigen wollen, dass L Teilmenge ist von Y
vereinigt mit LL, vereinigt mit Runde Klammer auf, L Runde Klammer zu,
dann können wir sagen, okay, Y ist Element L0, ist Teilmenge L und das
ist wieder gleich L konkateniert mit Y, das ist Teilmenge von LL, ist
Teilmenge von Y, vereinigt LL, vereinigt Runde Klammer auf, L Runde
Klammer zu, fertig.
Das heißt also, L ist offensichtlich Teilmenge von der definierten
Sprache, die wir uns da definiert haben, von diesem nächsten
Induktionsschritt.
Damit haben wir also Teilmenge dieser Definition ist.
Jetzt brauchen wir das Ganze umgekehrt.
Jetzt müssen wir halt zeigen, dass diese Definition Teilmenge von L
sei.
Jetzt sei also W ein Element aus dieser Definition, also aus Y
vereinigt LL, vereinigt Klammer auf L, Klammer zu.
Was gilt dann?
Wir wissen erstmal, für jedes I ist Y Element aus Li und wir wissen
für jedes I ist Li Teilmenge von Li plus 1.
Und wir wissen auch, dass L Teilmenge ist dieser Definition.
Wir müssen jetzt die
umgekehrte Teilinklusion zeigen und wir haben ein Wort, das aus dieser
Definition stammt.
Jetzt machen wir eine Fallunterscheidung.
Erstmal das Wort könnte Y sein.
Y ist Element von LL, Teilmenge von L.
Zweiter Fall, das Wort ist von dieser Form LL, ist also aus dem
Element LL.
Das heißt also, dass das Wort sich zusammensetzt aus zwei Worten W1,
W2, wobei W1 aus L ist und W2 aus L.
Das heißt, W1 muss irgendwo aus einem Li1 sein und das W2 muss
irgendwo aus einem Li2 sein.
Wir hatten das ja definiert als diese Vereinigung über alle I.
Dann können wir das Maximum nehmen aus I1 und I2 und wir wissen dann,
dass das sozusagen eine Obermenge ist für das andere.
Das heißt, dass W1 ist dann aus diesem Li und W2 ist aus dem Li, wenn
ich halt das Maximum für I nehme von I1 und I2.
Und damit ist dieses Wort, das sich aus W1 und W2 zusammensetzt, auch
logischerweise Element von Li, Li, mit sich selber konkordiniert, das
wiederum Teilmenge ist von Li plus 1, was wiederum Teilmenge ist von L
gemäß Definition.
Oder der dritte Fall, das W ist von dieser Form, das ist runde Klammer
auf, ist ein Wort aus L, runde Klammer zu.
Dann ist das W-Element aus runde Klammer auf Li, runde Klammer zu, für
irgendein I und das ist wiederum Teilmenge von Li plus 1, was wiederum
Teilmenge der gesuchten Sprache L ist.
Das heißt, alle drei Fälle sind abgedeckt.
Aber die Lösung ist halt nicht eindeutig, weil auch diese Sprache, die
besteht aus runde Klammer auf, runde Klammer zu und darüber beliebige
Wörter gebildet, das ist leider auch eine Lösung.
Diese einen Teilenmengen Inklusionen zeigt man halt wie oben, das ist
relativ einfach.
Die andere ist sozusagen trivial, da das ja eben der Y
-Konkordinationsabschluss ist, der echte Konkordinationsabschnitt und
das sind eben alle Wörter.
Diese Menge aller Ausdrücke, die ich über solchen Klammern bauen kann,
ist eben eine andere Lösung.
Sowas wie dreimal Klammer auf ist in dem Wort, aber nicht in der
Definition, wie man das gemacht hat, weil die Definition, die wir
gemacht haben, die ist eben so aufgebaut, dass man eigentlich gerne
hätte, dass die Anzahl der öffnenden und die Anzahl der schließenden
Klammern übereinstimmen und das Ganze auch schön von innen nach außen
gestachtelt ist.
Das heißt, wenn ich also so oben diese Definition habe, dann ist zwar
das, was ich vorher induktiv definiert habe, eine gültige Lösung
dafür.
Eine Sprache, die diese Definition erfüllt, aber es gibt leider auch
andere, weitere Sprachen und die sind nicht das, was ich haben möchte.
Das heißt also, dieses Problem, alles, was dem gehorchen soll, den
Klauseln K1 bis K3 ist drin, aber auch nur das und nichts anderes, das
K4.
Das können wir also mit der Art der Definition oben mit dieser
Vereinigung nicht erfüllen.
Was kann man halt sehen?
L0 enthält dann nur das leere Wort und wenn ich L1 nehme und davon L0
abziehe, dann bleibt halt nur Klammer auf, Klammer zu übrig.
Und wenn ich L2 nehme und da alles, was in L1 drin ist, rausnehme,
dann sehe ich halt, dass da diese geklammerten, wohlgeformten,
geklammerten Ausdrücke alle dabei drin stehen bleiben.
Das ist bei der induktiven Definition.
Also bei der induktiven Definition stelle ich als sicher, dass da
immer die wohlgeformten Klammerausdrücke drin sind, maximaler Länge.
Also in L1 sind es die wohlgeformten Ausdrücke mit maximal einem Paar
passender Klammern, bei L2 sind es halt die wohlgeformten
Klammerausdrücke mit maximal zwei jeweils passenden, zueinander
passenden Klammern, in L3 mit maximal drei passenden Klammern und halt
alle noch mit weniger passenden Klammern.
Und sowas wie da dieses Beispiel, wo ich hinten zweimal Klammer auf,
Klammer zu habe und am Anfang habe ich Klammer auf, dann da drin, dann
Klammer auf, Klammer zu und dann diese Klammer zu, das ist gerade
deshalb in L3, weil halt dieser erste Teil in L2 ist und diese beiden
anderen Teile, der zweite Teil mit den beiden Klammern, der ist halt
in L2 und dann gibt es halt die Regel, die sagt, ich kann diese beiden
Dinger miteinander konkatenieren.
Und dann kann man halt die ganzen Regeln der Reihe nach durchgehen.
Dieses zweimal geschachtelte Klammer ist halt in L2, weil die einmal
geschachtelte Klammer in L1 ist und dann gab es halt die Regel 3, die
mir erlaubt, den geklammerten Ausdruck wieder in den geklammerten
Ausdruck reinzubauen.
Und dieser einmal Klammer auf, Klammer zu, der ist halt in L1, weil
halt Y in L0 ist und dann gab es diese Regel 3, die wieder gesagt hat,
alles was ich aus L0 nehmen kann, kann ich in so Klammern setzen und
dann ist es in L2 und so weiter und so fort.
So kann man für jede dieser Teilbereiche halt das Ganze zurückführen.
Das ist in dieser Sprache drin, weil ich eine dieser drei Regeln, die
ich hatte, anwenden konnte und implizit immer gesagt habe, alles
andere soll in der Sprache entsprechend nicht drin sein.
Das kann man zum Beispiel grafisch darstellen.
Ich kann mir also so ein Wort aus L3 hernehmen und dann kann ich die
Teile zerlegen und zurückführen darauf, welche Teile waren da aus L2
und wie sind sie zusammengefügt worden.
Welche Teile waren aus L1 und wie sind sie zusammengefügt worden.
Welche Teile waren aus L0 und wie sind sie entsprechend zusammengefügt
worden.
Und von welchem Wort, das ursprünglich in L0 war, bin ich überhaupt
losgegangen und in L0 war halt nur ein Wort, nämlich das leere Wort
enthalten.
Kann man dann halt ein bisschen vereinfacht entsprechend darstellen,
indem ich mir halt diese Sachen, ob das jetzt in der Sprache auf der
Ebene drin war oder nicht, halt spare und einfach sage, ja passt.
Und hier haben wir einen Baum.
Etwas, was sich einen Baum nennt, so wie man Ableitungsbaum hatte bei
syntaktisch korrekten aussagenlogischen Formeln, haben wir auch wieder
einen Baum.
Der besteht immer aus einer Wurzel, besteht aus Blättern und dann
innere Knoten.
Bisher haben wir sozusagen mal von unten nach oben interpretiert als
Begründung dafür, warum ein Wort Syntaktische korrekt ist.
Und wenn ich jetzt die gesamte Sprache erzeugen will, kann ich das
sozusagen von oben nach unten interpretieren, anwenden, um halt ein
Schema zu haben, mit dem ich etwas Syntaktisch Korrektes definieren
kann.
Und dieses Vorgehen von, ich fange halt mit was Kleinem an und dann
habe ich Regeln, die ich der Reihe nach anwenden kann, um daraus was
Komplizierteres zu machen, das ist eben gerade die Erzeugung mit Hilfe
von Grammatiken, die das macht.
Und von diesen Grammatiken, die sowas machen können, gibt es
unterschiedliche Arten von Grammatiken, die unterschiedlich mächtig
sind und wir beschäftigen uns halt mit kontextfreien Grammatiken.
Und anhand dieser vier Klauseln, die wir da hatten, kann man schon
sehen, was es heißt, was eine kontextfreie Grammatik ist.
Eine kontextfreie Grammatik sagt immer, wenn ein x da ist, dann darf
ich aus dem x auch den xx machen oder einen y machen oder Klammer auf,
x Klammer zu.
Und es ist völlig egal, wo ich dieses x hernehme.
Es hängt nicht davon ab, in welchem Kontext jetzt das x steht.
Da steht also nicht drin, wenn ich ein x habe, das fängt mit einem a
an und hört mit einem b auf, dann darf ich daraus etwas machen.
Sondern es ist völlig illegal.
Wenn ich halt ein x habe, dann darf ich daraus irgendwas Neues machen,
sowas wie ein xx oder Klammer auf, x Klammer zu oder kann ich ein y
machen.
Und das ist eben gerade das, worauf sich dieser Ausdruck kontextfrei
bezieht, dass ich diese Regeln anwenden darf, unabhängig davon, in
welchem Kontext ich diese Teilbestandteile habe, die ich da
zusammenbauen möchte.
Das heißt, an dieser Stelle nehmen Sie jetzt halt mit
Klammerstrukturen und Klammerstrukturen als ein Beispiel dafür, von
etwas, was ich nicht mehr so ganz trivial nur mithilfe von Beeinigung
und Durchschnitt definieren kann, sondern etwas, das ich schon mal
zumindest induktiv definieren muss.
Manchmal kann man halt sich, wenn man sowas definieren muss, dadurch
hinkommen, wie die Definition aussieht, indem man sich irgendwie so
einen Fixpunkt raussucht, den man sich halt annähern kann.
Das heißt, ich kann mir zumindest sowas wie eine Obermenge davon
ansehen.
Und wie gesagt, Sie haben jetzt so ein paar kleine Beweise gesehen.
Die Schritte, die einzelnen Schritte der Beweise sind an sich immer
trivial, relativ einfach.
Man muss sie halt nur mal in Ruhe der Reihe nach durchlesen, um zu
sehen, wie sich diese kleinen, einfachen, offensichtlich trivialen
Schritte dann zusammenfügen in der Struktur, um das große Ganze
richtig beweisen zu können.
Genau.
Das lohnt sich jetzt nicht, an der Stelle da weiterzumachen.
Wir machen dann nächstes Mal weiter mit den kontextfreien Grammatiken
und formalisieren also das, diese Art und Weise, wie wir Klauseln
hinschreiben können, die wir kennengelernt haben, formalisieren wir
nächstes Mal dann Hilfe mit kontextfreier Grammatik.
Dann sehen wir uns am Freitag wieder.