Schönen guten Tag, meine Damen und Herren.
Herzlich willkommen in der nächsten Vorlesung zu Grundbegriffen in der
Informatik.
Suchen Sie sich einen schönen Platz.
Es gibt inzwischen immer noch eine ganze Reihe.
Deswegen insbesondere eine Mitteilung für die, die die Vorlesung
gerade noch drüben im Informatikgebäude im Hörsaal verfolgen.
Heute ist der letzte Tag, wo wir das noch in einen zweiten Hörsaal
übertragen.
Hier ist reichlich Platz.
Es muss keiner mehr auf den Stufen sitzen.
Ab nächsten Mittwoch nur noch hier.
Keine Live-Übertragung woanders hin mehr.
Wir haben angefangen mit diesem Kapitel, das überschrieben ist.
Erstmal grob Kodierungen.
Kodierungen an und für sich kommen erst im letzten Abschnitt.
Vorläufig sind wir noch dabei, uns Zahldarstellungen und so etwas
anzugucken.
Und einer der letzten Punkte in der Vorlesung am Mittwoch war diese
Darstellung, von der Herr Leibniz gemerkt hat, oh, das geht ja auch
von nicht negativen ganzen Zahlen, nur mithilfe von zwei Ziffern
sozusagen, dieser 0 und der 1.
Ganz normales Stellenwertsystem, wie Sie es von der üblichen Zehner
-Darstellung auch kennen.
Mit einem Unterschied eben, es gibt nur die Ziffern 0 und 1.
Und die Wertigkeiten der Ziffern sind eben nicht die Potenzen von 10,
sondern die Potenzen von 2.
1, 2, 4, 8 und deswegen 1, 1, 0, 1.
So als Zeichenkette, wenn Sie das auf diese Art und Weise
interpretieren, ist dann eben die Zahl 13.
Das sind leider auch für kleine Zahlen manchmal schon relativ lange
Zeichenfolgen, deswegen manchmal macht man es sich ein bisschen
bequemer und nimmt dann sogar nicht nur 10, sondern 16 Ziffern.
Das ist auch eine Potenz von 2.
Warum das nützlich ist, ist Ihnen vielleicht schon klar.
Wenn nicht, merken Sie es noch.
Und dann, weil es sozusagen für jede Ziffer mehr Möglichkeiten gibt,
die Zahldarstellungen sind kürzer.
Wenn man das Alphabet größer macht, werden die Zahldarstellungen
kleiner.
Und hier sind eben die Wertigkeiten der Ziffern eben 2, 0 und A bis F
sind dann 10 bis 15 und die Wertigkeiten sind die Potenzen von 16.
Umgekehrt hatten wir uns überlegt,
tatsächlich zu jeder Zahl können Sie auch zum Beispiel so eine
Darstellung nur aus Nullen und Einsen im Zweiersystem ausrechnen.
Was man braucht, sind diese beiden Operationen Diff und Mod.
Diff einfach die ganzzahlige Division und wenn ein Rest übrig bleibt,
wirft man den halt weg.
Das ist das Ergebnis von Diff und der Rest selber, das ist diese
Operation Modulo.
Und an vielen Stellen, das liegt dann daran, wie CPUs zum Beispiel
implementiert sind, rechnet man halt dann immer, wie man sagt, Modulo
irgendeiner Zweierpotenze.
Und wenn Sie Zahldarstellungen haben wollen zur Basis 2, dann können
Sie die so ausrechnen.
Wenn die Zahl hinreichend klein ist, also nur 0 oder 1, dann nehmen
Sie einfach den Rest, also einfach die Zahl selber.
Und wenn die Zahl größer ist, dann die letzte Ziffer kriegen Sie auch
über die Modulo-Operation.
Und für die Ziffern davor, dann nehmen Sie einfach das, was übrig
bleibt, wenn Sie die Zahl erst mal ganzzahlig durch das K, also 2 oder
16 oder so, dividieren.
Also Sie nehmen nDiffK, das ist eine kleinere Zahl, und repräsentieren
die analog und kleben das davor.
Und dann hat man uns überlegt, dass das vernünftig ist.
Und wenn man das so macht, ist es tatsächlich so, wenn Sie von der
Zahl ausgehen, repräsentieren die, also im Zweifelsfall stellen Sie
sich immer jetzt mal vor zur Basis 2, aber alles, was ich sage, gilt
für beliebige Basis.
Und gucken dann, was bedeutet das denn, wenn ich das auf die
naheliegende Art und Weise, die wir kennengelernt haben,
interpretiere.
Dann kommt wieder die Originalzahl raus.
Ja, gut.
Weil num von Repräsentation von n gleich n ist, weil hier das num
links von Repräsentation steht, heißt num auch linksinvers zur
Repräsentation, wenn hier das gleiche wieder rauskommt.
Aber dazu kommen wir dann gleich noch ein kleines bisschen genauer.
Und das kann man auch einfach nachrechnen.
Standardinduktion, schauen Sie sich das an.
Es ist immer wieder das gleiche Schema, aber gewöhnen Sie sich an das
Schema, immer wieder, immer wieder.
So, und dann haben wir noch so eine etwas kuriose Zahldarstellung
kennengelernt, wo man sieht, also es gibt durchaus Möglichkeiten, auch
mit negativen Zahlen jetzt erstmal, wenn man sich so anguckt, ganz
nett umzugehen.
Allerdings ist das nicht die Methode, wie man es im Rechner macht.
Wie man es da macht, das sehen wir gleich.
Und jetzt nähern wir uns eben tatsächlich Zahldarstellungen im
Rechner.
Also stellen Sie sich vor, wir betrachten die Zahlen von 0 bis 15.
Für diese Zahlenmenge haben wir Z16 geschrieben.
Das sind also genau die Zahlen, die als Rest auch rauskommen können,
wenn man Modulo 16 rechnet.
Ja, die Division ist 16.
Und dann kann man die hier zum Beispiel so im Kreis anordnen,
meinetwegen.
Und dann rechnen geht so, dass man... und wenn wir hier die Zahlen
aufsteigend im Uhrzeigersinn hinmalen, von 0 bis 15, dann können Sie
jede von den Zahlen, die in Z16 sind, durch so einen Pfeil, der im
Uhrzeigersinn weitergeht, repräsentieren.
Und je nachdem, wie viele Segmente der Pfeil lang ist, ist das halt
die entsprechende Zahl.
Also 6 ist halt so dieser rote Pfeil, der 6 Segmente lang ist.
3 ist der Pfeil, der 3 lang ist.
Und Addition bedeutet dann einfach, also Modulo 16, auf diesem Kreis
hier, man setzt die Pfeile hintereinander, die Spitze vom Anfang des
zweiten Summanden ans Ende vom ersten Summanden und dann landet man
halt hier zum Beispiel bei 9.
Und das ist aber die Regel immer so, wenn Sie 14 plus 3 rechnen, dann
nehmen Sie also so einen Pfeil, also Pfeil 0 fangen Sie an, nehmen Sie
einen Pfeil, der 14 Segmente lang ist, setzen einen Pfeil hinten dran,
der 3 Segmente lang ist, dann landen Sie hier in dem Bild bei der 1.
Und das stimmt auch, 14 plus 3 ist 17, Modulo 16, wenn Sie die
Division durch 16 machen, der Rest, der übrig bleibt, ist 1.
Also wenn Sie dieses Rechnen Modulo 16 sich vorstellen wollen, können
Sie sich vorstellen, hier so im Kreis.
Und Addition heißt einfach, Pfeile hintereinander setzen und die
Pfeile gehen alle im Uhrzeigersinn.
Subtraktion geht so ähnlich, nur setzen Sie die Pfeile da nicht
hintereinander, Anfang ans Ende, sondern Sie nehmen die Zahl, von der
etwas subtrahiert werden soll, so ganz normal sozusagen, also hier das
rote, die 4.
Und dann, wenn der Pfeil für die Zahl, die Sie abziehen wollen, da
setzen Sie hier an der roten Spitze nicht mit dem blauen Ende an,
sondern mit der blauen Spitze, also Sie machen die Spitzen
nebeneinander und gucken dann, wo ist das Ende von dem zweiten.
Und dann steht also hier, 4 minus 7 ist 4 vor, dahinter sind Sie bei
13.
Und das stimmt auch, 4 minus 7 ist natürlich minus 3.
Und jetzt muss ich ein bisschen ungenau Hände wedeln und Division
durch 16 gibt dann einen Rest von 13.
Sie können ja vorher vielfache von 16 drauf addieren, schadet ja
nichts.
Also so geht Subtraktion.
Wenn wir in so einem ZK, also meinetwegen hier Z16 rechnen.
Und tatsächlich in Rechnern, also wenn Sie da so ein Prozessor haben,
das was tatsächlich typischerweise fest eingebaut ist, ist die
Addition von Zahlen.
Das funktioniert nur für Zahlen einer beschränkten Größe.
Die ist fest und in dem Mini-Prozessor, den wir dann im übernächsten
Kapitel sehen werden, da sind das Zahlen, die muss man mit Hilfe von
24 Bits, also Nullen und Einsen, repräsentieren können.
Im Allgemeinen hat man halt irgendeine Länge und die naive Methode, um
jetzt irgendwie Zahlen, ja das sind nochmal diese abstrakten Dinge in
Ihrem Kopf, in so einem Rechner zu repräsentieren, ist zu sagen, naja
gut, nehmen wir halt die Zahlen, können wir endlich viele
repräsentieren.
Nehmen wir die von 0 bis 2 hoch irgendwas minus 1.
2 hoch L minus 1.
Und jede dieser Zahlen können wir repräsentieren als ein Wort der
Länge L.
Und jetzt alle Zahlen werden repräsentiert durch Wörter der gleichen
Länge.
Und wenn die normale Repräsentation, wie wir sie definiert haben, zu
kurz ist, dann macht man halt davor noch ein paar führende Nullen,
macht das künstlich länger, sodass insgesamt die Länge immer L ist.
Also, wenn sie alle Zahlen mit 24 representieren, dann die Null halt
die Repräsentation 0, 0, 0, 0, 0, 0, 0, 0, 0, laut und null, naja 24
Stück.
Also, die Darstellung aller Zahlen gleich lang.
Alle haben Länge L.
über dem Alphabet 01, ja.
Und für jede Zahl, wenn Sie die aus dem hinreichenden kleinen Bereich,
wenn Sie die repräsentieren und dann wieder gucken, was bedeutet die
Repräsentation, sind Sie tatsächlich wieder bei der Originalzahl.
Allerdings, also mal abgesehen davon, dass man hier noch keine Brüche
oder Wurzeln oder irgendwas hat, ja, Wurzel Pi oder irgendwas
Schreckliches, was Sie übrigens auch nie präzise reinkriegen werden in
Ihre CPU.
Also zumindest negative Zahlen wäre aber schon schön, ja, und die will
man jetzt dann doch irgendwie haben.
Und die übliche Methode, das zu machen, ist so, und das ist jetzt
wirklich so, wie es CPUs auch tun, jedenfalls heutzutage die meisten
CPUs, es mag Ausnahmen geben, also wir hatten ja bisher so hier zum
Beispiel die Zahlen von 0 bis 15 irgendwie so, kann man sich
vorstellen, so im Kreis angeordnet.
Das war dann auch praktisch für das Rechnen, kann man so Teile nehmen,
aneinandersetzen und das will man sozusagen alles übernehmen, deswegen
bleibt, lassen wir den Kreis mal als Kreis hingemalt, aber wir
schreiben jetzt nicht mehr die Zahlen von 0 bis 15 hin, sondern ein
paar, also die 0 will man sowieso haben, und ein paar positive und ein
paar negative Zahlen, zum Beispiel so.
Das ist jetzt so, wie man das dann typischerweise macht, also man
behält die 0 und dann sozusagen von 0 so weit, dass also die eine
Hälfte des Kreises nicht negative Zahlen sind, also hier 0 bis 7 und
die andere Hälfte des Kreises sind negative Zahlen, das sind dann also
hier 8 negative Zahlen, minus 1 bis minus 8 und die malt man hier an
den Kreis von 0 ausgehend im umgekehrten Uhrzeigersinn.
Sowas kann man sich auch hinmalen und also diese Menge von Zahlen von
minus 8 über 0 bis plus 7, werden wir gleich sehen, die nennen wir K4
und so eine Menge von Zahlen, das ist das, was man wirklich tut im
Rechner und man kann sich auch vorstellen, dass das, also wenn Sie
sich im Zweifelsfall den Kreis vorstellen, liegen sie richtig für die
Operationen und man definiert jetzt sozusagen die Arithmetik so, wie
wir es gerade bei Z16 gesehen haben.
Man stellt sich vor, man hat Pfeile und setzt sie hintereinander.
Also wenn Sie jetzt in diesem Zahlbereich hier von minus 8 bis 7, 6
plus 3 rechnen, dann nehmen Sie den Pfeil für die 6, also von der 0
ausgehend im Uhrzeigersinn sechs Segmente und hinten dran ein weiterer
Pfeil im Uhrzeigersinn drei Segmente und dann landen Sie hier bei
minus 7.
Und dann in diesem Zahlenbereich, der hier K4 heißt, ist dann eben
tatsächlich 6 plus 3 minus 7.
So ist es halt.
Und weil wir jetzt negative Zahlen explizit haben, also mit denen kann
man auch rechnen, also wenn Sie jetzt sowas nehmen wie minus 2 plus 3.
Minus 2 ist jetzt eben der Pfeil von der 0 zur minus 2.
Das ist jetzt ein Pfeil links herum entgegen dem Uhrzeigersinn.
Das sind die Pfeile für die negativen Zahlen.
Und wenn Sie jetzt minus 2 plus 3 rechnen wollen, also plus heißt
immer Anfang ans Ende vom vorhergehenden Pfeil.
Minus 2 sind wir hier und von da jetzt der blaue Pfeil drei Segmente
nach rechts, kommt 1 raus.
Passt ja, das ist so wie man es kennt.
Also solange nicht so komische Dinge passieren, dass man da hier so,
man sagt, einen Überlauf hat, 6 plus 3 ist minus 7.
Solange man hinreichend kleine Werte hat und mit denen operiert,
passiert das, was man kennt, das Richtige sozusagen, wie in den ganzen
Zahlen.
Und Sie können das auch umgekehrt machen.
Ja, die Summanden vertauschen, 3 und minus 2, dann gehen Sie eben von
0, 3 nach rechts und dann minus 2 ist ja der Pfeil links rum, zwei
Segmente, dann sind Sie auch bei 1.
Funktioniert auch.
Alles ist gut.
Also was plus und minus betrifft.
Kleine Anmerkung am Rande, man könnte natürlich auf die Idee kommen,
sich auch noch Multiplikationen anzugucken.
Kann man auch machen, aber passen Sie auf, da passieren dann kuriose
Dinge in diesen Zahlbereichen, auch schon bei Z16.
Nehmen Sie 4 mal 4, da wissen Sie, was das ist, das ist 16, aber 16
modulo 16 ist 0.
Oder anders gesagt, wenn Sie hier von der 0 4 mal um 4 Segmente
weitergehen, dann sind Sie bei 0.
In diesem Zahlbereich haben Sie zwei Werte, sie sind beide ungleich 0,
4 und 4 zum Beispiel.
Und wenn Sie multiplizieren, kommt 0 raus.
Das ist sehr gewöhnungsbedürftig.
Das ist auch nicht so ganz schön, aber so ist es eben nur so am Rande.
Gut.
Ja, und jetzt habe ich also gesagt, ja, wir nehmen jetzt so einen
Zahlenbereich von minus irgendwo über die 0 bis plus irgendwo.
Und für diesen Zahlenbereich möchte man jetzt also auch irgendwie
festlegen, welche Zahl wird wie repräsentiert.
Und das ist ganz einfach.
Man nimmt diese harmlose Repräsentation der Zahlen, also zum Beispiel
von 0 bis 15.
0 ist 0 0 0 0.
Also jetzt hier zum Beispiel für Bitstrings der Länge 4.
0 0 0 1 ist 1, 1 0 ist 2, 1 1 ist 3 und so weiter.
Und wenn wir jetzt zu den anderen Zahlenbereich übergehen, dann was
wir tatsächlich machen, wir ändern nur hier drin bei den Zahlen, dann
nehmen wir jetzt nicht mehr 8 bis 15, sondern minus 1 bis minus 8.
Und außenrum, die Bitstrings, die Repräsentationen, das lassen wir
einfach so stehen.
Also die Festlegung soll sein, zum Beispiel minus 1 wird repräsentiert
durch 1 1 1 1.
Das ist jetzt einfach so.
Und minus 2 durch 1 1 1 0.
Und minus 7 durch 1 0 0 1.
Und minus 8 ist 1 0 0 0.
Auf diese Art und Weise können Sie für jeden Bereich von 0 bis, also
auch so einen Bereich von 0 bis 2er Potenz minus 1, so einen Bereich
von minus 2er Potenz bis plus 2er Potenz machen.
Und wenn Sie hier außen die Repräsentation stehen lassen, dann haben
Sie die Repräsentation für diese Zahlen.
Das ist eine spezielle Repräsentation von einem endlichen Bereich von
ein paar positiven, paar negativen Zahlen unter 0.
Und diese Darstellung heißt 2er Komplementdarstellung.
Und das ist das, was typischerweise heutzutage CPUs machen für ganze
Zahlen.
Was man sieht, ist die negativen Zahlen, also hier in dem Beispiel
jedenfalls von minus 1 bis minus 8, die haben alle Repräsentationen,
wo das Bit ganz links eine 1 ist.
Und die nicht negativen Zahlen, 0 und die positiven, die haben alle
eine Repräsentation, wo vorne dran eine 0 steht.
Das ist immer so, auch wenn Sie das größer machen, bei 2er
Komplementdarstellung, das erste Bit sagt Ihnen, ist die Zahl negativ
oder nicht.
Das kann man da ganz leicht ablesen.
Aber die Frage ist jetzt noch, wie kommt man im Allgemeinen, also zum
Beispiel von der minus 6 zu 1, 0, 1, 0.
Das sieht jetzt nicht so ganz ähnlich aus wie die Repräsentation von
der plus 6, 0, 1, 1, 0.
Da sieht man nicht so richtig, wie passt denn das zusammen?
Und vor allem, wenn man die beiden addiert, wieso kommt dann 0 raus?
Also gucken wir uns das ein bisschen genauer an.
Also erstens 2er Komplementdarstellung, da legt man sich also fest,
ich habe Alphabet 0, 1 und ich nehme jetzt Bitstrings einer gewissen
Länge L.
Die ist im Prinzip beliebig.
In modernen CPUs ist das halt 32 oder 64 oder so etwas.
Die Anzahl, die Länge der Zeichenketten zur Repräsentation von ganzen
Zahlen in 2er Komplementdarstellung.
64 Bit, da kann man schon eine ganze Menge Zahlen repräsentieren.
Und welche Zahlen repräsentiert man?
Das sind also die um die 0 links und rechts.
Und ins Negative geht man dann bis minus eine 2er Potenz, nämlich 2
hoch L minus 1.
Und nach rechts geht man nicht bis zur 2er Potenz, so weit kommt man
nicht, weil man ja für die 0 auch noch was braucht.
Also man hat dann eine positive Zahl weniger, als man negative Zahlen
hat.
Man geht nur bis 2, bei den positiven Zahlen bis plus 2 hoch L minus
1, minus 1.
Also in dem Beispiel eben nur bis plus 7, nicht bis plus 8.
Von minus 8 bis plus 7.
So, also zum Beispiel, es ist ja auch immer sinnvoll, wenn Sie
irgendwelche Definitionen sehen, gucken Sie sich das konkret an für
irgendwelche kleinen Beispielwerte.
Jetzt für L gleich 1, können Sie sich das auch noch mal aufschreiben,
was da passiert, das ist nicht so spannend.
Für L gleich 2 hätten wir die Zahlen von minus 2 bis 1.
Für L gleich 8 von minus 128 bis plus 127.
Gerade hatten wir den Fall L gleich 4.
L gleich 64 gibt halt größere Zahlen links und rechts, also
betragsmäßig größere.
So, und dann will man jetzt also für jede dieser Zahlen aus so einem
Bereich KL die sogenannte 2er Komplement Darstellung festlegen, die
dann aus genau L Ziffern aus dem Alphabet 0 1 besteht.
Für alle Zahlen gleich lang, ja.
Und die Definition ist, also falls die Zahl, die Sie repräsentieren
wollen, positiv ist, also zwischen 0 und 2 plus 2 hoch L minus 1,
minus 1, dann nehmen Sie einfach die normale Binärdarstellung.
Und weil die Zahl hinreichend klein ist, reichen da L minus 1 Bits und
machen eine 0 vorne dran.
Und was Sie haben, ist also die ganz normale Binärdarstellung.
Und wenn Sie eine negative Zahl haben, dann habe ich gerade schon
gesagt, man sieht vorne dran, das erste Bit ist immer 1.
Und was dahinter kommt, ist die Binärdarstellung einer positiven Zahl,
und zwar der Zahl 2 plus 2 hoch L minus 1 plus das X.
Und X ist echt kleiner 0.
Das ist jetzt ein bisschen komisch.
Sieht das aus, so ein bisschen nicht so schön homogen.
Warum macht man das genau andersrum?
Das macht man, weil hinterher die Arithmetik einfach zu implementieren
ist, schön funktioniert.
Das gucken wir uns gleich nach einem Beispiel an.
Also das ist die Definition von Zweierkomplement, ja.
So ist es einfach.
Wenn Sie wissen wollen, wie minus 127 in Zweierkomplementdarstellung
aussieht mit 8 Bits, dann müssen Sie halt diese Formel nehmen.
Und weil minus 127 negativ ist, müssen Sie also eine 1 hinschreiben
und dahinter die Binärdarstellung von 128 minus 127.
Also von 1.
Mit L minus 1 Bits, lauter Nullen und ganz hinten eine 1.
So.
Ja und der Witz ist, auch wenn die Definition ein bisschen komisch
aussieht, so ein bisschen schräg, es funktioniert.
Man kann einfach so rechnen, wie man es aus der Schule kennt.
Also ich habe hier mal spaßhalber für L gleich 4, zwei Zahlen
hingeschrieben, 7 und minus 5, ja.
Das können Sie auf dem Bildchen weiter vorne nochmal nachgucken.
Das hier ist hoffentlich wirklich minus 5.
So und wie rechnet man?
Na ja, also man geht die Stellen von hinten nach vorne durch, wie im
Zehner -System und addiert halt immer zwei Ziffern und hat vielleicht
einen Übertrag.
Also jetzt hier, man fängt ganz hinten an.
1 plus 1, das ist 2.
Wir sind aber bei Darstellung im Binärsystem.
2, das ist ja 0, 1.
Also hinten die 0, vorne die 1.
Und dezimal, wenn Sie 8 plus 3 ausrechnen, das ist 11, dann schreiben
Sie da eine 1 hin und haben eine 1 Übertrag.
Und hier 1 und 1 ist 2, haben Sie eine 0 und eine 1 Übertrag.
Also dann schreiben Sie hier eine niedrigste Stelle als Summe eine 0
hin und da eine 1, weil 1, 0, 2 ist.
Und das ist hier 1 plus 1.
So und dann betrachten Sie die nächste Stelle.
Da haben Sie hier 1 plus 1 plus 1, das ist 3.
3 binär ist 1, 1.
Also schreiben Sie eine 1 hin, die hintere und die vordere ist
Übertrag zur nächsten Stelle.
Und dann haben Sie hier 1 plus 0 plus 1, das ist 2.
Das ist wieder unten eine 0 und einen Übertrag von 1.
Und dann haben wir hier 0 plus 1 plus 1 ist 2.
Das ist ein Summenbit von 0.
Und da hätten wir noch einen Übertragsbit.
Und wenn Sie hier in zweier Komplementdarstellung rechnen, wenn Sie da
vielleicht ganz vorne noch einen Übertragsbit am Ende übrig haben,
schmeißen Sie das einfach weg.
Einfach verschwunden.
Und was man jetzt erstmal hier in diesem Beispiel sieht, Hurra, es
kommt raus, die Binärdarstellung der Länge 4 von 2.
Also in diesem Beispiel hat es funktioniert und die gute Nachricht
ist, es funktioniert immer.
Also was hier immer rauskommt, ist die Summe von den beiden Argumenten
Modulo...
jetzt kann ich nicht mehr sagen Modulo 16, denn es kann ja auch was
Negatives rauskommen.
Also es kommt eine Zahl raus, die um 16 weg ist von der Summe Modulo
16.
Das kann man beweisen, dass das immer schön klappt.
Es ist allerlei Rechnerei und wir sparen uns das mal einfach an dieser
Stelle.
Im Zweifelsfall natürlich wieder Induktion, aber ich habe es mal
versucht hinzuschreiben, das wird etwas länglich und man lernt nicht
wirklich viel dabei.
Und der Punkt ist, so eine richtige CPU, wenn die zwei Zahlen addiert,
die macht das nicht so von hinten nach vorne ein Bit nach dem anderen
angucken.
Also selbst wenn wir jetzt beweisen, das funktioniert, wir hätten
etwas bewiesen, was nicht benutzt wird in der CPU.
Aber also das Ergebnis ist so, nur man macht das ein bisschen
geschickter, nicht so mit den Überträgen, nicht so plump langsam, wie
wir das hier durch exerziert haben.
Da kann man halt noch Abkürzungen finden.
Das lernen Sie dann, wenn Sie die Vorlesung hören, denke ich mal
irgendwann in, wie heißt die Vorlesung?
Rechnerorganisation oder technische Informatik oder irgendwie so.
Vielleicht eher in technischer Informatik.
Gut.
Also, das ist zweier Komplementdarstellung und das ist wirklich das,
was CPUs benutzen für die Repräsentation von ganzen Zahlen in einem
gewissen Bereich.
Und der ist endlich.
Und wenn Sie mit größeren Zahlen rechnen wollen, dann muss man halt
typischerweise Zündzüge machen, dass da nichts, was direkt durch die
CPU unterstützt wird, sondern da brauchen Sie oben drüber so ein
bisschen was.
Worum Sie sich hoffentlich auch nicht selber kümmern müssen, je
nachdem in welcher Sprache Sie umhantieren.
So.
Und damit haben wir also so eine erste Zutat für echte CPUs, zweier
Komplementdarstellung.
Und rechnen Sie im Zweifelsfall noch so ein bisschen damit rum.
Also, jedenfalls Addition.
Und machen Sie sich klar, was da immer passiert.
Jetzt nicht in dem Abschnitt, der gleich kommt, sondern danach werden
wir dann anfangen,
irgendwie zu übersetzen, Repräsentationen von irgendwelchen Dingern,
also zum Beispiel Zahlen in einem System in ein anderes System.
Übersetzungen und dann Codierungen.
Und da taucht noch ein bisschen Notation auf, einfach für Funktionen,
für Abbildungen.
Die habe ich jetzt hier nochmal kurz zusammengefasst, dass das auch
irgendwo mal kompakt noch steht und nicht völlig verstreut ist im
ganzen Vorlesungsskript.
Das erste ein bisschen schreibweise, das wird auch gleich im nächsten
Kapitel dann noch wieder auftauchen.
Wenn wir zwei Mengen haben, A und B, und wir wollen hinschreiben die
Menge aller Funktionen, Menge aller Abbildungen mit Definitionsbereich
A und Zielbereich B, dann schreibe ich dafür B hoch A.
Also, wenn A und B zwei Mengen sind, B hoch A ist die Menge aller
Abbildungen von A nach B.
Dass das jetzt da sozusagen in der umgekehrten Reihenfolge steht,
vorne steht das B und hinten oben das A, ich weiß nicht, wer sich die
Notation ausgedacht hat, aber vielleicht der, der sich das ausgedacht
hat, hat das so hingeschrieben, weil nämlich das Folgende gilt, wenn
Sie sich angucken, wie viele Abbildungen gibt es von A nach B.
Also, wie groß ist die Menge aller Abbildungen von A nach B?
Was ist die Kardinalität von B hoch A?
Dann, wenn die Mengen endlich sind, jedenfalls, ist das gleich
Kardinalität von B hoch Kardinalität von A.
Weil Sie für jedes mögliche Argument, da haben Sie Kardinalität von A,
viele haben sie immer B-Möglichkeiten, was soll denn der Funktionswert
sein?
Da haben Sie B-Möglichkeiten für das erste mögliche Argument, B
-Möglichkeiten für den zweiten Wert, B-Möglichkeiten für den dritten
Wert, B mal B mal B mal B.
Also, das schreibe ich einfach so.
Also, statt zu schreiben, F ist eine Abbildung, Doppelpunkt A, Pfeil
B, könnte ich auch schreiben, F ist Element von B hoch A.
Das ist exakt das Gleiche.
Das Zweite, das ist Ihnen, nehme ich doch mal ganz stark an, schon
längst vertraut, wenn Sie eine Abbildung haben von A nach B und dann
eine zweite von B nach C, dann kann man die auch hintereinander
ausführen.
Also, wenn Sie ein Element aus A nehmen, können Sie erstmal mit der
ersten Abbildung F abbilden, auf das zugehörige Element in B und das
Element, was Sie dann da kriegen, mit der Abbildung G, gleich weiter
abbilden auf ein Element in C.
Und das, was Sie dann kriegen, da haben Sie eine Zuordnung für jedes
Element aus A, gibt es dann ein Element in C, das ist auch wieder eine
Abbildung und für die schreibe ich G-Kringel-F.
Ja, und bitte Vorsicht, wenn da G-Kringel-F steht, das heißt, erst
wird F angewendet, dann G.
Das ist auch wieder irgendwie von der Reihenfolge her ein bisschen
komisch.
Aber wenn Sie sich das explizit hier hingeschrieben angucken, was ist
der Funktionswert für A bei der Komposition, das ist eben, auf A wird
erst F angebindet und dann G und wenn wir das so mit G von F von A
hinschreiben, da steht auch das G, was hinterher angewendet wird,
links vom F.
Aber seien Sie vorsichtig, es gibt auch Leute, die vertauschen die
Reihenfolge bei der Notation für Funktionskomposition.
Ich habe das Gefühl, die meisten machen es so, wie es hier steht, aber
es gibt ein paar, die schreiben es genau andersrum hin.
Also wenn Sie irgendetwas lesen und Sie wundern sich irgendwie
ziemlich schnell darüber, wie da Funktionen komponiert werden, lesen
Sie mal nach, wenn es der Autor explizit sagt, ob das vielleicht
andersrum gemeint ist.
So und wenn Sie drei Funktionen hintereinander haben, also F von A
nach B, G von B nach C, H von C nach D, dann können Sie also erst F
anwenden und dann G und dann H und dann haben Sie hier wieder so einen
Ausdruck, wo Sie Klammern links oder Klammern rechts setzen können und
die Mitteilung ist, es ist egal, die Funktion, die Sie da beschreiben,
ist immer die gleiche.
Also man kann die Klammern auch einfach weglassen.
Und das ist sozusagen in ganz vielen Fällen so.
Addition von Zahlen, Multiplikation von Zahlen.
Sie können Klammern setzen, wie Sie wollen.
Die einzige Ausnahme, die wir bisher gesehen haben, ist irgendwie
sowas wie Subtraktion oder Mengendifferenz.
Da können Sie nicht einfach Klammern hin und her schieben.
Eine Funktion, die gar nichts tut, aber manchmal doch nützlich ist,
hinzuschreiben, ist die Identität.
Also für jede Menge können Sie die Abbildung betrachten von M nach M
und jedes Element wird abgebildet auf sich selbst.
Da passiert also rein gar nichts, aber es ist eine Abbildung von einer
Menge auf sich selber.
Und die Beobachtung ist, wenn Sie eine Abbildung haben von A nach B,
wenn Sie erst die Abbildung von A nach B anwenden, dieses F und danach
noch die Identität auf B.
Also F liefert Ihnen eine Zahl in B.
Die Identität liefert Ihnen dazu nochmal die gleiche Zahl.
Die Komposition, das ist einfach F.
Und umgekehrt, wenn Sie ein Element aus A erst mit der Identität in A
abbilden, bleiben Sie bei dem gleichen Element.
Und wenn Sie es dann mit F abbilden, kriegen Sie eben das Element, das
F liefert.
Also diese identischen Funktionen, aber bitte Vorsicht, links und
rechts hier, wenn A und B verschieden sind, das sind verschiedene
identische Funktionen.
Die Mengen können unterschiedlich groß sein, das können ganz
verschiedene Dinger sein, sozusagen.
Aber diese identischen Funktionen sind links bzw.
rechts neutrales Element, wenn Sie den Begriff schon mal irgendwo
gesehen haben.
Wenn Sie jetzt zwei Funktionen haben, F von A nach B und eine zweite
Funktion G von B zurück nach A, dann können Sie also zum Beispiel erst
F anwenden und dann G hintendran oder Sie können auch erst G anwenden
und dann F und gehen Sie von B nach A und wieder zurück.
Und dann kann natürlich im Allgemeinen alles Mögliche passieren.
Aber es gibt halt einen Fall, der interessant ist.
Es kommt nämlich vor, und dann heißt G die Umkehrfunktion von F oder
die Inversefunktion zu F, dass nämlich egal, was Sie angucken, erst F
und dann G oder erst G und dann F, wenn Sie die beiden hintereinander
anwenden, was passiert ist?
Nichts.
Die Komposition ist immer die Identität.
Sie landen immer wieder bei dem Element, wo Sie ganz am Anfang
gestartet sind.
Ja und dann heißt also G die Inverse zu F und man schreibt dann
manchmal auch statt G einfach F hoch minus 1.
Und wenn G die Umkehrfunktion zu F ist, dann überlegen Sie mal, was
man da überhaupt tun muss.
Es ist nicht viel.
Dann tatsächlich F ist auch die Umkehrfunktion zu G.
Und deswegen, weil es egal ist, sozusagen die Reihenfolge, sagt man da
manchmal einfach, benutzt man so eine symmetrische Formulierung, F und
G sind inverse zueinander.
Und also wenn in der Situation sozusagen egal, was die Abbildung F
macht, Sie können es immer wieder rückgängig machen.
Und umgekehrt, was die Umkehrabbildung macht, Sie können es wieder
rückgängig machen.
Ja, die sind inverse zueinander.
Das ist natürlich zu gegebenen... also für manche... und es gibt
Abbildungen F, da klappt das einfach nicht.
Wenn Sie eine Abbildung F haben, die zwei Elemente auf den gleichen
Funktionswert abbildet, dann können Sie nicht eindeutig zurückkommen.
Wie soll das funktionieren?
Also wenn F nicht injektiv ist, dann kann es kein G geben, sodass wenn
Sie hinterher zurückgehen, wieder genau beim Original landen, denn Sie
sind ja von zwei Originalen beim gleichen Funktionswert unter F
angekommen.
Also manche Funktionen F haben einfach keinen Linksinversus und Sie
haben es nur dann, wenn F injektiv ist.
Und umgekehrt, F-Kringel-G ist die Identität auf B.
Das kann nur funktionieren, wenn F surjektiv ist.
Denn wenn Sie erst G anwenden und dann F und dann wollen Sie, ja, egal
bei welchem Element B Sie angefangen haben, egal was G gemacht hat,
Sie wollen wieder zurück zum Originalelement, dann offensichtlich
müssen Sie mit F zu jedem Element in B kommen können.
Also F muss dann auch surjektiv sein.
So, und das ist hier nochmal erwähnt, ohne dass wir das hier jetzt
alles im Detail beweisen, aber vielleicht bleibt das ein oder andere
hängen.
Es ist gut, wenn man das vielleicht so ein bisschen im Hinterkopf hat.
Also manchmal gibt es halt so ein G, sodass G-Kringel-F die Identität
ist, aber umgekehrt nicht.
Jedenfalls, wenn G-Kringel-F die Identität ist, dann heißt G
Linksinverse zu F, weil G hier links von F steht.
Und wenn F-Kringel-G die Identität auf B ist, dann heißt G
Rechtsinverse zu F, weil G hier rechts von F steht.
Und was ich gerade gesagt habe, wenn F ein Linksinverses hat, dann ist
F injektiv und umgekehrt.
Und F hat ein Rechtsinverses genau dann, wenn F surjektiv ist.
Und wenn Sie eine Funktion haben, die sowohl ein Links- als auch ein
Rechtsinverses hat, also gerade eben habe ich ja gesagt, bei
Umkehrfunktionen, das muss das gleiche G sein, egal ob man es links
oder rechts hinschreibt.
Jetzt könnte es ja erst mal rein theoretisch sein, dass eine Funktion
ein Linksinverses hat und eine andere Funktion als Rechtsinverses.
Mitteilung, nein, das kann nicht passieren.
Wenn eine Funktion sowohl ein Links- als auch ein Rechtsinverses hat,
dann sind Links- und Rechtsinverses gleich.
Überlegen Sie sich mal, das ist ganz einfach hinzuschreiben.
Also der Beweis passt in eine Zeile.
Und deswegen ist auch klar, dass eine Funktion nicht verschiedene
Umkehrfunktionen haben kann.
Die ist dann auch immer eindeutig.
Überlegen Sie sich das auch mal.
Das ist auch eine Zeile.
Und deswegen F hat eine Umkehrfunktion genau dann, wenn die Abbildung
bijektiv ist.
Und das hat man schon mal gelernt.
Sie haben wirklich so eine Eins-zu-eins-Beziehung zwischen den
Elementen in den beiden Längen.
So, das nur so am Rande.
Also und was wir jetzt insbesondere gleich erst mal brauchen, ist
Komposition von Funktionen.
Und was uns jetzt interessiert, ist Übersetzungen.
Und als einfaches Beispiel, stellen Sie sich vor, wir haben
Repräsentationen, eine Hexadezimaldarstellung von Zahlen.
Also Hexadezimaldarstellung, das haben wir also so ein Alphabet mit 16
Ziffern, 0 bis 9, A bis F.
Wir haben irgendein Wort über diesem Alphabet und wir wollen jetzt das
übersetzen in Binärdarstellung.
Und zwar also dann eine Folge von Nullen und Einsen, die die gleiche
Zahl bedeutet.
Wir wollen, dass die Semantik die gleiche bleibt.
Die beschriebene Zahl ist die gleiche.
Wie kann man das machen?
Also die Abbildung nenne ich jetzt mal trans 2, 16 in Zweiersystem von
Sechzehnersystem.
Man kann zum Beispiel sagen, ich nehme die Hexadezimaldarstellung, das
bedeutet ja immer eine Zahl.
Diese Abbildung haben wir Nummer 16 genannt.
Dann habe ich die Zahl und anschließend wende ich an die Abbildung,
die mir die Binärdarstellung, die binäre Repräsentation der Zahl
liefert.
Also für jedes Wort über dem Alphabet mit 16 Ziffern, 0 bis 9, A bis
F.
Ich gucke mir an, welche Zahl ist das, repräsentiere die Binär.
Dann habe ich meine Übersetzung.
Also zum Beispiel die Übersetzung von A3, das ist also die
Übersetzung, die Darstellung im Binärsystem der Zahl, die durch A3
dargestellt wird.
Das ist 163, 10 mal 16 plus 3 mal 1 und das ist das hier.
Da ist überhaupt nichts Tiefsinniges dahinter, aber weil man es so
definiert auf dem Umweg, um welche Zahl geht es denn, ist klar, das
Ergebnis der Abbildung beschreibt die gleiche Zahl wie das Original.
Und das ist das, was wir eine Übersetzung nennen wollen.
Also eine Übersetzung ist nicht nur einfach, wir machen aus einem Wort
irgendein anderes Wort, sondern wie im alltäglichen Leben.
Also wenn Sie einen deutschen Text ins Englische übersetzen, also die
Bedeutung des englischen Textes sollte halt immer noch die gleiche
sein wie die deutsche, sonst würden Sie das nicht Übersetzung nennen.
Wenn Sie Faust nehmen und übersetzen ins Englische und raus kommt
Hamlet, dann war irgendwas verkehrt.
Das ist keine Übersetzung.
Gut, also allgemeiner, jetzt in diesem Beispiel war es ganz harmlos,
wir konnten alle Wörter übersetzen, im Allgemeinen nicht.
Also wenn Sie von Deutsch nach Englisch übersetzen, manche Zeichen
folgen, es sind halt gar kein deutscher Text.
Was wollen Sie da übersetzen?
Also im Allgemeinen, wir haben nur so eine Teilmenge von A-Stern für
irgendein Alphabet A, die Wörter, die eine Bedeutung haben, die man
übersetzen kann und will.
Und jedes Wort hat eine Bedeutung.
Was weiß ich, was das ist, nenne ich die Menge einfach mal Sem wie
Semantik.
Die Bedeutung kann, wie gerade in dem Beispiel, einfach eine Menge von
Zahlen sein.
Wenn Sie Java-Programme haben als Wörter über Ihrem Alphabet, dann ist
die Bedeutung halt vielleicht sowas wie, was passiert, wenn ich das
Programm ausführe.
Das sind dann vielleicht relativ komplexe Objekte.
Und wenn Sie jetzt ein Java-Programm übersetzen in ein C-Programm oder
ein Haskell-Programm oder was weiß ich, dann ist eben hoffentlich für
Haskell -Programme auch definiert, was bedeutet es, es auszuführen.
Und Sie würden sagen, das ist eine Übersetzung, wenn die Ausführung
des Original-Java-Programms und die Ausführung des übersetzten Haskell
-Programms das Gleiche macht, sozusagen.
Gut.
Ja, und damit etwas eine Übersetzung ist, also da haben wir dann noch
einen Zielbereich.
Ja, wir wollen neue Wörter produzieren über einem anderen Alphabet.
Und da haben wir jetzt im Allgemeinen auch nicht beliebige
Zeichenketten, die irgendeine Bedeutung haben, sondern auch so eine
formale Sprache LB.
Und eine Übersetzung ist dann also eine Abbildung, die ein Wort aus
LA, also jedem vernünftigen Java-Programm zuordnet, ein Wort aus LB,
vielleicht ein vernünftiges Haskell-Programm.
Wenn das geht, wer weiß.
Und wir wollen aber eben nicht beliebige Abbildungen zulassen, sondern
wir haben für die Wörter in LA und für die Wörter in LB jeweils
definiert, was ist ihre Bedeutung.
Und dieser Bereich Bedeutungen ist der gleiche für LA und LB.
Und was man dann eben will, ist, egal welches Wort W man übersetzt,
die Bedeutung des nicht übersetzten Wortes W hier, gegeben durch so
eine Abbildung, die jedem Wort aus LA Bedeutung zuordnet, muss gleich
der Bedeutung sein, die die Übersetzung des Wortes bezüglich der
anderen Bedeutungsabbildungen hat.
Also man schreibt dann manchmal hier so ein Bildchen und macht da so
einen kleinen Kringel rein, wenn man will, dass Semantik A ist gleich
Semantik B Kringel F.
Auf beiden Wegen, es muss das gleiche rauskommen.
Sowas soll Übersetzung heißen.
So.
Und ein Beispiel und alles Weitere gucken wir uns dann nächste Woche
an.
Für heute war es das mit der Vorlesung.
Guten Morgen zusammen, herzlich willkommen zu unserer vierten Übung.
Heute geht es ein bisschen über formale Sprachen und
Zahlendarstellung.
Also formale Sprachen, da habe ich schon, glaube ich, in der
vorletzten Übung erwähnt, dass wir, sagen wir, logische Formeln
syntaktisch definiert haben und die Menge der Formeln ist eine
Sprache.
Dann haben wir uns genauer angeschaut, was Sprachen sind.
Sprachen sind einfach Teilmengen dieser Alphabet A.
Da sind die Sprachen eben die Teilmengen von dem A auf Stern, was eben
alle Wörter über A sind.
Und dann haben wir ein paar Operationen auf formale Sprachen
definiert, unter anderem die Konkatenation von zwei Sprachen.
Also dann nehme ich alle Wörter, also die Konkatenation sieht so aus,
ich konkateniere Wörter aus der einen Sprache mit Wörtern aus der
anderen.
Ganz einfach.
Und damit können wir auch etwas Ähnliches wie Potenzieren bei Sprachen
definieren.
Also wir haben angefangen mit L hoch 0, das soll einfach die Menge mit
dem leeren Wort, weil das gut zusammenpasst mit der Potenzieroperation
später.
Und wir haben dann induktiv definiert, L hoch K plus 1 soll dann L
-konkateniert mit L hoch K sein.
Und dann können wir sukzessive K verringern und dann das Ganze L
-konkateniert mit sich selber K plus 1 mal sein.
Und wenn das 0 mal konkateniert mit sich selber, dann ergibt das das
leere Wort.
Und dann habe ich ein paar Beispiele unten.
Unter anderem die leere Menge konkateniert mit sich selber, das ergibt
wieder die leere Menge.
Ja klar, ich kann überhaupt keine Wörter miteinander konkatenieren,
weil ich überhaupt keine Wörter habe.
Aber auch wenn ich was mit der leeren Menge konkateniere, dann kommt
wieder die leere Menge raus, weil ich ja keine Wörter in der leeren
Menge mit irgendwelchen anderen Wörtern konkatenieren kann.
Dafür, wenn ich die Menge mit dem Epsilon fehle und das mit einer
Sprache konkateniert, dann kommt immer die gleiche Sprache raus.
Also ich nehme einfach Epsilon am rechten Ende und das ist ja neutral.
Und dann was ein Wort konkateniert mit dem leeren Wort Epsilon, ergibt
wieder das gleiche Wort wie eben.
Und dann bleibt das alles gleich.
Und deswegen kommt die Motivation für die Definition von R hoch 0 ist
ja die Menge mit dem Epsilon, weil am Ende, wenn ich zum Beispiel R
hoch 2 aufschreibe, dann ist das L konkateniert mit R hoch 1 und das
ist L dann konkateniert mit R hoch 0 und dann ist alles okay dahinten.
Also das verschwindet und dann bleibt nur L konkateniert mit R.
Und dann hier im Beispiel unten, gleich im nächsten Beispiel, dann A,
B, B hoch 1.
Das ist die Sprache A, B, B konkateniert mit der Sprache A, B, B hoch
0 und dann kommt die Menge mit dem Epsilon, das, wie gesagt, bleibt
alles erhalten.
Das ergibt dieselbe Sprache, wie das sein sollte.
Auch wie bei Potenzieren, wenn ich hoch 1 mache, dann kommt die
gleiche Zahl raus.
Und wenn ich weiter potenziere, dann kommen mehrere Konkatenzionen der
Wörter.
Es können mehr Wörter herauskommen, aber es müssen nicht mehr Wörter
herauskommen.
Also wenn ich zum Beispiel die Menge mit Lehrenwort und dann auch die
Wörter A, zweimal das A, dreimal das A nehme und so weiter und das
hoch 2 mache, potenzieren miteinander, mit dem selben Sprache
konkatenieren, dann kommt die selbe Sprache raus.
Es muss nicht etwas Größeres herauskommen.
Dann, natürlich ist es in diesem, wenn ich L hoch K betrachte,
natürlich sind alle Wörter von L, natürlich alle Potenzen von Wörtern
von L hoch K da drin, aber es muss nicht unbedingt gleich sein.
Wenn ich zum Beispiel die Wörter A und B habe und die Potenzen dieser
Wörter auch zweimal anschaue, dann gibt es nur A, A und B, B, aber das
L hoch 2 ist dann alle Wörter, die in L sind, die können auch mit
anderen Wörtern in L konkateniert sein, nicht unbedingt mit sich
selber, was mit den Potenzen von Wörtern passiert.
Ausnahme mit der Lehrermenge, wird das immer gleich sein, also
Lehrermenge hoch K wird immer Lehrermenge sein, weil ich keine Wörter
nehmen kann für diese Operation mit der Konkatenation.
Und das ist der Fall, K ist zumindest so groß wie 2, aber ich möchte
auch den Fall betrachten, wo K nicht größer als 1 ist.
Was passiert dann?
Machen wir einfach Fallunterscheidung, was ist K gleich 1?
Da ist die linke Menge einfach Wörter hoch 1 und dann gibt das die
Wörter in der Sprache, das ist wieder die Sprache selber und die
Sprache selber hoch 1 ist sich selber.
Das gibt es für jede Sprache, also nicht einfach für jede Nicht
-Lehrersprache, sondern das gibt es auch für die Lehrermenge.
Wenn Lehrermenge hoch 1 ist, ist Lehrermenge hoch 0, das ist
Lehrermenge mit dem leeren Wort und dann gibt es die Lehrermenge
wieder.
Also kein Problem.
Bei K hoch 0 ist es ein bisschen anders, also wenn ich die Wörter hoch
0 nehme, die in der Sprache sind, dann kommt die Menge mit dem leeren
Wort raus, falls die Sprache nicht leer ist.
Also wenn die Sprache nicht leer ist, dann kann ich keine Wörter
nehmen und die potenzieren.
Dann kann ich wieder keine Wörter erzeugen.
Und dann ist L hoch 0 gleich die Menge mit der Messung, obwohl das die
Lehrermenge ist und ist echt größer als die Menge, die keine Wörter
enthält.
Also bei K hoch 0 gilt die gleiche von da oben, nur wenn die Sprache
nicht leer ist.
Also Botschaft, man muss sich immer Gedanken machen über die
Randfälle, also Lehrermenge, die Menge mit Zahlenwörtern und so
weiter.
Manchmal geht da was schief.
In der Regel, wenn was schief geht, dann geht es da.
Dann haben wir auch eine zweite Operation für formale Sprachen
kennengelernt und das ist der Konkatenationsabschluss.
Da haben wir das mit L hoch Stern gekennzeichnet und das passt
zusammen mit unserer Definition von A hoch Stern.
A hoch Stern war einfach der Abschluss über das Alphabet und wir
können auch Abschluss über eine Sprache nehmen.
Und das ist dann einfach alle L hoch Is und I geht von 0, 1, 2 bis zum
Endlichen und ich vereinige alle dieser Sprachen.
Und wir haben auch den Epsilon-freien Abschluss definiert und dann
fange ich nicht bei 0 an, sondern ich fange bei 1 an.
Aber warum Epsilon-frei?
Also intuitiv, das sollte nicht das Epsilon enthalten, seitdem das
Epsilon schon in der Sprache war.
Also zum Beispiel, wenn ich eine Sprache mit dem A auf Stern nehme,
dann kommen alle Wörter beliebiger Länge über das A.
Aber wenn ich A hoch Plus nehme, dann kommen nur Wörter positiver
Länge.
Dann fange ich bei dem Wort A mit einem Symbol A und dann mit zwei
Symbolen A und so weiter.
Das Lehrewort ist nicht da, weil es nicht in der ursprünglichen
Sprache enthalten war.
Ich kann auch über alle Sprachen reden, zum Beispiel diese Sprache von
vorher, A und zweimal das B.
Wenn ich hoch Stern nehme, dann habe ich natürlich das Lehrewort da,
ich habe die Wörter A und B, B und ich habe alle möglichen
Konkatenationen da drin.
Und es gibt unendlich viele davon.
Ich werde noch darüber sprechen, über diese Unendlichkeit.
Wenn ich das A hoch Stern wieder hoch Stern mache, dann kommt wieder A
hoch Stern raus.
Und man soll sich da nicht überraschen, wie wir später sehen werden.
Es gibt dann beim Konkatenationsabschluss ein paar pathologische
Fälle.
Also wie gesagt, es gibt immer diese Randfälle, die man sich am besten
Gedanken machen soll.
Und zum Beispiel bei der Lehrermenge, wenn ich das hoch Plus nehme,
dann ist das alle Vereinigungen, Lehrermenge hoch I und I ist
zumindest eins.
Und dann haben wir ja gesehen, Lehrermenge hoch irgendwas Positives
ist wieder Lehrermenge.
Wenn ich Lehrermenge und I vielmal mit sich vereinige, dann bleibt es
leer.
Aber wenn ich die Lehrermenge hoch Stern nehme, dann fange ich bei
Lehrermenge hoch Null an und die Menge da ist nicht leer.
Die Menge da enthält das Lehrerwort nach unserer Definition.
Und dann, wenn ich das mit der Lehrermenge wieder vereinige, dann
kommt eine Menge, die doch ein Element hat.
Das ist ein bisschen kontrainduktiv, dass das hoch Stern größer
geworden ist.
Zum Beispiel, wenn ich die Menge mit dem Lehrerwort nehme und die hoch
Plus oder hoch Stern mache, dann kommt immer die gleiche Menge raus.
Und es sind nur die zwei Mengen da, die ähnliche Sprachen erzeugen mit
diesen Operationen Plus und Stern.
Also, wenn ich irgendwelche, wenn ich ein Wort habe mit zumindest
einem Zeichen, dann kann ich die mehrmals mit sich aneinander
konkretisieren und dann habe ich automatisch ähnlich viele Wörter.
Und dann, wie gesagt, dieser epsilon-freie Teil von dem Abschluss soll
so zu verstanden sein, dass wenn ich epsilon in der Sprache nicht
hatte, dann ist es im epsilon-freien Abschluss auch nicht da.
Also, zum Beispiel bei der Lehrermenge, es hat kein Lehrerswort da
enthalten, dann wenn ich diese Menge, diese Sprache hoch Plus nehme,
dann bleibt es ohne epsilon.
Aber wenn ich das hoch Stern mache, dann ist automatisch immer das
epsilon dabei.
Und man tendiert dazu zu verstehen, ja vielleicht ist sehr hoch Plus,
sehr hoch Stern ohne das epsilon, aber das ist nicht wahr.
Das haben wir gerade gesehen.
Zum Beispiel bei der Menge mit dem epsilon, also die Menge mit dem
epsilon ist, die Menge mit dem epsilon, die Menge mit dem epsilon hoch
Stern ist die gleiche Menge.
Die ist nicht um ein Element kleiner.
So etwas geht nicht.
Dann können wir auch diesen Konkordationsabschluss mehrfach anwenden
und uns Gedanken machen, was passiert, dann mache ich viele
Konkordationen, über was schon mit Konkordationen erhalten worden ist.
Und wenn man sich klar machen will, was das ist, dann nimmt man
einfach die Definition und die besagt, das ist die Vereinigung über
alle diese Potenzen von der Menge hoch Stern.
Und dann, ja das ist dann, das ist L hoch Stern hoch Null, das muss
die Menge mit dem leeren Wort sein, dann vereinigt die Menge selber,
vereinigt die Menge selber diese Menge zum Quadrat und so weiter diese
Vereinigung.
Und schon beim dritten Term ist es gut, wenn man sich Gedanken macht,
was ist dieser Konkordationsabschluss dann zum Quadrat.
Dann sind das Wörter, also Wörter von der Form, die ich so schreiben
kann, also ein Wort davor und ein Wort dahinter und die beiden Wörter
sind wieder im Konkordationsabschluss enthalten.
Das heißt, ich kann den vorderen Teil als N viele Wörter schreiben
nacheinander und N kann Null sein oder 1 und 2 und so weiter.
Und der rechte Teil darf auch so aufgeschrieben werden und es muss,
wenn das gleich Null ist, dann ist es so zu verstehen, dass das leere
Wort rauskommt.
Dann haben wir alle Fälle gedeckt und ich kann diese W, W' dann als
alle diese Wörter nacheinander schreiben und das war wieder im
Konkordationsabschluss.
Also ich habe einfach N plus M Wörter aus L genommen und die
nacheinander konkordiert.
Dann ist was in L hoch Stern hoch 2 rausgekommen und da haben wir zwei
Inklusionen, also L hoch Stern hoch 2 ist in L hoch Stern als
Teilmenge da und das L hoch Stern ist wieder natürlich Teilmenge von L
hoch Stern zum Quadrat.
Und dann haben wir Gleichheit und das Spiel können wir wieder für die
weiteren Potenzen so machen, also induktiv einfach z.B.
bei L hoch Stern hoch 3, das ist L hoch Stern zum Quadrat, das
konkordiert mit dem L hoch Stern.
Das haben wir bewiesen, das muss L hoch Stern konkretmäßig selber
sein, also es kommt wieder L hoch Stern raus.
Also das bleibt gleich dann, wenn ich diesen Konkordationsabschluss
mehrfach anwende.
Das bringt mir nichts.
Nochmal zum Zusammenhang zwischen dem L hoch Stern und dem L hoch
Plus.
Also wir haben gesehen, das L hoch Plus ist nicht einfach, ich nehme
das leere Wort raus, aber es gibt einen Zusammenhang, der vernünftig
ist und das ist eben, dass L hoch Plus ist die Sprache L hoch Stern
und dann konkret mit der Sprache L.
Und man sieht schon, also wenn das leere Wort nicht in der Sprache
war, dann kann es auch in dem zweiten Konkordinationsterm nicht da
sein.
Vielleicht was Leeres mit was in der Sprache und in der Sprache gibt
es keine leeren Wörter, also kann nicht das leere Wort rauskommen.
Es könnte nur das leere Wort rauskommen, wenn die beiden Wörter leer
sein würden.
Und ein kleiner Beweis, warum diese Gleichheit gilt.
Also es geht wieder mit diesen zwei Inklusionen.
Ich nehme ein Wort aus der linken Menge, die kann ich schreiben als
V1, V2, wobei V1 in dem Konkordinationsabschluss ist und V2 in der
Sprache selber.
Und dann kann ich wieder L hoch Stern in der Definition schauen.
Es muss V1 in L hoch I enthalten sein und dann kommt, wenn ich etwas
in L hoch I mit etwas in L konkateniere, dann kommt etwas in L hoch I
plus 1.
Und I plus 1 muss echt positiv sein, deswegen kommt was in L hoch Plus
raus.
Und umgekehrt, wenn ich ein Wort in L hoch Plus nehme, dann muss das
in einem L hoch I sein und I minus 1 muss zumindest so groß wie 0
sein.
Wenn es echt kleiner als 0 wäre, dann hätten wir ein Problem mit dem L
hoch I minus 1, natürlich.
Aber L hoch I minus 1 haben wir gar nicht definiert, deswegen müssen
wir uns Gedanken machen, dass es immer noch vernünftig ist.
Aber es passt, L hoch I minus 1 ist dann zumindest so groß wie 0 und
dann kann ich L hoch I als L hoch I minus 1 konkateniert mit L
schreiben und ja, natürlich ist das in L hoch Stern konkateniert mit L
enthalten.
Deswegen habe ich diese Gleichheit.
Okay,
was können wir noch, wofür sind diese Operationen da?
Also Konkatenation und Konkatenationsabschluss.
Also ich habe eine Formalsprache da und ich habe eine mögliche
Formulierung, wie die aussehen soll, zum Beispiel die hat alle Wörter
mit ungerader Länge, aber ich möchte die etwas präziser ausdrucken.
Also ich möchte Sprachen finden, sodass ich diese Sprache als
Konkatenation dieser Sprachen, Vereinigung oder
Konkatenationsabschluss aufschreiben kann.
Dann kommt etwas Präziseres raus, also einfach nur eine Eigenschaft zu
verlangen.
Dann sage ich explizit, wie die Wörter aussehen.
Also ich zeige das jetzt in einem Beispiel.
Also ich fange an, welche Wörter können da sein, also das Lehrewort
kann nicht da sein, das Lehrewort hat Länge 0, 0 ist gerade, also das
passt nicht.
Aber bei Länge 1, da habe ich alle Wörter über A da.
Also A und B sind wieder enthalten.
Und wenn ich diese Wörter nehme, die mit Wörtern gerade Länge
konkateniere, zum Beispiel Länge 2, dann bleibt das in der Sprache.
Also dann kommen Wörter der Länge 3.
Aber auch wenn ich mehrfach diese Wörter der Länge 2 nehme, dann
bleibt es immer ungerade.
Also wenn ich keine Wörter der Länge 2 nehme, dann bleibt das Wörter
der Länge 1.
Wenn ich ein Wort der Länge 2 nehme, dann bleiben Wörter der Länge 3.
Und wenn ich zweimal dann Wörter der Länge 5 und so weiter, dann habe
ich eben alle Wörter der ungeraden Länge, die müssen so aussehen.
Hier schreibe ich noch ein Ausrufezeichen vor der Gleichheit, dass man
sich Gedanken macht, dass das gleich sein soll.
Also wenn das Wort ungerade ist, dann kann ich es immer so
aufschreiben.
Es muss ein Zeichen davorstehen, es muss weder A oder B sein.
Was dahinter kommt, muss so eine gerade Länge haben.
Dann kann ich explizit schreiben, was diese Wörter der Länge 2 sind.
Die sind einfach vier Stück, die kann ich aufschreiben und dann kann
ich dasselbe so ausdrucken.
Und dann habe ich explizit eine Form da, wie die Wörter aussehen.
Die fangen mit einem Zeichen, weder A oder B und dann gibt es mehrere
Konkatenationen, vielleicht gar keine, mit diesen Wörtern der Länge 2.
Oder ich kann es auch, ich kann wieder diese Menge von der Länge 2
wieder ausdrucken als eine Konkatenation.
Also ich habe da vorne A oder B und dahinten wieder A oder B.
Und dann einen Abschluss dafür.
Wenn ich Wörter der geraden Länge haben möchte, dann ist es einfach,
ich muss nur diesen vorderen Teil weglassen.
Dann habe ich alle Wörter mit gerader Länge.
So.
Zweites Beispiel.
Bisschen kompliziert, hier nicht gerade oder ungerade Länge, sondern
gerade Anzahl von Nullen.
Jetzt ist das Alphabet über 0, 1.
Ja, gerade Anzahl von Nullen wieder.
Das leere Wort, ich fange mit dem einfachsten Fall, das leere Wort,
das enthält genau 0 Nullen, das muss eine gerade Anzahl von Nullen
enthalten.
Das muss in der Sprache sein.
Aber wenn ich belebig viele Einsen davor oder dahinten habe, dann
ändert sich nichts.
Das bleibt eine gerade Anzahl von Nullen.
Aber ich könnte auch ein paar Nullen haben, dann vielleicht habe ich
zwei Nullen da stehen.
Dann habe ich belebig viele Einsen da vorne, dann vielleicht leer oder
doch zwei Nullen und dann belebig viele Einsen dahinten.
Aber es können auch Einsen dazwischen, zwischen den Nullen sein.
Das ist nicht ausgeschlossen.
Deswegen mache ich diese Menge noch ein bisschen größer.
Also ich kann entweder das leere Wort dazwischen haben oder ich habe
eine Null, dann habe ich vielleicht ein paar Einsen, belebig viele in
der Mitte und dann habe ich eine Null noch.
So kann ich es aufschreiben.
Aber ich könnte auch mehrere Nullen haben, nicht nur zwei, also
vielleicht vier und sechs und so weiter.
Und deswegen nehme ich einfach den Konstanzabschluss über diesen
mittleren Teil und das passt.
Warum passt das?
Also wenn ich ein Wort mit einer geraden Zahl von Nullen nehme, dann
fange ich am Anfang an, da gibt es vielleicht ein paar Einsen und dann
kommt eine Null, dann gehe ich in diesen mittleren Teil und dann gibt
es vielleicht einige Einsen bis eine Null kommt.
Und dann bin ich fertig mit diesem Abschlussteil und dann vielleicht
kommt das wieder, so ein Teil mit vielleicht Einsen und Nullen und
dann am Ende kommen belebig viele Einsen raus.
Und ich habe das leere Wort auch in der Mitte, also wird damit belebig
viele Einsen auch vor.
So, dann wechseln wir das Thema.
Wir haben auch was zur Zahlendarstellung in der Vorlesung
kennengelernt.
Ich habe Zahlen und dann möchte ich die Zahlen als Wörter
aufschreiben.
Und diese Wörter sollen über ein Alphabet von Ziffern definiert sein.
Was eine Ziffer ist, ist wie bei einem Alphabet, wo wir gesagt haben,
der Alphabet soll Symbole enthalten, soll was Vernünftiges sein.
Es wird nicht explizit von der Definition verlangt, was das sein soll.
Und natürlich für unsere Ziffern nehmen wir 0, 1 und 2 und so weiter.
Und wenn wir mehr Ziffern brauchen, dann nehmen wir Buchstaben, zum
Beispiel A, B, C, D, E, F oder so.
Ja, dann über diese Zahldarstellung ist dann so zu verstehen, dass ich
ein Wort mit diesen Ziffern aufschreibe und dann fange ich bei der
höchstwertigen Stelle bis zur niedrigstwertigen Stelle.
Und das leere Wort soll wieder eine Zahl darstellen.
Warum nicht?
Dann wird es ein bisschen komisch, wenn das Wort nicht mit seiner Zahl
zugenommen werden kann.
Und dann nehmen wir einfach die Zahl 0, das passt dann mit der
Definition.
Und wenn wir ein Wort da haben, mit zumindest einem Symbol, dann haben
wir einen Teil davor, das vielleicht das leere Wort oder nicht und
dann haben wir ein Symbol am Ende.
Und wie gesagt, wir nehmen dann das Symbol der niedrigstwertigen
Stelle.
Deswegen haben wir diesen kleinen K von X und wir machen dann induktiv
über diesen vorderen Teil dann mit K multipliziert, was die Basis ist.
Sky ist die Basis.
Bei den normalen, bei den ganz herkömmlichen Zahlen ist K dann gleich
10, das ist Basis 10 und in der Formatik ist K gleich 2 ganz beliebt,
eine binäre Darstellung.
Und es gibt auch den Rückweg, also ich habe ein Wort da und dann habe
ich eine Zahl herausgerechnet aus dem Wort, aber ich könnte auch eine
Zahl nehmen und die in einer gewissen Basis darstellen.
Deswegen haben wir diese Repräsentationabbildung da und wenn die Zahl
echt kleiner als die Basis ist, dann nehme ich einfach einen Ziffer
dafür.
Deswegen der kleine Rep.
Und wenn das groß ist, dann muss ich, da hinten schreibe ich, also ich
mache eine ganze Division, da habe ich einen Teil, wo das Ergebnis der
Division steht und da habe ich einen Restteil.
Und diesen Restteil nehmen wir für ein Modul und diesen Restteil
schreiben wir als Ziffer dar und den vorderen Teil, da machen wir mit
dem, was aus der Division sich ergeben hat, dann machen wir da weiter
als Ziffer, als Ziffern repräsentieren.
Und das jetzt in einem Beispiel, also wenn ich zum Beispiel eine
binäre Darstellung von 30 haben will, dann muss ich diese ganzteilige
Division machen und 30 durch 2, das zahlt ohne Rest, deswegen kommt 15
bei diesem vorderen Teil und 0 dahinter.
Also ich schreibe Ziffer 0 da hinten und ich mache dann vorne weiter
mit der Division, dann kommt 15 durch 2 und das ergibt dann 7 und Rest
1.
Und deswegen schreibe ich da hinten dann diese Ziffer 1 und nehme
davor diese Ziffer 0 und dann mache ich weiter da vorne mit dem 7 und
das ergibt dann 3 und Rest 1 und so mache ich es weiter, bis ich eine
Darstellung für die Zahl 30 habe.
Und so wie wir uns diese Repräsentationsfunktion definiert haben,
können keine führenden Nullen da rauskommen.
Spätestens da, da haben wir zum Beispiel eine Darstellung von 1
darstellen, dann nehmen wir einfach die Ziffer und das kann nie 0
sein.
Dann müsste bei der Division auch ein 0 rauskommen, das könnte nicht
sein.
Und bei der Numm-Funktion, da ist es nicht ausgeschlossen, dass
führende Nullen da sind.
Also da könnte ich durchaus, vielleicht das W ist nur 0, dann habe ich
Darstellung von diesen Nullen ist 0, dann passt das.
Dann madere ich 0 und es bleibt so.
Aber man kann nicht unbedingt hin und her gehen, weil diese führenden
Nullen nicht eindeutig sind.
Nochmal zu diesem hin und her gehen in die Geschichte.
Also ich habe zwei Welten.
Ich habe Darstellungen, also Wörter von Ziffern auf der einen Seite
und ich habe Zahlen auf der anderen Seite.
Und die Zahlen können als Wörter dargestellt werden, aber das sind
keine Wörter.
Also die Zahl ist etwas ganz abstrakt und ich kann eine Darstellung,
mittels einer Darstellung kann ich diese Zahl dann ausdrucken.
Also diese Repräsentation kodiert, ist eine Kodierung für diese Zahl,
weil es ein abstraktes Konstrukt ist.
Aber die Ziffern selber sind keine Zahlen, sie sind nur Zeichen.
Die Zahl ist etwas abstraktes, ich kann es ausdrucken durch Ziffern,
aber die Zahl ist keine Ziffer.
Und diese Mantik von, das ist eine Syntaxzahl, ich habe diese Wörter
von Ziffern, damit ist etwas ausgedruckt.
Und diese Mantik, was das bedeutet, das gibt mir diese Nummerbildung
und das hängt immer von der Basis ab.
Also ich kann eine Zahl, zum Beispiel hier diese 4 mal 1 und 0 am
Ende, das kann eine in Basis 2, das steht für die 30 da.
Aber wenn ich das in Basis 10 interpretiere, dann kommt natürlich 11
.110 daraus.
Also das hängt immer von der Basis ab.
Und die Basis gibt mir diese Bedeutung von der Zahl, von der ich
kodiert habe.
Und das ist ähnlich wie bei der Aussagenlogik.
Also ich habe Formen mit Zeichen auf der einen Seite und ich habe
Wahrheitswerte, die von einer Interpretation abhängen.
Und diese Interpretation ist wie die Basis, die sagt mir, wie ich die
Formel dann auswerten soll.
Die Formel selber ist etwas Statisches, die hat keine Bedeutung.
Wie die Wörter über die Ziffern.
Und dann diese dummen Rep-Funktionen, die Brillen rücken zwischen
diesen zwei Feldern von Zahlen und Darstellung in einer gewissen
Basis.
Und wie gesagt, die Wahl von der Basis ist nicht eindeutig.
Ich kann mehrere Basen nehmen.
Und dann gibt es andere Repräsentationen, wie bei dem Beispiel 11.110
oder 30, das kommt darauf an.
Und es gibt mehrere Repräsentationen über diese Basis, aber die haben
die gleiche Bedeutung, die gleiche Zahl wird da ausgedrückt.
Und es gibt auch Abbildungen, die zwischen diesen Repräsentationen
übersetzen.
Und die haben wir eben gleich vorhin in der Vorlesung kennengelernt.
Da habe ich noch ein paar Folgen, ein bisschen technischer.
Zum Beispiel, ich nehme hier eine Basis B, beliebig.
Und wenn ich die Ziffer für das B-1 nehme und das N mal aufschreibe,
nacheinander, dann stellt das, die Bedeutung davon ist die Zahl B hoch
N minus 1.
Es ist nicht das B minus 1 als Zahl hoch N in dem Mittenteil von dem
Nullnumm, sondern die Ziffer davon, das ist als Wort zu verstehen.
Zum Beispiel, wenn ich über Basis 10 habe, da habe ich 10 minus 1, das
ist die 9.
Und wenn ich die Zahl 9 N mal nacheinander schreibe, dann ist das die
Zahl 10 hoch N minus 1.
Zum Beispiel, wenn N gleich 0 ist, dann habe ich das leere Wort da
stehen, dann habe ich 10 hoch 0 ist 1, minus 1 ist 0, das passt.
Und wenn ich nur eine 9 da habe, dann ist das 10 minus 1.
Wenn ich zwei 9 habe, dann ist das 100 minus 1.
Und so weiter.
Und man kann auch beweisen, dass das so ist, für beliebige Basis.
Und hier machen wir einfach eine Induktion über diese Länge dieses
Wortes.
Und beim Induktionsanfang, da haben wir das leere Wort da stehen, also
N ist gleich 0, dann kommt eine Ziffer hoch 0, das Wort hoch 0 ist
Epsilon.
Und Epsilon steht für die 0 und B hoch 0 muss 1 sein.
Und 1 minus 1 ist 0.
Und die B ist nicht 0.
0 hoch 0 ist nicht erlaubt, aber in dem Fall ist B zumindest 2.
Und bei dem Induktionsschritt, dann nehme ich ein beliebiges N und
dann soll die Behauptung gelten.
Und dann mache ich mir Gedanken über den N plus 1 Fall.
Im N plus 1, da habe ich N plus 1 Ziffer da stehen.
Also ich kann den vorderen N-Teil nehmen und dann Induktiv in diese
Definition reinschreiben.
Also habe ich B, dann mal die Zahl, die davon rauskommt, plus die
Ziffer am Ende.
Und die Ziffer am Ende ist B minus 1.
Und dann finde ich meine Induktionsvoraussetzung für den Wert, dieser
N großen Teil.
Und dann ist das B hoch N minus 1 und dann plus ein B minus 1 am Ende.
Und dann kommt raus, was rauskommen sollte.
Und das passt.
Dann kann ich das für beliebige Basen einsetzen.
Also wenn ich auch ein Basis 2 könnte es nötig sein, wenn ich viele
Einsen da habe.
Dann möchte ich noch als letztes Thema die zwei Themen hier verbinden.
Also ich habe Zahlendarstellung und ich habe formale Sprachen.
Und ich könnte auch Darstellung von Zahlen als eine formale Sprache
zusammenfassen.
Also zum Beispiel könnte ich mir anschauen, die Binärdarstellungen,
die für eine gerade Zahl stehen.
Und wenn ich das formal beschreiben will, welche Wörter das erfüllen,
dann...
Ja, was könnte das sein?
Ich muss eine Null am Ende haben.
Bei dieser Null-Operation, das passt zusammen.
Also zum Beispiel...
Sprechen wir zuerst über die genaue Darstellung.
Ich habe Null meist da vorne und am Ende soll eine Null sein.
Oder es könnte auch das leere Wort sein, das ist nicht ausgeschlossen.
Das leere Wort macht hier manchmal immer Probleme, man muss es immer
im hinteren Kopf behalten.
Und wenn ich ein Wort aus dieser Sprache nehme, warum muss das gerade
sein?
Wenn das das leere Wort ist, dann muss das Null sein.
Das ist gerade, das bleibt so, ist kein Problem.
Wenn das nicht leer ist, dann kann ich es so schreiben als ein
beliebiges Wort über Null 1.
Vielleicht leer.
Und dann kommt eine Ziffer Null.
Und wenn ich das in diese Null-Funktion reinpacke, dann kommen
zweimal, was da vorne repräsentiert ist, plus diese Ziffer am Ende.
Und das ist dann zweimal, was da vorne repräsentiert ist und zweimal
irgendwas muss immer gerade sein.
Umgekehrt, ich zeige, dass alle Wörter in L sind, indem ich zeige,
dass wenn ein Wort nicht in L ist, muss es ungerade sein.
Also wenn ich ein Wort habe, das nicht so aussieht, dann kann es weder
das leere Wort sein, noch kann es ein Null am Ende haben.
Also es gibt nur die Möglichkeit, die hat ein 1 am Ende und da vorne
steht was beliebiges.
Und die kann ich dann wie vorher so aufschreiben, als beliebiges Wort
und am Ende eine Ziffer 1.
Und wenn ich das wieder in die Null reinstecke, dann kommt was
ungerade raus.
Also da kommen zweimal die Darstellungen da vorne, zweimal der Wert
der Darstellung da vorne plus die 1, die dahinter steht, das muss
ungerade sein.
Zweimal irgendwas plus 1 muss ungerade sein.
So kann man diese Sprache darstellen.
Ein zweites Beispiel, wir machen den Rückweg.
Vorher hatte ich eine Eigenschaft und wollte das durch eine Sprache
ausdrucken und jetzt habe ich eine Sprache und ich frage mich, was das
sein könnte.
Also da habe ich eine 1 da vorne und dann beliebe ich viele Nullen.
Es könnte auch gar keine Nullen sein.
Bei Basis 10 ist das einfach 1, 10 und 100 und so weiter, das sind die
Potenzen von 10.
Und in Basis 2 sind das die Potenzen von 2.
Und ich muss mir Gedanken machen, die Fortlänge.
Wenn ich 2 hoch die Fortlänge habe, dann kommt was zweimal zu groß.
Ich muss deswegen 2 hoch Fortlänge minus 1 nehmen.
Dann beweise ich wieder durch Induktion, dass das passt.
Also wenn die Fortlänge 1 ist, dann gibt es nur ein Wort in L, das das
erfüllt.
Das ist das Wort mit der Ziffer 1.
Und 2 hoch 1 minus 1 ist 2 hoch 0, das ist 1, also deswegen passt das.
Und für den Induktionsschritt, da nehme ich ein beliebiges Wort in der
Sprache und bei der Voraussetzung, da setze ich voraus, dass jedes
Fort dieser gleichen Länge dann auch diese Eigenschaft erfüllt.
Also ich nehme ein beliebiges Wort und dann betrachte ich alle Förter,
die diese Länge haben können.
Das ist dann Induktion über die Länge des Fortes.
Also für Induktion brauche ich immer eine Zahl, eine natürliche Zahl,
also in dem Fall nehme ich die Länge des Fortes.
Ich kann nicht Induktion über die Förter machen.
Man könnte es machen mit einigen Techniken, aber das ist in der Regel
zu umständlich und das bringt mir meistens nichts.
Und dann habe ich diese Voraussetzung da und dann nehme ich ein
beliebiges Wort als L und die soll um ein Zeichen größer sein.
Dann könnte das aussehen, das hat eine 1 davor gezwungen und dann hat
das natürlich beliebig viele Nullen.
Es kann nur so viele Nullen haben, sodass das mit der Länge
zusammenpasst.
Dann muss die Länge von diesem W viele Nullen sein und wenn ich das in
die Nullenfunktion reinstecke, dann geht alles gut.
Dann habe ich zweimal zwei Hochlänge des Ws, minus eins und dann passt
das mit meiner Behauptung zusammen.
Dann bin ich fertig und bedanke mich für eure Aufmerksamkeit und
wünsche euch noch ein schönes Wochenende.