Einen wunderschönen guten Morgen.
Wir hatten letztes Mal aufgehört an einem Punkt, wo wir uns anschauen
wollten, was denn diese O-Abschätzungen oder wenn Algorithmen in
bestimmten Laufzeiten laufen, was das denn bedeutet überhaupt
tatsächlich in echter Lebenszeit.
Auch manchmal einfach Wall-Clock-Time genannt.
Also wie sieht das aus, wenn der Algorithmus jetzt in Lock-In
-Schritten läuft?
Und dann kann man sich überlegen, was ist so eine typische
Größenordnung für so einen Schritt?
Wie lange braucht der ungefähr?
Irgendwelche Vorschläge, wie lange so ein Schritt ungefähr braucht?
Wie viel Zeit?
Was ist da so Größenordnung?
Wir brauchen es jetzt nicht so ganz genau.
Ist das eine Millisekunde, Mikrosekunde, Femtosekunde?
Lauter.
Also wir haben mal mit einer Nanosekunde gerechnet.
Das ist eindeutig das Speakers-Corner.
Ah, hier hat einer das auseinandergenommen.
Ungünstig.
Was haben wir denn hier?
Das ist Out.
Das ist ja doof.
Also können wir uns auf eine Nanosekunde einigen?
Was ist so heutige Taktrate Prozessoren?
Das ist so ungefähr immer noch das gleiche, wie es auch vor Ewigkeiten
schon war.
Also wir haben gerechnet mit einer Nanosekunde pro Rechenschritt.
Das ist so eine vernünftige Größenordnung.
Das Interessante ist, wir werden gleich sehen, ob das jetzt eine
Sanosekunde ist oder vielleicht 0,1 Nanosekunden.
Das macht am Ende gar nicht mehr so einen großen Unterschied.
Wir haben jetzt hier eine große Tabelle.
In der linken Spalte sind die Laufzeiten.
Jetzt nicht im O-Kalkül, sondern jetzt das sei die tatsächliche echte
Laufzeit.
So viele Schritte soll das brauchen, bei einer Eingabe der Größe n.
Dann fangen wir an mit so etwas wie logarithmischem, zur Basis 2, dann
Wurzel, so etwas wie linear.
Dann diese n mal log n, also linear mit einem Logfaktor davor.
Dann so ein paar polynomielle Sachen, n²n hoch 3.
Und dann gehen wir rein in die exponentiellen Sachen.
So etwas, das ein bisschen größer ist als 1 hoch n, 1,01 hoch n, dann
1,1 hoch n.
Und danach mit mal echt n²n und dann so etwas ganz Böses wie n hoch n.
Wenn man das jetzt mal ausrechnet für so in Zehnerschritten,
Zehnerpotenzen für die Eingaben, dann sieht man so etwas wie einen
Logarithmus.
Wenn ich Eingabenlänge 10 habe, bin ich so bei Größenordnung 3
Nanosekunden.
Und dann wächst das relativ gutmütig an, obwohl ich halt um
Zehnerpotenzen die Eingabe größer mache.
Wächst logischerweise die Zeit nur logarithmisch, sodass ich bei einer
Eingabe von 10 hoch 6 auch erst so etwas wie 20 Nanosekunden brauche.
Wurzel wächst halt schon deutlich schneller als der Logarithmus.
Am Anfang haben wir auch so etwas wie 3 Nanosekunden.
Und dann in den Zehnerpotenzen wächst das zwar nicht linear, aber
schon deutlich schneller als der Logarithmus.
Sodass ich dann bei so einer Eingabe wie 10 hoch 6 bin ich schon bei
so etwas wie einer Mikrosekunde.
Linear ist klar, wächst halt logischerweise in den Zehnerpotenzen,
also aus 10 Nanosekunden werden bis zur Eingabe 10 hoch 6 insgesamt
eine Millisekunde.
Wenn ich das Ganze dann halt mit einem Logarithmus noch multipliziere,
dann habe ich halt überlineares Wachstum.
Und dann sieht man schon, dass man am Anfang halt von 33 Nanosekunden
dann ganz am Ende plötzlich bei 20 Millisekunden ist.
Wenn man das also vergleicht mit dem rein logarithmischen Wachstum,
sieht man da schon Größenordnungen, zwei Größenordnungen letztendlich
über dem logarithmischen Wachstum.
Und dann bei Polynomial, da wird es halt schon deutlich unangenehmer.
Also bei n² fange ich noch an mit 100 Nanosekunden und dann bei so
einer Eingabe von 10 hoch 6 bin ich schon bei so etwas wie einer
halben Stunde.
Und eine Eingabe von 10 hoch 6 ist jetzt gar nicht so übermäßig groß.
Das ist jetzt vielleicht nicht die Anzahl der Studierenden am KIT,
aber wenn ich mir sowas angucke wie Anzahl Weltbevölkerung, bin ich da
schon recht gut dabei, wenn ich anfange sowas zu machen wie
Raytracing, wo ich halt Pixel berechnen muss.
Angenommen ich berechne einen Film, entweder Spezialeffekte oder halt
den Nachfolger vom Zeichentrick, also irgendwelche computeranimierten
Filme, dann bin ich problemlos da in der Größenordnung schon bei
relativ kurzen Filmen, sodass ich da jetzt schon signifikant warten
muss.
Ob ich jetzt 20 Nanosekunden warte oder eine Mikrosekunde bei etwas
Größerem, das merke ich als Mensch nicht.
Das ist mir egal.
Ob ich jetzt eine Mikrosekunde warten muss oder eine halbe Stunde, das
macht schon Unterschied.
Und das ist, n² ist ein kleines Polynom.
Bei n³, bei n hoch 3, wird es schon deutlich schlimmer.
Da fange ich an bei einer Mikrosekunde und bin dann hinterher bei
Eingaben von 10 hoch 6 schon im Bereich von einer
Wissenschaftlerkarriere, fast bei über 30 Jahren.
Das ist der Bereich, das ist so in Blöcke gefasst.
Sie sehen schon, Sie haben da oben so den unterlinearen Block, dann
hier den Polynomblock, n hoch 1 halt auch als Polynom, als
polynomielles Wachstum.
Man sieht, dass da so Größenordnungen Unterschiede sind und dann kommt
als letzter Block dieses exponentielle Wachstum, also relativ sanftes
exponentielles Wachstum, 1,01 hoch n.
Da fange ich am Anfang an auch mit einer Nanosekunde.
Das geht also noch sehr, sehr, sehr schnell.
Wenn ich dann anfange, zu 10 hoch 2 zu gehen, zu 10 hoch 3, dann bin
ich schon im Bereich Mikrosekunden.
Wenn ich halt diesen Faktor von 1,01 auf 1,1 gehe, dann wird
dementsprechend aus der einen Nanosekunde plötzlich schon mal sowas
wie 2,5 Nanosekunden.
Da, wo ich vorher Nanosekunden hatte, hatte ich plötzlich
Mikrosekunden.
Und so sieht man halt, geht das halt immer weiter.
Wenn ich jetzt unten den Faktor, den ich exponentiere, erhöhe, 2 hoch
n, bin ich bei 1,02 Mikrosekunden schon bei der kleinsten Ausgabe und
bei n hoch n bin ich schon bei 10 Sekunden.
Jetzt ist es natürlich wieder geschlampft worden bei dieser Tabelle.
Die ist leider unvollständig.
Da fehlen ein paar Werte.
Das ist doof.
Ich habe es heute Morgen erst zu spät gesehen.
Damit wir mal ein Gefühl dafür bekommen, gucken wir uns das mal an.
Wer hat einen Taschenrechner dabei?
Dann kann ich das gleich für nächstes Jahr, dass wir das vollständig
haben, nehme ich mal einen Taschenrechner her.
Gucken wir uns das mal an.
Also wir fangen an, das war 1,01 hoch n.
Für 10 hoch 4 war eine Lücke.
Das kann ja jetzt nicht so schwierig sein.
Also 1,01 wollten wir hoch 10 hoch 4 machen.
Gut, machen wir das.
Hoch 10, hoch 4.
Und das gibt uns das Ganze dementsprechend in Nanosekunden.
Da kriegen wir halt eine relativ große Zahl.
Da sind wir bei 1,6 Nanosekunden.
Was sagt uns das?
Wie lang ist das jetzt?
Ich habe jetzt nicht so ein Gefühl dafür, was Nanosekunden sind.
Wer weiß schnell, wie viele Nanosekunden im Jahr?
Allgemeinwissen, also sagen wir mal so was wie 3,1 mal 10 hoch 16
Nanosekunden im Jahr.
Das ist so ungefähr die Größenordnung, mit der wir rechnen müssen.
Das sind Schaltjahre und sowas, das ist jetzt egal.
Also 3,1 und sagen wir mal so schön mal 10 hoch 16.
Sind wir also bei 5,2 mal 10 hoch 26 Jahre.
Teilen wir es noch durch tausend.
Dann sind wir bei so was wie 5,2 mal 10 hoch 23 Jahrtausende.
Das heißt also, das fiese dabei ist, das wird ganz, ganz schnell,
ganz, ganz überraschend plötzlich sehr, sehr groß.
Das ist wichtig, das müssen Sie sich dafür merken.
Damit Sie, wenn Sie beim Programmierwettbewerb da sind, die überhaupt
noch ein Programm schreiben, das überhaupt während des
Programmierwettbewerbs durchläuft am Ende.
Das heißt also, da wo wir Mikrosekunden haben, wenn ich da um Faktor
10 meine Eingabe vergrößere.
Ich bin jetzt kein Geologe, wir haben Geologen hier, Geodäten,
Geologen, Geodäten, Geodäsie.
Wie alt ist die Welt?
Wie viele Jahre?
Haben wir so sechs Milliarden oder was war das so groß?
Vier Milliarden?
Vier Milliarden.
Vier Milliarden, das sind deutlich weniger als die Zahl, die hier
steht.
Also mit anderen Worten, wenn Sie ganz am Anfang, am Urknall, wenn Sie
am Entstehen der Welt angefangen hätten...
Nee, die Erde ist nicht vier Milliarden, ja, das Universum ist vier
Milliarden, oder?
Nein, Erde ist vier Milliarden, was ist Universum?
13?
12, 13 Milliarden?
Das heißt also, nichtsdestotrotz, wenn Sie am Urknall angefangen
hätten zu rechnen, wären Sie heute noch nicht fertig.
Also, mit anderen Worten, exponentielles Wachstum ist extrem böse.
Irgendwas, was in exponentiellem Wachstum wächst, sollte man, wenn es
auch nur irgendwie geht, vermeiden.
Wenn man irgendwie mit Eingaben rechnen will, die halbwegs vernünftige
Größe haben.
Und wenn Sie dann hinterher jetzt in theoretische Grundlagen der
Informatik oder auch in Softwaretechnik sich so bestimmte Algorithmen
anschauen, dann werden Sie leider feststellen, dass man zwei Klassen
von Algorithmen unterscheidet.
Einmal die Klasse der Algorithmen, die in polynomieller Laufzeit
laufen, und das ist die Klasse der Algorithmen, die in nicht
-polynomieller Laufzeit laufen.
Und dieses nicht-polynomielle Laufzeit heißt nicht, dass sie in den
oberen Block reinfallen.
Das heißt, dass sie also langsamer sind als polynomiell.
Und mit anderen Worten, Probleme, die in exponentieller Laufzeit
laufen, sind für an sich interessante Problemgrößen gar nicht
berechenbar in vernünftiger endlicher Zeit.
Und das sind durchaus interessante Sachen.
Das kann also sowas sein wie Travelling-Salesman-Problemen.
Auch schon mal gesprochen, wenn ich also gucke, ich habe eine Stadt
und da will ich jetzt eine Karte mit ganz vielen Städten und ich will
so einen Rundweg finden, dass ich jede Stadt höchstens einmal besuche,
dann gibt es noch keinen Algorithmus, der das in polynomieller
Laufzeit löst.
Das heißt also, wenn ich schon sowas wie 1004 Städte habe, habe ich
ein Problem.
Und das ist jetzt keine unrealistisch große Zahl.
Und je mehr man jetzt reingeht mit 1,1 hoch n, kann man auch
ausrechnen, kommt ungefähr das gleiche raus.
Wenn Sie das in n hoch n reinstecken, explodiert innerhalb der
Taschenrechner.
Also Quintessenz, exponentielles Wachstum böse, vermeiden.
Leider lässt es sich nicht immer vermeiden und die große Frage ist
immer noch, ob es irgendwelche Tricks gibt, diese Probleme, von denen
man noch keinen nicht-polynomiellen Laufzeitalgorythmus kennt, und man
die irgendwie umwandeln kann in polynomielle Laufzeit.
Das als letzte Bemerkung zu dieser Absetzung der Rechenzeiten.
Man kann sich das auch mal schön hinmalen.
Das ist einfach mal linear eine E-Funktion hingeschrieben.
1,1 hoch x und x² als eine einfache polynomielle Funktion.
Und da sieht man diese Exponentielle, die fängt so harmlos an, aber
die düst ganz, ganz, ganz schnell ab.
Die geht ganz, ganz schnell plötzlich durch die Decke.
Und auch die dann mit der E-Funktion, wenn ich damit anfange, dann bin
ich ganz ruckzuck außerhalb meiner Skala, dass ich das irgendwie noch
in vernünftige Worte fassen kann.
Das Ganze auf einer logarithmischen Skala aufgetragen.
Unten die Rechenzeit, oben die Problemgröße.
Dann sieht man, wenn man halt so eine logarithmische Skala hat, dass
dann die polynomiellen Funktionen irgendwie linear in dieser
logarithmischen Skala sind.
Aber die exponentielle Funktion verlässt ganz schnell die
exponentielle Skala auch.
Okay, also was Sie mitnehmen sollten, wir hatten letztes Mal über das
Mastertheorem gesprochen, als so ein Kochrezept, um
Laufzeitabschätzungen zu machen, wenn Sie so einen divide-and-conquer
-Algorithmus anfangen.
Sie sollten gucken, dass Sie auch ein Gefühl dafür bekommen, wie Sie
Laufzeiten in diesem O-Kalkül, Theta-Kalkül, Omega-Kalkül abschätzen
können.
Sie sollten sich Schleifen anschauen können und da die Laufzeit
abschätzen können, durch einfaches Draufschauen oder, wenn Sie das
wollen, auch im Mastertheorem.
Und ansonsten haben Sie halt diese Komplexitätsmaße.
Sie wissen, es gibt die Laufzeit, es gibt den Speicherplatz.
Sie haben so ein bisschen Beispiele auch gesehen, wo man tauschen
kann.
Laufzeit gegen Speicherplatz, wo ich also Sachen schneller machen
kann, indem ich mehr Speicher verwende.
Das stößt natürlich auch irgendwann an die Grenzen, wenn man halt über
den Speicherplatz hinausläuft.
Also Laufzeit ist nicht alles.
Wir kennen diese Abschätzungen, die alles abschätzen bis auf einen
konstanten Faktor.
Den konstanten Faktor wollen wir halt nicht, weil wir uns loslösen
wollen von der Hardware.
Wir wollen lieber so Problemklassen haben von Algorithmen, die
ungefähr, wenn ich die Eingabe nur groß genug mache, in der gleichen
Laufzeit laufen.
Und das können Sie mitnehmen jetzt aus dem Kapitel Komplexitätsmaße.
Damit kommen wir zum nächsten Kapitel, das Kapitel der endlichen
Automaten.
Endliche Automaten kann man so ein bisschen reinwerfen in das Kapitel
auch Grafentheorie.
Warum?
Weil wir so endliche Automaten schön als Grafen darstellen können.
Und die Idee bei endlichen Automaten ist, dass wir Prozesse
modellieren können, wo wir irgendwie eine Maschine haben.
Mit dieser Maschine interagieren wir.
Wir geben der irgendwelche Eingaben und die Maschine wechselt dann
intern irgendwie einen Zustand und macht irgendwelche Ausgaben,
basierend auf dem, was wir so eingegeben haben.
Ganz simples Beispiel, ein ganz simpler, primitiver, also wirklich
primitiver Getränkeautomat.
Das ist jetzt nicht so ein schickes Ding wie draußen steht, wo so ein
Schlitten durch die Gegend fährt und erstmal großes Gedöns macht, bis
die Flasche rauskommt.
Das hier ist ein Getränkeautomat aus dem Kindergarten.
Da kann man einmal Mineralwasser kaufen und einmal Zitronensprudel.
Das Mineralwasser nennen wir R wie reines Wasser.
R ist halt einfacher hinterher darzustellen als ein M, könnte ja auch
Münze heißen.
Dann gibt es Zitronensprudel.
Kann oben Geld reinwerfen, glücklicherweise einfaches Preisprinzip.
Alles kostet einen Euro.
Ich kann auch immer nur eine Flasche gleichzeitig ziehen.
Das heißt also, ich kann einen Euro reinwerfen, dann kann ich mir
auswählen, ob ich Sprudel oder Zitrone will.
Und wenn ich das ausgewählt habe, wenn ich auf OK drücke, dann soll
unten die Flasche rauskommen.
Und wenn ich auf Cancel drücke, auf C, dann soll einfach wieder das
Geld zurückkommen.
Das ist so ein ganz einfacher, billiger, primitiver Getränkeautomat
als Beispiel.
Wenn man sowas jetzt realisieren will, das kann man natürlich
mechanisch machen, aber heutzutage läuft alles mit Software.
Dann müssten wir dafür jetzt ein kleines Programm schreiben, das in
dem Getränkeautomat läuft.
Und das dafür sorgt, dass der Getränkeautomat in Abhängigkeit davon,
was der Benutzer vorher gemacht hat, auch bitte schön das Richtige
macht.
Es muss also schon mal Geld eingeworfen sein, muss also ein Euro drin
sein.
Dann muss man gucken, wurde ein Getränk gewählt?
Wenn ja, muss ich mir das merken.
Und dann ganz zum Schluss, wenn auf OK gedrückt wird, dann muss ich
halt gucken, es sollte Geld drin sein, es sollte ein Getränk gewählt
sein.
Wenn das der Fall ist, dann wird halt das richtige Getränk ausgewählt.
Wenn der halt ein Getränk auswählt und OK drückt, aber noch kein Geld
eingeworfen hat, dann soll gefälligst kein Getränk rauskommen.
Und wenn der Geld reingeworfen hat und ich auf Cancel drücke, egal ob
er schon ein Getränk ausgewählt hat oder nicht, dann soll halt das
Geld wieder zurückkommen.
Aber wenn der Cancel drückt und noch kein Geld reingeworfen hat, dann
soll bitte schön auch kein Geld wieder rauskommen.
Das wäre sonst ein schöner Automat.
Das Ganze will man jetzt irgendwie in ein Programm gießen und damit
das auch vernünftig hinterher verifizierbar ist, ob es das tut oder
nicht, kann man das schön formalisieren.
Ich habe also immer so ein paar XY.
Das X soll mir sagen, ob schon Geld drinsteckt oder nicht.
Also ist nun Euro drin oder ist 0 Euro drin.
Das Ganze mit Geld wechseln und mehr und Geldspeicher, das vergessen
wir in diesem einfachen Modell.
Da ist entweder ein Euro reingesteckt worden oder nicht.
Und dann brauchen wir auch irgendwie ein Speicher dafür, ob eine
Getränkewahl stattgefunden hat.
Wird entweder kein Getränk bisher ausgewählt, das soll der Minus sein.
Es wird entweder reines Mineralwasser ausgewählt, das soll das R sein.
Oder es wurde Zitronensprudel ausgewählt, das soll das Z sein.
Und das sind die beiden Dinge, die ich mir merken muss.
Und ich muss mir jede mögliche Kombination ausgeben.
Geld ist schon drin oder Geld ist noch nicht drin und es wurde noch
nichts ausgewählt oder es wurde schon einer von beiden ausgewählt.
Jede dieser möglichen Kombinationen muss ich irgendwie abspeichern und
für jede dieser möglichen Kombinationen brauche ich dann hinterher
eine Antwort, wenn eine der Tasten gedrückt wird.
Und deswegen kann man sagen, der Automat ist immer in einem dieser
Zustände, die aus dem kathesischen Produkt von wie viel Geld steckt
drin und ob und welches Getränk wurde ausgewählt.
In einem dieser Zustände ist dieser Automat und dann in Abhängigkeit
davon, in welchem dieser Zustände ich bin, habe ich unterschiedliches
Verhalten in Bezug darauf, welche Taste gedrückt wird.
Wenn dann also so eine Taste gedrückt wird, dann gibt es
Zustandsänderungen.
Zum Beispiel, wenn ich halt Sprudel auswähle, dann gehe ich halt in
den Zustand über, wo halt von wurde noch nichts ausgewählt nach
Sprudel.
Wenn ich meine Meinung ändere, ich hatte Sprudel ausgewählt und will
Zitronensprudel haben, dann geht er halt über in den Zustand, der
wieder den gleichen Eigenschaft hat, was das Geld angeht, hin in
diesen Zustand, der jetzt dann stattdessen Sprudel ist.
Wenn ich Getränk ausgewählt habe, es steckt Geld drin und ich drücke
auf OK, dann kommt halt die entsprechende Sprudelflasche raus und
danach habe ich auch eine Zustandsänderung, weil das Geld, das er
reingesteckt hatte, soll dann ja bitteschön verbraucht worden sein.
Er soll ja nicht, wenn er das nächste Mal wieder OK drückt, nochmal
eine Flasche bekommen, sondern er soll halt für jeden Euro, den er
reinsteckt, nur eine Flasche bekommen.
Und bei Cancel muss ich mir halt auch entsprechend überlegen, dass
dann, wenn Geld drin ist, das rausgespuckt wird und ich muss mir ein
Verhalten überlegen, was die Auswahl des Sprudels angeht, der
Sprudelsorte.
Was kann man da machen?
Naja, man kann entweder sagen, wenn er Cancel drückt, dann wird
ebenfalls Geld rausgespuckt und ich lösche mir, was ich gemerkt hatte
in Bezug auf Sprudelauswahl oder man könnte sagen, es wird halt Geld
ausgespuckt, aber ich behalte das, was an Sprudelauswahl vorher drin
war.
Das ist im Prinzip eine Designentscheidung.
Meistens wird man es wahrscheinlich so machen, dass man, wenn man C
drückt, sowohl die Sprudel als auch die Geldauswahl zurücksetzt.
Wenn man das Ganze jetzt formalisiert, hängt also so ein
Zustandsübergang genau ab von dem aktuellen Zustand, in dem ich mich
befinde und dem aktuellen Eingabesymbol.
Und sonst gar nichts.
Das ist doch offensichtlich.
Das ist etwas, das kann man später erweitern.
Zum Beispiel kann man hinterher zu solchen Modellen kommen, wo man
sagt, die Zustandsänderung hängt ab von der Eingabe, die ich mache,
dem aktuellen Zustand und zum Beispiel dem Zustand, den ich mich davor
befand.
Oder sie hängt ab von der aktuellen Eingabe, vom aktuellen Zustand,
vom Zustand, in dem ich mich vorher befand und in dem Zustand, in dem
ich mich davor befand.
Dass man jetzt sowas abhängig macht, nur von dem aktuellen Zustand und
gegebenenfalls noch der Eingabe, ist sowas wie erste Ordnung.
Wenn ich es abhängig mache von Zeitschritt davor und auch der Zustand
zusätzlich, habe ich zweite Ordnung und so weiter und so fort bis hin
zur Endordnung.
Und würde ich jetzt zum Beispiel auch noch die
Zustandsübergangsänderung nur abhängig machen vom aktuellen Zustand
und gar nicht mehr von der Eingabe, dann hätte ich die sogenannte
Markov -Annahme für solche endlichen Automaten.
Und für unsere Automaten, die wir betrachten, hängt es halt ab vom
aktuellen Zustand, vom Eingabesymbol und sonst gar nichts.
Und das Wichtige ist, die Zustandsübergangsänderung, die ich dann
machen werde, die ist eindeutig bestimmt.
Wenn so etwas eindeutig bestimmt ist, in jedem Fall eindeutig bestimmt
ist, dann nennt man das Ganze deterministisch.
Es ist also vorbestimmt, was als nächste Aktion, als nächster
Zustandsübergang ausgeführt wird.
Man kann das auch später machen, in anderen Semestern werden Sie
feststellen, kann man das zum Beispiel so machen, dass eine von zwei
Möglichkeiten zutrifft.
Das ist natürlich die Frage, ok, und welche von beiden Möglichkeiten
trifft zu?
Kann man über Wahrscheinlichkeit machen.
Kann man sagen, ok, der Zustand würfelt dann halt und in Abhängigkeit
davon, was er für eine Zahl wirft, nimmt er halt den einen oder den
anderen Übergang.
Oder man kann sich sowas Kompliziertes überlegen, dass er beides
macht.
Dass ich dann hinterher nicht mehr in einem Zustand bin, sondern dass
ich mich gleichzeitig in zwei Zuständen befinde.
Oder ich kann die Annahme machen, ich weiß nicht, was passiert.
Ich muss dann halt damit rechnen, dass ich vielleicht in dem einen
oder vielleicht in einem anderen Zustand bin und da muss ich irgendwie
mit rechnen und den ganzen Wahrscheinlichkeiten zu.
Wir sind im ersten Semester.
Unsere Automaten sind immer deterministisch, das heißt, wenn ich in
einem Zustand bin und ich bekomme eine Eingabe, weiß ich genau, was
als nächstes passiert.
Und dieses, was als nächstes passiert, das drückt man halt als eine
Funktion ein.
Die Funktion kriegt halt als Eingabe den aktuellen Zustand, die
aktuelle Eingabe und spuckt halt raus, in welchen neuen Zustand ich
übergehen soll.
Und häufig kann man solche Automaten, wenn sie halt relativ klein
sind, schön grafisch hinzeichnen als Grafen.
Das ist unser Getränkeautomat und das sind jetzt erstmal nur die
Zustandsübergänge unseres Getränkeautomaten.
Und da sind auch jetzt erstmal noch nicht alle Tasten abgemalt, damit
es nicht zu unübersichtlich wird.
Ich habe erstmal hier die Zustände, die halt aus diesem kathesischen
Produkt kommen, aller Möglichkeiten von Geld und Getränkeauswahl, die
getroffen wurden.
Das heißt, 0 noch nichts ausgewählt, 1 noch nichts ausgewählt, 0 und
Wasser, 1 und Wasser, 0 und Zitronensprudel, 1 und Zitronensprudel.
Mehr Zustände habe ich nicht.
Das ist das, was ich mir merken muss.
Und dann guckt man mal hier bei dieser Taste Zitronensprudel,
Mineralwasser und Geld eingeworfen oder nicht.
Was kann man da für Übergänge machen?
Wenn man so einen Automaten hat, muss man ja irgendwo anfangen.
Also man muss sich in einem Zustand befinden.
Erst wenn ich mich in einem Zustand befinde, weiß ich, in welchen
nächsten Zustand ich übergehe, wenn ich eine Eingabe mache.
Bei solchen Automaten, die man grafisch darstellt, legt man halt einen
Anfangszustand fest.
Also ganz am Anfang, wenn der Automat ins Leben gerufen wird,
festlegt, in welchem Zustand ich bin.
Und wenn ich das grafisch mache, dann mache ich das hier mit so einem
kleinen Pfeil.
Dann gibt es einen Zustand, der ist so ein Kreis, und dann gibt es so
einen kleinen Pfeil, der aus dem Nichts da rein zeigt.
Und das ist das Zeichen dafür, dass dies der Anfangszustand ist, wo
ich mich ganz am Anfang drin befinde.
Also ganz am Anfang gibt es noch kein Geld und es hat noch keiner eine
Taste gedrückt, die irgendwie Spudel auswählt.
Und wenn halt einer Geld reinsteckt, dann bin ich halt in einem
Zustand, wo halt Geld drin ist und noch kein Getränk ausgewählt.
Und wenn ich eine Getränkeauswahl treffe, dann ändert sich halt der
zweite Teil dieses Tuples, welches Getränk ausgewählt wurde.
Da muss man dann auch solche Sachen sich überlegen.
Was ist, wenn einer mehrmals Geld reinsteckt?
Beispiel hier.
Also ich stecke Geld rein, bin ich in einem Zustand, wo Geld drin ist.
Was ist, wenn ich jetzt nochmal Geld reinstecke?
Wir hatten gesagt, wir haben keinen Münzspeicher oder sowas, sondern
wenn ein Euro drin ist, ist ein Euro drin.
Und wenn halt einer nochmal ein Euro reinsteckt, dann fällt der halt
sozusagen durch und es ist nach wie vor ein Euro drin.
Das kann man mit so einer kleinen Selbstschleife machen.
Also wenn nochmal ein Euro reingesteckt wird, dann bleibt nach wie vor
weiterhin nur ein Euro drin.
Das Geld unten kullert dann sozusagen durch.
Genauso, wenn ich schonmal Mineralwasser ausgewählt habe und jetzt
drücke ich nochmal die Taste R, dann habe ich nach wie vor
Mineralwasser ausgewählt.
Ändert sich halt nichts.
Und wenn ich halt meine Meinung irgendwann ändere und ich hatte vorher
Mineralwasser ausgewählt und dann drücke ich Z, dann geht es halt zu
Sprudelwasser und dann wieder zurück.
Und das halt für alle Kombinationen.
Dann fehlen noch die Tasten Cancel und OK.
Das sieht dann so aus.
Wenn das also wieder alle meine Zustände sind, wenn ich in einem
Zustand bin, wo zum Beispiel ich noch kein Geld reingesteckt habe,
aber ich habe Sprudel ausgewählt oder Zitronensprudel ausgewählt, wenn
ich dann auf OK drücke, dann soll nichts passieren.
Dann ist immer noch kein Geld drin und ich habe immer noch Sprudel
ausgewählt.
Ich ignoriere einfach diesen Tastendruck.
Wenn ich aber Geld drin reingeworfen habe, ich habe irgendwas
ausgewählt und ich drücke OK, dann fliegt halt unten die
Sprudelflasche raus und das Geld ist weg.
Und ich bin wieder ganz am Anfang, wo ich angefangen habe.
Und hier jetzt die Designentscheidung, die Frage, was ist, wenn ich
was ausgewählt habe und ich drücke Cancel, dann erst mal das Geld
fliegt unten raus, dann ist 0 Euro im Speicher.
Was machen wir mit der Auswahl?
Hier wird die Getränkeauswahl auch gelöscht und das ist dann so, als
hätte ich überhaupt kein Getränk ausgewählt und ich bin wieder im
Anfangszustand, im jungfräulichen Zustand des Autos.
Und das ist dann hier die Eingaben, die ich machen kann und wie intern
sich der Zustand des Automaten ändert.
Oder halt alles zusammen sieht das Ganze halt so aus.
Man sieht schon für so einen kleinen Automaten, der relativ primitiv
ist, wird das schon relativ unübersichtlich.
Nichtsdestotrotz werden Sie dann hinter Designwerkzeuge und alles
mögliche kennenlernen, wo Sie genau solche Graphen werden zeichnen
können.
Und dann werden Sie das entweder komplett manuell spezifizieren
können, welche Zustandsübergänge gemacht werden sollen oder Sie werden
das semiautomatisch spezifizieren können.
Dann gibt es ein Werkzeug, da können Sie reinzoomen mit den Graphen
und sich nur Teilaspekte angucken und so weiter und so fort.
Und dann kommt am Ende so ein Automat raus.
Dieser Automat hat jetzt eine Unschönheit.
Der kann bisher nur Eingaben machen, der kann intern seinen Zustand
wechseln, aber das was ich gesagt hatte mit der spuckt unten Geld raus
oder der spuckt Sprudelflaschen raus, das ist bisher noch nicht hier
in dem Automaten abgebildet.
Wir brauchen also noch Ausgaben.
Wie gesagt, es gibt entweder Geld zurück oder es gibt eine Flasche
raus.
Und wenn man sich dieses Ausgabealphabet anschaut, dann gibt es
entweder den Euro zurück, es gibt das Mineralwasser oder den
Zitronensprudel.
Und dann muss man sich überlegen, wovon ist diese Ausgabe abhängig und
genauso wie die Zustandsübergänge, macht man das wieder abhängig von
dem aktuellen Zustand und dem aktuellen Eingabesymbol.
Das heißt, das was festliegt, was die Zustandsübergänge macht, das
legt auch fest, was die Ausgabe ist.
Wenn ich mir das jetzt im Automaten überlege in diesem Graphen, dann
kann ich das schön so machen, dass ich an diese Pfeile, an denen
bisher die Eingabesymbole liegen und die mir sagen, welche
Zustandsübergänge ich mache, da kann ich dann zusätzlich noch die
Ausgabe dran werfen.
Weil zu jeder Eingabe gehört ein entsprechender Zustandsübergang und
es gehört immer streng damit gekoppelt eine Ausgabe, sodass ich die
beiden mal an die gleichen Pfeile dran legen kann.
Das Ganze kann man jetzt wieder formalisieren als eine
Ausgabefunktion, die abbildet vom kathesischen Produkt von Zustand und
Eingabe in zur Ausgabe.
Und die Ausgabe hier kann jetzt halt zusammengesetzt sein aus den
Symbolen, die es im Ausgabealphabet gibt.
Das kann ein beliebiges Wort sein, das gebildet wird über diesem
Ausgabealphabet und kann im Allgemeinen auch das leere Wort sein,
Epsilon.
Es kann auch sein, ich mache keine Ausgabe, ist auch eine gültige
Ausgabe.
Oder ich bilde halt ein Wort über dieses Alphabet.
Und wie schon gesagt, unsere Automaten sind deterministisch.
Das heißt, die Ausgabe ist immer eindeutig festgelegt und ich weiß
immer genau, wenn ich hier Zustand habe und Eingabe, welche Ausgabe
als nächstes gemacht wird.
Das wird sich auch in späteren Semestern ändern.
Da kann man das dann halt auch so machen, dass man dann auswählen kann
zwischen Ausgabe 1 oder Ausgabe 2.
Oder ich kann sowohl Ausgabe 1 als auch Ausgabe 2 machen.
Oder ich muss halt irgendwie wieder würfeln.
Ich habe wieder irgendeine Wahrscheinlichkeitsverteilung, die sagt mir
dann, welche der möglichen Wörter ausgewählt wird, die ich auswählen
kann in diesem Zufall.
Wenn man das, wie gesagt, ins Diagramm einzeichnet, dann macht man das
so, dass man halt an die Pfeile sowohl die Eingabe schreibt, dann so
einen senkrechten Strich und dahinter das Ergebnis der Ausgabe, also
worauf diese Ausgabefunktion abbildet.
Das sieht dann in unserem kleinen, übersichtlichen Automaten
entsprechend so aus.
Wenn kein Geld drin steckt und irgendwas von OK gedrückt wird, dann
soll immer nichts passieren.
Wenn ich Geld drin habe und ich drücke Cancel, dann soll das Geld
wieder rausgespuckt werden.
Das heißt, dann kommt so eine 1 raus.
Wenn ich Geld drin habe und ich habe eine Sprudelsorte ausgewählt und
dann drücke ich OK, dann soll halt die entsprechende Sprudelsorte
rausfliegen.
Und wenn ich Cancel drücke, dann soll halt entsprechend das Geld
wieder rausfliegen.
Kann man mal schauen, wo haben wir sowas hier in diesem schönen
Übersicht.
Hier zum Beispiel, ich habe Geld drin und Zitronensprudel ausgewählt.
Wenn ich OK drücke, dann soll ich halt hier Zitronensprudel rausgeben
und wenn ich hier Cancel drücke an der Stelle, dann soll halt der Euro
wieder rauskommen.
Das heißt, an so einem Pfeil kann man auch zwei Paare aus Eingabe und
Ausgabe reinschreiben.
Das ist ungefähr so, als wenn ich zwei Pfeile schreiben würde.
Ich könnte da auch zwei Pfeile schreiben und der eine Pfeil kriegt
halt das OK und die Sprudelsorte raus und der andere kriegt halt
Cancel und den Euro raus.
Oder die beiden Pfeile lege ich halt zusammen.
Streng genommen sind das aber zwei unterschiedliche Eingabefunktionen
und zwei unterschiedliche Ausgabefunktionen.
Also hier haben wir so einen relativ einfachen endlichen Automaten,
der deterministisch ist.
Deterministisch, wissen Sie, bedeutet also Zustandeingabe legt
automatisch fest, welcher Zustandsübergang gemacht wird und welche
Ausgabe.
Was bedeutet endlich?
Man kann sich denken, warum so ein Automat endlich ist.
Was ist an dem Automaten endlich?
Genau, die Zustandsmenge und die Eingabemenge.
Wobei bei so einem Automaten er schon dann endlich ist, wenn die
Zustandsmenge endlich ist.
Also bei uns kommt es bei diesem Automaten darauf an, dass ich nur
eine endliche, begrenzte Anzahl an Zuständen habe, mit der ich
arbeiten kann.
Und jetzt unterscheiden wir zwei unterschiedliche Arten von Automaten.
Wir unterscheiden einmal die Mili-Automaten und die Mur-Automaten und
dann lernen wir einen besonderen Spezialfall kennen, den der endlichen
Akzeptoren.
Und spätestens bei den endlichen Akzeptoren sind wir wieder bei
unserem Lieblingsthema formale Sprachen und Grammatiken und wie wir
formale Sprachen verarbeiten können.
Und können dann sehen, wie man mit solchen Automaten auch schön
formale Sprachen abarbeiten kann.
Und ich bin mir sicher, das haben Sie alle schon vermisst.
Also, ein Mili-Automat kann man formal darstellen als so ein
Sechstupel.
Ich habe eine Menge von Zuständen.
Diese Menge muss endlich sein.
Deswegen heißt der Automat endlicher Automat.
Unter diesen Zuständen gibt es einen Anfangszustand.
Der kriegt halt im Diagramm so einen kleinen Pfeil, der aus dem Nichts
kommt und da rein zeigt.
Ich habe ein Eingabealphabet.
Und da mache ich nicht mehr die Erforderung, dass das endlich sein
muss.
Das Eingabealphabet kann unendlich sein.
Da muss man halt entsprechend überlegen, wie ich diese schönen
Funktionen schreiben kann, sodass ich hier sämtliche Kombinationen aus
Eingabe und Zustand und neuer Zustand hinschreiben kann.
Ich habe eine Funktion f, die überführt mir die Zustände vom
kathesischen Produkt z und x hin nach z.
Ich habe ein Ausgabealphabet und ich habe eine Ausgabefunktion, die
mir halt aus so einer Kombination aus Zustand und Eingabe ein Wort
über dem Ausgabealphabet zurückgibt.
Und das ist genau jetzt diese Darstellung, die Sie kennengelernt haben
als Graph.
Zustände sind Kreise.
Innen drin in den Zuständen kodiere ich irgendwie, wie der Zustand
aussieht.
Ich gebe was rein, das steht links vom Strich, ich gebe was aus, das
steht rechts vom Strich und ich lande in einem neuen Zustand, der mir
halt durch diese Funktion angegeben wird.
Das, was in diesem Zustand drinsteht, muss nicht unbedingt immer
explizit gemacht werden als diese Kombination aus diesem kathesischen
Produkt, die wir zum Beispiel aus diesen internen Zuständen haben.
Häufig macht man es so, dass man die Zustände einfach generisch
durchnummeriert von 0 bis n, ohne dass man da jetzt irgendwie so eine
komplexe Beschreibung hinschreibt, wofür denn dieser Zustand überhaupt
stehen soll.
Manchmal ist das auch gar nicht so ohne weiteres möglich.
Mit diesen Automaten kann man jetzt anfangen, ein paar Sachen zu
berechnen.
Die erste Sache, die man sich überlegen kann, ist, dass man sich
anschaut, wieso die Zustandsübergänge im Laufe der Zeit ablaufen.
Und da kann man sich zwei Fragestellungen machen.
Die erste Fragestellung ist, wenn ich so einen Automaten habe und ich
gebe so sukzessive eine Eingabe rein, eine Eingabesequenz, dann
durchläuft er seine Zustände.
Und wenn ich die Eingabesequenz abgearbeitet habe, in welchem Zustand
befinden wir uns am Ende?
Und die andere Frage ist, ich möchte nicht nur wissen, in welchem
Zustand wir uns am Ende befinden, wenn ich die Eingabe gemacht habe,
sondern mich interessiert die gesamte Sequenz von Zuständen, die ich
während der Eingabe durchlaufen habe.
Und das kann man wiederum formalisieren mit zwei Funktionen, f** und
f**, die halt beides berechnen sollen.
Und diese Funktionen kann man definieren wieder.
Die erste Möglichkeit, f** zu definieren, ist, dass ich halt abbilde
aus dem kathesischen Produkt aus Zuständen und diesmal einer Sequenz
von Eingaben.
Und so eine Sequenz von Eingaben ist nichts anderes als ein Wort über
den Alphabet der Eingaben X.
Und das bildet halt ab auf einen Zustand, nämlich den Zustand, den ich
ganz am Ende erreicht habe.
Und das kann man wieder sehr schön induktiv definieren.
Ich brauche einen Induktionsanfang und der sagt relativ einfach, naja,
wenn ich in einem Zustand bin und nichts mache, dann bleibe ich in dem
Zustand.
Also Eingabe, Alphabet, Eingabewort ist Y, das leere Wort, man bleibt
im Zustand.
Was ist, wenn ich in einem Zustand bin und ein echtes Wort eingebe,
bei dem ich hinten ein Zeichen X abtrennen kann?
Das Wort selber vorne, das Präfix des Wortes kann wieder Y sein, damit
komme ich dann wieder zurück auf meinen Induktionsanfang.
Ich zerhacke also meine Worte, mache die immer kleiner, indem ich das
letzte Zeichen abtrenne und mich zurückhange.
Naja, das ist schlicht und einfach der Zustand, in den ich gehe, wenn
ich von W komme und die Eingabe X mache.
Naja, das ist der Zustand, in dem ich war, wenn ich halt vom Zustand Z
anfange und die Eingabe W mache, ohne das letzte X.
Das berechnet mir gerade F-Sternchen, das durchläuft bis zum letzten
Zustand.
Und jetzt mache ich noch die Eingabe X und komme in meinen Endzustand
von WX.
Und das berechnet mir gerade die Übergangsfunktion, die Teil der
Definition des Automaten.
Also auf diese Art und Weise eine schöne, einfache, induktive
Definition dieser Funktion F-Sternchen, die mir angibt, welchen
Zustand ich erreiche, wenn ich eine Eingabe mache.
Das kann ich auch andersrum machen.
Und das andersrum ist, dass ich vorne anfange, Zeichen abzuhacken.
Also anstatt, dass ich immer das letzte Zeichen von meinem Wort
abhacke, fange ich an, das erste Zeichen abzuhacken.
Der Induktionsanfang ist wieder relativ einfach.
Ich befinde mich in einem Zustand.
Wenn ich nichts mache, bleibe ich in dem Zustand.
Was ist jetzt, wenn ich so etwas habe wie ZXW?
Vorne gibt es ein tatsächliches nichtsleeres Zeichen X, das ich von
meinem Wort W abhacken kann.
Was passiert dann?
Naja, das ist so, als wenn ich vom Zustand Z nach X übergehe.
Das ist der erste Schritt, dann bleibt noch das restliche Wort W
übrig.
Das heißt, von diesem Zustand, in dem ich gelandet bin, wenn ich von
ZX eingebe, muss ich jetzt noch bis ans Ende durchrechnen, was
passiert denn, wenn ich jetzt noch das restliche Wort W durchlaufe, in
welchem Zustand bleibe ich.
Und das ist gerade wieder F-Sternchen, mit diesem Querstrich darüber,
als alternative Definition.
Und das, was die beiden Funktionen berechnen, ist immer dasselbe.
Also die beiden Funktionen sind letztendlich äquivalent, wenn ich
einen beliebigen Zustand reingebe und ein beliebiges Wort.
Ganz wichtig hier, eine Bemerkung noch.
Bei dem Automaten hatten wir gesagt, wir haben den Anfangszustand und
wir gehen davon aus, wenn der Automat ins Leben gerufen wird, dann
befinden wir uns in diesem Anfangszustand und dann geht es los.
Bei dieser Berechnung dieser erweiterten Zustandsübergangsfunktionen
ist es mir egal, von welchem Zustand ich loslaufe.
Wenn ich also dieses F-Sternchen Z von W berechne, dann muss Z nicht
der Anfangszustand sein.
Das kann ein beliebiger Zustand sein.
Ich kann mir also einen beliebigen Zustand aus dem Automaten
raussuchen und mir dann die Frage stellen, wenn ich jetzt ein
bestimmtes Wort reingebe, wo komme ich am Ende raus.
Das andere ist, wenn ich diese Menge aller zu durchlaufenden Zustände
berechnen will, auch das kann man wieder induktiv machen.
Wie stellt man das formal dar?
Na gut, ich habe wieder irgendeinen Zustand Z und ein Wort aus dem
Eingabealphabet.
Das heißt, ich bilde aus diesem kathesischen Produkt ab und statt dass
jetzt nur ein einzelner Zustand Z rauskommt, kommt jetzt halt eine
Folge von Zuständen raus und die kann ich wieder als Wort darstellen
über die Menge der Zustände Z.
Die Menge der Zustände Z interpretiere ich jetzt als ein Alphabet und
alle Wörter über diesem Alphabet kann man dann interpretieren als
Zustandsfolgen.
Jetzt kann ich das wieder induktiv definieren.
Wenn ich in Z bin und nichts mache, dann habe ich genau den Zustand Z
durchlaufen, bin ich nach wie vor im Zustand Z.
Wenn ich jetzt ein Wort hernehme, das aus mindestens einem echten
Zeichen besteht und ich trenne das letzte Zeichen ab, wie sieht dann
meine Folge aus?
Naja, das ist erstmal so, dass ich von Z W reinlaufen lasse.
Dann bin ich in irgendeinem Zustand, in welchem Zustand ich bin.
Das gibt mir F Sternchen von Z und W an.
Und dann muss ich noch den Übergang machen, den ich mache, wenn ich
die Eingabe X bekomme.
Das gibt mir die Übergangsfunktion F an und das konkateniere ich
einfach hintendran an das Wort, das ich schon erhalten habe, wenn ich
von Z die Eingabe W sehe.
Also auch wieder eine induktive Definition, diesmal mit Konkatenation,
um dieses Wort der durchlaufenden Zustände der Reihe nach aufzubalten.
Und auch das könnte ich wieder, wenn ich wollte, alternativ so
darstellen, indem ich nicht Hintenzeichen vom Wort abhacke, sondern
Vornezeichen vom Wort abhacke.
Gut, Beispiel.
Ich habe wieder meinen Getränkeautomaten.
Ich möchte wissen, was passiert, wenn ich vom Anfangszustand loslaufe,
der Anfangszustand war kein Euro drin, noch kein Getränk ausgewählt
und dann kommt einer hin und fummelt an dem Automaten rum.
Der drückt einmal R, dann tut er ein Euro rein, dann drückt er wieder
R, dann drückt er Z und dann kommt O raus.
Und dann kann man sich anschauen, welche Zustandsfolgen man
durchläuft.
Man kann schön mit dem Finger dem Automaten nachfahren und sieht dann,
dass er sich merkt, dass schon etwas ausgewählt wurde.
Dann merkt er sich irgendwann, dass der Euro reingeworfen wurde und
wenn dann ganz zum Schluss OK gedrückt wurde, dann laufe ich wieder
entsprechend in den Zustand rein, dass kein Euro mehr da ist und auch
nichts ausgewählt wurde.
Also genau das Verhalten, das wir auch wollen.
Das, was ich jetzt für die Eingabefunktion gemacht habe, das kann ich
in gleicher Art und Weise natürlich auch für die Ausgabefunktion
machen.
Und das interessiert mich ja letztendlich genauso.
Genauso spannend ist ja nicht, wie welche Zustände durchläuft der
Automat, es ist ja auch, welche Ausgabe gibt er.
Also was hat der Benutzer, der da am Automaten Eingabe gemacht hat,
was kriegt er raus?
Das ist jetzt wieder eine Funktion, die bildet wieder ab von den
Zuständen und einem möglichen Wort, also aus dem kathesischen Produkt,
der Menge der Zustände und der klinischen Hülle über dem Alphabet der
Eingabe.
Und der bildet dann ab in ein Wort über dem Alphabet der Ausgabe.
Weil jedes Mal, wenn ich eine Eingabe mache, wird hier irgendwas
ausgegeben.
Es wird ein Wort über Y-Sternchen ausgegeben.
Und wenn ich jetzt mehrere Eingaben mache, dann konkateniere ich
einfach die Ausgaben zu neueren, längeren Worten aus der klinischen
Hülle dieses Ausgabealphabet Y.
Und auch hier wieder kann man zwei Hülle unterscheiden.
Einmal die letzte Ausgabe, also was ist das letzte einzelne Teilwort,
das ausgegeben wird und was ist eben diese Abfolge, wo ich die Sachen
miteinander konkateniere.
Wieder analog wie bei F haben wir G-Sternchen und G-Sternchen
-Sternchen induktiv definiert.
Wenn ich in einem Zustand bin und ich kriege keine Eingabe, dann
kriege ich auch keine Ausgaben.
Wenn ich in einem Zustand bin und ich habe eine Eingabe, das ein
echtes Zeichen hinten am Ende hat, dann trenne ich das wieder ab.
Und dann ist das die Ausgabe, die ich bekomme, wenn ich erstmal von Z
die Eingabe W verarbeite und mich dann frage, wenn jetzt noch die
Eingabe X kommt, in welcher Ausgabe mache ich dann?
Das F-Sternchen gibt mir halt den Zustand, in dem ich mich befinde
nach Verbrauchen der Eingabe W und dann G von diesem Zustand und der
Eingabe X sagt mir dann, das ist das letzte Zeichen, was ich dann
jetzt ausgebe.
Und dann entsprechend, wenn man das für die Ausgaben konkateniert
macht, macht man das dann halt so, dass man sich erstmal anschaut, was
ist das Wort, das ich bekommen habe und muss dann das letzte Zeichen
dran konkatenieren und das gibt mir halt die Funktion G-Sternchen
zurück.
Also wieder ein Beispiel an unserem Getränkeautomaten, wenn man sich
die Sequenz anschaut, der Ausgaben, wenn ich beim Startzustand anfange
und wieder eine Eingabe machen lasse dem Benutzer, dann drückt er halt
mal R, dann kommt ein Euro rein, R, Z und OK, da passiert erstmal als
Ausgabe ganz lange gar nichts, bis ich das erste Mal OK drücke und
dann kommt der Zitronensprudel raus.
Was auch logisch ist, wenn man sich da anschaut, die einzigen beiden
Eingaben, die eine Ausgabe produzieren, die nicht Epsilon sind, sind
OK und Cancel.
Also, Sie kennen jetzt die offizielle Definition vom Miliautomat und
das ist so, das werden Sie immer wieder sehen.
Sie haben schon gesehen, Grammatik wird definiert als einen Tupel und
hier haben wir auch wieder eine Definition des Miliautomaten als Tupel
hier hingeschrieben als so eine Bulletlist, als eine Aufzählungsliste.
Das Ganze kann man natürlich auch schön als Menge hinschreiben oder
halt als Tupel, dass man also die Ordnung hat, dass man weiß, was was
ist.
Es gibt eine Zumenge Zustandsmenge, es gibt einen besonderen Zustand,
das ist der Anfangszustand, es gibt ein Alphabet von Eingaben, es gibt
eine Funktion, die mir halt diese Zustandsübergänge modelliert, es
gibt ein Alphabet von Ausgaben und es gibt eine Funktion, die mir die
Ausgaben bei modelliert.
Dann im Gegensatz zum Miliautomaten gibt es noch den Muautomaten und
der Unterschied ist, dass ich jetzt die Ausgabe nicht mehr mache, wenn
ich den Zustand wechsle, sondern ich mache die Ausgabe in einem
Zustand.
Und zwar muss man sich dann überlegen, wenn man so die Zeit
quantisiert, in so Zeitschritte einteilt, mache ich das, wenn ich aus
dem Zustand rausgehe oder mache ich das, wenn ich in den Zustand
reingehe.
Hier ist die Definition, wenn ich in den Zustand gelange, mache ich
eine Ausgabe.
Und das ist insofern interessant, es ist jetzt nicht mehr wichtig, von
welchem Zustand aus ich gekommen bin.
Vorher war es so, es ist wichtig beim Miliautomaten, ich habe einen
Zustand und eine Eingabe und komme in einen neuen Zustand und während
ich diesen Übergang mache, wenn ich also diesen Pfeil verfolge, steht
an diesem Pfeil die Ausgabe dran.
Beim Murautomaten habe ich jetzt immer noch die Übergänge, an den
Pfeilen stehen immer noch die Eingabe dran, aber egal von welchem
Zustand ich gekommen bin, sobald ich diesen Zustand erreiche, mache
ich eine einzige Ausgabe.
Insofern nur eine ganz leichte Modifikation.
Ich habe nach wie vor Zustandsmenge, Anfangszustand, Eingabe,
Alphabet, eine Übergangsfunktion.
Ich habe ein Ausgabealphabet, aber meine Ausgabefunktion jetzt bildet
nicht mehr ab aus dem kathesischen Produkt von Z und X, sondern bildet
nur noch ab aus der Menge der Zustände in die Wörter über dem Alphabet
Y.
Man kann das jetzt analog zum Murautomaten darstellen und dass man
jetzt die Ausgabe entsprechend reinschreibt in den Zustand.
Das heißt, der Zustand bekommt jetzt irgendeinen Namen, dann gibt es
einen Strich und dann steht da drin, was der Zustand ausgibt.
Da habe ich zum Beispiel einen Zustand, der heißt QY.
Das ist der Anfangszustand, der soll 0 ausgeben.
Wenn ich dann A reingebe, komme ich in einen Zustand, der 0 ausgibt
und wenn ich viel A durchlaufe, gibt der viel 0 aus.
Wenn ich dann B reingebe, komme ich in einen Zustand, der gibt 1 raus.
Wenn ich dann entweder A oder B reingebe, komme ich in einen Zustand,
der nur noch 0 ausgibt und egal, ob ich jetzt A oder B eingebe, wird
da halt 0 ausgegeben.
Und alternativ, wenn ich vom Anfangszustand B reingebe, werden 0
ausgegeben, dann gebe ich ganz egal, wie viele Bs ich jetzt nehme,
kommt eine 0.
Wenn ich einmal ein A ausgebe, gibt es eine 1 und wenn ich danach A
oder B eingebe, gibt es eine 0.
In anderen Worten, so ein Automaten, man gibt ja das einzige Mal in
seinem Leben eine 1 aus.
Wenn ich ein Wort reinfüttere und das erste Mal einen Wechsel mache,
entweder von A nach B oder von B nach A.
Sobald ich sozusagen das erste Mal den Wechsel mache, gibt er eine 1
aus.
Also ein Automat, der detektiert mir sozusagen, wann wechsle ich das
erste Mal das Zeichen in dem Wort, das ich ausgebe.
Jetzt können wir genauso F-Sternchen und F-Sternchen-Sternchen
definieren und das ist ganz genauso wie beim Mili-Automaten, weil da
haben wir ja an der Definition der Mili-Automaten gegenüber den Moore
-Automaten nichts geändert.
Die Funktion F, die Übergangsfunktion ist genauso definiert wie bei
den Mili-Automaten, ändert sich gar nichts.
Das heißt hier, wenn ich mir das anschaue, was ist der letzte Zustand,
wenn ich so etwas wie 3 mal ABA reingebe, dann bin ich im Zustand QR.
Und wenn ich so etwas reingebe wie 3 mal ABA, dann durchlaufe ich die
Zustandssequenz QY, QA, QA, QA, QF, QR.
Wenn ich jetzt G-Sternchen und G-Sternchen-Sternchen habe, dann muss
ich halt die Funktionen entsprechend anders definieren, weil ich ja
die Ausgabefunktion gegenüber den Mili-Automaten auch anders definiert
habe.
Und die letzte Ausgabe G-Sternchen, das ist eben gerade diese
Hintereinanderausführung von A.
Ich gebe etwas aus und dann mache ich den Übergang F-Sternchen.
Kann man also so definieren, dass G-Sternchen-Zustand und ein Wort
wird konsumiert.
Das ist eben gerade A, also die Ausgabe, die ich mache.
Wenn ich erstmal die Zustände durchlaufe mit dem Wort W, dann komme
ich an den Zustand F-Sternchen-Z von W und dann wird darüber A
ausgeführt.
Wenn ich jetzt alle Ausgaben haben möchte, dann bilde ich auch wieder
ab von dem kathesischen Produkt, der Zustandsmenge und diesen Wörtern,
die Eingaben sein können.
Und das nennen wir, können wir durch diese Funktion H-Sternchen
-Sternchen machen.
Und jetzt erinnern wir uns an das Kapitel über die Isomorphismen und
Homomorphismen und haben damals schon in dieser Definition
kennengelernt, dass dieses H-Sternchen-Sternchen eben der durch H
induzierte Homomorphismus ist.
Also die in Kette ausgeführte Hintereinanderausführung mit
Konkatenation der Ausgaben.
Einfaches Beispiel, wenn ich halt jetzt wissen will, was ist die
Ausgabesequenz oder die Zustandssequenz durchlaufe oder die Ausgabe
ist, wenn ich von Anfang an fange und dann A, A, A, B, A anlaufe, dann
kann ich mir F-Sternchen-Sternchen anschauen.
Das zeigt mir die Zustandssequenz an und dann kann ich einfach G
-Sternchen relativ leicht ausrechnen, indem ich angucke, in welchem
Endzustand komme ich an.
Das heißt, ich komme also im Zustand QR an und dann gucke ich mir, was
ist die Ausgabe von QR und das ist dann entsprechend 0.
Und bei G-Sternchen-Sternchen ist das eben diese in Kette ausgeführte
Ausführung dieser Ausgabe H auf dieser Sequenz, die mir das F
-Sternchen -Sternchen vorgibt.
Und das ist halt dieses Hintereinandersetzen und Konkatenieren der
einzelnen Ausgaben der jeweiligen Zustände, die ich der Reihe nach
durchlaufe.
Also, Moorautomat definiert so ähnlich wie der Miliautomat.
Einziger Unterschied ist an der Stelle dieser Ausgabefunktion G, die
aus dem kathesischen Produkt von Zuständen und Eingabesymbolen
abbildet, bilden wir nur noch von den Zuständen ab.
Und jetzt gibt es einen Spezialfall dieser Moorautomaten.
Dieser Spezialfall ist der sogenannte Endliche Akzeptor und der ist
gut dafür geeignet, um mit Sprachen und Grammatikern und Wörtern zu
arbeiten.
Der Sonderfall ist, dass wir jetzt eine ganz besondere Form von
Ausgabealphabet haben.
Und das Ausgabealphabet, das wir jetzt haben, besteht nur noch aus den
beiden Symbolen 0 und 1.
Und die Idee dahinter ist, dass man jetzt in diesem Moorautomaten
spezielle Zustände definiert, die man sich so vorstellen kann als
Endzustand, der erreicht werden soll, wenn ein bestimmtes Wort
eingegeben wird.
Und diese Zustände nennt man die akzeptierenden Zustände.
Und was diese akzeptierenden Zustände machen ist, wenn sie erreicht
werden, geben sie 1 aus.
Und alle anderen Zustände geben 0 aus.
Und was man halt wissen will ist, kann man jetzt ein Wort, das man
reingibt, irgendwie verarbeiten.
Ist das zum Beispiel korrekt gemäß einer bestimmten Syntax?
Ist die Eingabe wahr oder falsch?
Ist die Eingabe gut oder schlecht?
Und das kann man jetzt dadurch machen, indem man sich sozusagen
anschaut, was ist denn h-Sternchen von einem Wort?
Ist das 0 oder ist das 1?
Und wenn es 0 ist, dann soll der Automat das Wort eben nicht
akzeptieren und wenn es 1 ist, h-Sternchen von W, dann soll das
akzeptiert werden.
Und man macht das jetzt dadurch, dass man halt nicht überall alle
Zustände immer 0 und 1 reinschreibt, weil in der Regel wird man sehr
viele nicht akzeptierende Zustände haben und sehr wenige akzeptierende
Zustände, sondern ich markiere mir nur noch die akzeptierenden
Zustände.
Das mache ich, indem ich die so einen Doppelkreis, durch so einen
Doppelkreis symbolisiere.
Dann weiß ich, die geben halt 1 aus, die sind halt akzeptierend und
die anderen geben halt 0 aus.
Also hier haben wir jetzt diesen Moorautomaten von eben.
Das ist erstmal noch die komplizierte Darstellung, wo es einen gibt,
der 1 ausgibt und alle anderen geben 0 aus.
Das ersetze ich jetzt dadurch, dass ich diesen Doppelkringel einführe.
Und jetzt kann man sich schon überlegen, ich hatte vorhin schon
gesagt, das einzige Mal in seinem Leben, dass der 1 ausgibt ist, wenn
das erste Mal das Zeichen gewechselt wird.
Wenn also das erste Mal entweder von einem A auf das B gewechselt wird
oder wenn das Wort von einem B auf dem A ausgewechselt wird.
Und wenn danach noch was kommt, dann gehe ich rüber in diesen anderen
Zustand und der ist nicht akzeptiert.
Das heißt, die Worte, die jetzt hier nur akzeptiert werden, sind
solche Worte, die entweder mit A anfangen und dann auf einem B enden
oder die mit lauter Bs anfangen oder auf einem A entsprechend enden.
Und alle anderen Wörter werden nicht akzeptiert.
Und wie gesagt, das kann man halt dadurch machen, man kann sich also
entweder angucken, was ist das A Sternchen oder man kann halt sagen,
wenn wir halt das so machen, dass wir nicht die Ausgabe angucken,
sondern sagen, welche Zustände sind denn akzeptierend, dann guckt man
sich halt an, ist man am Ende, wenn das Wort abgearbeitet wurde und
man vom Anfangszustand aus losgegangen ist, ist man da in einem
akzeptierenden Zustand.
Und hier ist es halt wichtig, dass man immer von einem Anfangszustand
losgeht.
Wenn man also wissen will, ob ein Wort akzeptiert wird oder nicht,
dann laufe ich ganz am Anfang los.
Die Regeln, welche Wörter akzeptiert werden oder nicht, sind in den
Übergängen des Automaten kodiert und dann muss ich am Ende, damit es
akzeptiert wird, in einem der akzeptierenden Zustände sein.
Das kann ein Zustand sein, das können aber auch mehrere Zustände sein,
je nachdem, was ich akzeptieren will oder nicht.
Das heißt also, so ein Wort wie A-A-A-B-A wird halt nicht akzeptiert,
aber so ein Wort wie A-A-A-B wird akzeptiert.
Und wenn man jetzt dann sich anschauen will, wie die Sprache aussieht,
die jetzt akzeptiert wird, dann sind das also alle Wörter der Form A-K
-B, B-K-A.
Wobei das K echt größer A-0 sein muss.
Also ich muss zumindest einmal ein A oder mindestens einmal ein B
ausgegeben haben und danach noch mindestens ein anderes Zeichen und
zwar das passende, jeweils das umgekehrte.
Und dementsprechend kann man dann halt definieren, die Sprache, die
von so einem Akzeptor akzeptiert wird.
Das ist die formale Sprache, die erkannt wird.
Von A alle Wörter aus dem Eingabealphabet, sodass ich am Ende in einem
akzeptierenden Zustand reinlaufe, wenn ich vom Anfangszustand
durchlaufe.
Das ist so eine Art Syntaxanalyse.
Jetzt diskutieren wir mal, warum es ist keine Syntaxanalyse.
Mir gefällt der Term Analyse nicht so genau.
Das ist eigentlich eher ein Test, ein Syntaxtest.
Das Einzige, was nämlich bei rauskommt im Augenblick ist, ist das Wort
syntaktisch korrekt, ja oder nein.
Das ist aber nicht das, was man normalerweise unter einer
Syntaxanalyse verstehen würde.
Wenn ich jetzt eine Syntaxanalyse machen wollte, bräuchte ich eine
andere Funktion.
Da bräuchte ich nämlich dann die Funktion f**.
Weil bei einer Syntaxanalyse interessiert mich in der Regel, aus
welchen Teilen ist denn das Wort, das ich jetzt da reingegeben habe,
aufgebaut.
Also denken Sie an ein einfaches Programm.
Da interessiert sich auch, wo habe ich Schlüsselwörter, wo habe ich
Variablen, wofür sind Variablen Zuweisungen, was sind arithmatische
Operatoren, was sind Kontrollflussoperatoren, was sind Tests, die halt
auf wahr oder falsch abtesten.
Und diese Informationen, die können Sie sozusagen kodieren in den
Zuständen, indem Sie den Zuständen irgendwie eine Interpretation, eine
Bedeutung zugeben.
Und wenn Sie dann so ein Wort akzeptieren lassen, dann ist es
syntaktisch korrekt.
Und wenn Sie dann sich anschauen, was ist denn die Folge von
Zuständen, die ich durchlaufen habe, dann sagt Ihnen darüber etwas
aus, was ist denn so diese Bedeutung dieses Wortes oder zumindest aus
welchen syntaktischen Teilen besteht denn das Wort.
Und jetzt ist das Interessante, jetzt kann man sich wahrscheinlich
leicht überlegen, je nachdem wie man das macht, wie man Ausgaben und
Eingaben definiert, ist der Weg entweder eindeutig oder er ist
eventuell nicht eindeutig.
Und insbesondere wird er dann im Allgemeinen nicht eindeutig, wenn der
Automat nicht deterministisch ist.
Also hier in unserem Beispiel die Sprache, die akzeptiert wird, ist
halt A+, konkatiniert mit B, vereinigt mit B+, konkatiniert mit A.
Jetzt kann man sich anschauen, kann ich denn alle formalen Sprachen
mit so endlichen Automaten anschauen oder habe ich vielleicht Pech und
ich kann nicht alle Sprachen mit so einem endlichen Automaten
akzeptieren lassen.
Also kann ich so eine Überprüfung für jede beliebige Sprache mir
zusammenbauen oder geht das für bestimmte Sprachen nicht.
Jetzt schauen wir uns erstmal an, wo das geht.
Also angenommen, wir haben die formale Sprache über dem Alphabet A, B
so, dass die Wörter B so in der Gestalt sind, dass mindestens einmal
ein B vorkommt und vor dem letzten B muss ein A stehen.
Nicht im Sinne von direkt vor dem letzten B, sondern direkt vor dem
letzten B muss ein A stehen.
Und die Behauptung ist, es gibt einen endlichen Automaten, der diese
Sprache erkennen kann und um das zu zeigen, ist das einfachste häufig,
einen endlichen Automaten hinzumalen, der das tut.
Und da kommen wir natürlich rein, woher wissen wir denn, dass der
endliche Automaten, den wir jetzt da hingeschrieben haben, das auch
wirklich tut.
An dieser Stelle im Studium, in der Vorlesung, durch scharfes drauf
gucken, erkennen Sie das einfach.
Da haben wir jetzt erstmal keinen Formalismus, mit dem man das jetzt
beweisen kann.
Also, jetzt wollen wir uns so einen Automaten zusammenbasteln.
Also in W kommt mindestens ein B vor und vor dem letzten B steht ein
A.
Das heißt, ganz vorne kann relativ viel passieren.
Also mein Wort kann ganz unterschiedlich anfangen.
Es kann mit einem A anfangen oder es kann mit einem B anfangen.
Nur wenn es mit einem B anfängt, dann kann es nicht schon wieder
aufhören, weil dann steht nämlich vor dem letzten B kein A.
Und wenn es mit einem A anfängt, dann kann es auch noch nicht
aufhören, weil es kommt ja nicht mindestens ein B vor.
Aber wir fangen also an, geben entweder ein B oder wir geben ein A
aus.
Und so Wörter, die man haben, die fangen erstmal mit beliebig vielen
Bs an oder die fangen mit beliebig vielen As an.
Und die sind halt in der Gestalt, dass halt mindestens mit einem B
oder mindestens mit einem A anfangen müssen und danach können nach
diesem ersten B oder nach diesem ersten A erstmal keines, eines oder
viele Bs und As folgen.
Und wenn ich dann irgendwo mal Bs ausgegeben habe, muss irgendwann mal
ein A kommen.
Es darf nicht aufhören.
Es muss erstmal irgendwann wieder ein A kommen, wenn ich mein Wort mit
einem oder vielen Bs angefangen habe, weil sonst ist es kein korrektes
Wort.
Und wenn erstmal das erste A erschienen ist nach den vielen Bs, dann
können wieder keines oder beliebig viele As kommen.
Und jetzt schauen wir uns das da mal scharf an und man kann jetzt
sehen, dass man das vereinfachen kann.
Zur Vorgehensweise.
Was man hier im Prinzip macht ist, man überlegt sich irgendwie, welche
Fallunterscheidungen mache ich denn, wenn ich jetzt dieses Wort
anfange aufzubauen.
Und nach diesen Fallunterscheidungen fange ich an, meinen Automaten zu
konstruieren.
Und jetzt sehen wir diesen Teil.
Es kommt mindestens ein B oder mehrere Bs.
Oder es kommt ein A und ganz viele As mit dieser Abkürzung hier.
Das kann ich erstmal zusammenfassen.
Weil ich habe hier die Möglichkeit, dass ich mit einem B anfange und
dann beliebig viele Bs.
Oder ich habe die Möglichkeit, dass ich mit einem A anfange oder ich
habe nach den vielen Bs ein A kommt.
Und das ist nichts anderes als, es kommt entweder kein B oder mehrere
Bs und danach kommt ein A und danach ganz viele As.
Und dann kann ich das einfach so zusammenfassen.
Ich habe also vorne ein B-Sternchen.
Oder wenn ich den B-Zweig nicht durchlaufe, fange ich an mit einem A
und es kommen ganz viele As.
Wenn jetzt ich so ein Wort habe, wo keines oder mehrere Bs kommen,
dann ein A oder mehrere As und danach kommt ein B, dann habe ich schon
ein fertiges Wort.
Denn in W kommt dann mindestens ein B vor und vor dem letzten B steht
ein A.
Das heißt, wenn ich also dann von Cent 1 aus einen B ausgebe, habe ich
etwas, das akzeptiert werden soll.
Wenn ich in diesem Zustand B bin und dann gebe ich nochmal ein B aus,
dann habe ich etwas, was nicht akzeptiert ist.
Weil ja vor dem letzten B kam ja vorher schon mal ein B.
Das heißt, es steht kein A vor dem B.
Das heißt, hier bin ich wieder völlig am Anfang.
Jetzt können wieder alle möglichen Teilwörter kommen.
Und dann kommt irgendwann ein B.
Und dieses B muss halt nach einem A kommen.
Wenn ich in diesem akzeptierenden Zustand Z2 bin, das heißt, ich habe
irgendein beliebiges Wort, dann kam ein B nach einem A, dann ist das
akzeptierend.
Und wenn danach ein A kommt, dann ist das immer noch ein Wort, wo nach
dem letzten B das Vorkam und es kam mindestens ein B vor, ein A kam.
Das heißt, wenn danach noch As kommen, ist das auch nach wie vor ein
Wort, das akzeptierend ist.
Es akzeptiert wird, das heißt, ich bin in einem Zustand, der
akzeptierend ist.
Die Frage ist jetzt, wenn ich in diesem Zustand bin, der akzeptierend
ist, was ist, wenn jetzt wieder As und was ist, wenn Bs kommen?
Na ja, wenn As kommen, ist immer noch alles im grünen Bereich.
Und wenn ein B kommt, ist auch immer noch alles im grünen Bereich,
weil vor dem B, das dann das letzte wäre, kam ja vorher direkt ein A.
Aber wenn dann wieder ein B kommt, dann fange ich wieder von vorne an,
wenn wieder lauter As kommen, ist immer noch alles in Ordnung und
akzeptierend und im grünen Bereich.
Und auf diese Art und Weise habe ich jetzt einen Akzeptor gebaut, der
halt diese Sprache, diese definierte Sprache erkennt.
Wenn man sich das jetzt anschaut, man kann ein paar einfache Sachen
abklappern.
Man kann alle Zustände einmal abklappern und gucken, habe ich denn
Übergänge für jedes Zeichen aus meinem Eingabealphabet?
Das ist der Fall, weil wäre das nicht der Fall, dann hätte ich ja ein
Problem.
Ich muss also hier einen Automatenbastel, oder allgemein immer einen
Automatenbastel, dass ich für jedes Eingabezeichen auch wirklich einen
Übergang mache.
Und dann muss man halt noch irgendwie sich überzeugen, dass man
wirklich in der Lage ist, jedes beliebige Wort zu erzeugen.
Und dann entsprechend sich überlegen, welche Zustände sind dann die,
die akzeptierend sein sollen.
Ein anderes Beispiel.
Angenommen, ich habe eine Textdatei.
Diese Textdatei besteht aus vielen Zeilen.
Und ich suche genau diejenigen Zeilen, in denen ein gewisses Wort M
vorkommt.
Sowas kann man mit einem endlichen Akzeptor machen.
Schon ein kleiner Vorgriff auf die Vorlesung, wenn es hinterher um
Algorithmen geht.
Das werden Sie nicht wirklich mit einem endlichen Akzeptor machen.
Das ist nur eine Möglichkeit, das zu machen.
Es gibt da noch so andere gewiefte Algorithmen, die gerade dieses
Problem in sehr effizienter Art und Weise lösen.
Das jetzt zu machen mit einem Akzeptor ist eigentlich auch eine
relativ effiziente Art und Weise.
Was wird die Laufzeit sein, wenn Sie einen Akzeptor haben, der Ihnen
dieses Problem löst?
Welche Laufzeit wird er haben?
Genau, offenen Linearzeiten.
Sie müssen das Wort einmal genau, alle Zeichen einmal genau
abklappern.
Und dann passt das.
Das Problem ist, je nachdem was Ihr Eingabealphabet ist, kann der
Akzeptor halt relativ groß werden.
Also, wir haben eine Zeichenkette W, das sei eine Zeile.
Wir haben ein Textmuster M.
Und wir suchen halt jetzt irgendwie, ob in diesem Wort W, das der
Zeile entspricht, ob da M in diesem W vorkommt.
Das machen wir mit einem endlichen Akzeptor.
Jetzt machen wir es uns einfach.
Unser Eingabealphabet sei einfach A und B.
Und das Textmuster, das wir erkennen wollen, sei ABABB.
Wir brauchen jetzt einen endlichen Akzeptor, der das macht.
Das heißt, dieser Akzeptor soll alle die Wörter akzeptieren, die
derart sind, dass es irgendwo einen Präfix W1 gibt und einen Suffix
W2.
Und wenn dann irgendwann ABABB vorkommt innen drin, dann soll das
Ganze akzeptiert werden.
Wenn wir jetzt nochmal nachgucken und uns überlegen, ist da eine
gewisse Einschränkung.
Und diese Einschränkung ist schon in der Problemformulierung.
Die Problemformulierung lautet, Sie sollen alle die Zeilen rausgeben,
wo dieses Wort drin vorkommt.
Das ist etwas anderes, als was Sie häufig normalerweise machen.
Das ist nämlich nicht die Formulierung, Sie sollen mir sagen, wo
überall dieses Teilwort M vorkommt.
Das ist etwas anderes.
Und dieser Akzeptor macht das auch nicht notwendigerweise, sondern
dieser Akzeptor ergibt Ihnen erst einmal nur die Zeilen aus.
Beste Laufzeitabschätzung.
Wer hat vorhin die Laufzeitabschätzung gemacht?
Wir formulieren das Problem um, also es läuft in O von N.
Angenommen, wir haben eine Datei mit ganz vielen Zeilen, das seien K
-Zeilen.
Und jede Zeile habe die Länge L und mein Teilwort M habe die Länge M.
Beste Laufzeitabschätzung.
Beste und Schlimmste.
Das ist K mal M.
Das ist im besten Fall und im schlimmsten Fall.
Dann ist es K mal L.
Wenn ich vorher weiß, wie lange die Zeilen sind, wo kann ich ein
bisschen was weghobeln?
Zwar nicht im Omega-Kalkül und auch nicht im O-Kalkül, aber...
Genau, K mal L minus M minus 1, also wenn ich weiß, dass ich schon mal
genügend Zeichen habe, dann kann ich schon ein bisschen früher
abbrechen.
Was ist die Gefahr, wo ich mich für kalkulieren kann?
Das Abprüfen, wie viele ich jetzt schon gemacht habe, kostet halt auch
Zeit.
Muss man halt dann in der Praxis gucken, ob das, was ich einspare
durch Abprüfen, dass ich nicht die Zeile bis ganz zu Ende gehen muss,
ob ich dadurch genügend Zeit spare, dass ich immer mitschleifen muss,
wie viele Zeichen ich denn schon akzeptiert habe.
Also, wir überlegen uns, wie wir da hinkommen können.
Das Erste, wir gucken uns jetzt erstmal nur das Wort an, das wir
akzeptieren wollen.
ABABB, mache ich mir meine sechs Zustände und das Wort akzeptiert
ABABB, dann bin ich in einem akzeptierenden Zustand und völlig egal,
was dahinter kommt, ist mir völlig egal, da ist Ende.
Das kann aber noch nicht alle möglichen Wörter erkennen.
Ich kann im Augenblick nur Wörter erkennen, die mein Wort M enthalten
und dahinter kommt irgendein anderes beliebiges Wort W-Sternchen.
Muss mich jetzt noch kümmern, was kann denn vor dem Wort M, das ich
erkennen möchte, kommen.
Also zum Beispiel sowas, da kommen ganz viele Bs, bevor ABABB kommt.
Oder da kommen viele As, bevor ABABB kommt.
Oder da kommt zum Beispiel ein A gefolgt von zwei Bs, das kommt dann
ABA.
Oder es kommt nur AB davor.
Gut, wenn ich lauter Bs erstmal davor in meinem Wort, das kommt, das
ich einfügen will, haben will, dann mache ich da einfach so eine
Selbstschleife mit den Bs.
Einfach.
Wenn ich lauter As haben will, dann habe ich halt schon mal ein A
ausgegeben.
Das ist auch der erste Buchstabe meines Suchwortes.
Und dann mache ich noch eine Selbstschleife, dass ich beliebige As
noch zusätzlich davor einfügen kann.
Wenn ich jetzt haben will, dass ich sowas habe wie A gefolgt von
beliebigen vielen Bs.
Gut, ich habe erstmal das Präfix AB, das habe ich schon mal
akzeptiert.
Und dann gehe ich wieder zurück und will ganz beliebig viele Bs haben,
bevor ich losgehe.
Dann, was ist, wenn ich sowas haben will wie AB und ganz viele As?
Na gut, ABA habe ich schon erkannt.
Und dann kommen noch zusätzliche As.
Und dann wirft mich das sozusagen wieder zurück.
Soweit, wie das dem Präfix meines Suchwortes entspricht.
Und wenn ich halt ABABB erkennen will, wirft mich das halt dann da
hinten um ein A zurück bei meinem Präfix.
Das heißt, was ich sozusagen gucken muss ist, dieses Wort M, was hat
das denn für Präfixe in beliebigen Wörtern?
Und wenn ich sozusagen mal das Präfix aufgebaut habe und dann kommt
was anderes, was nicht dem Präfix entspricht, wie weit wirft mich das
denn wieder zurück in der Zeichenfolge, die meinem Suchwort
entspricht?
Und wenn ich das alles reingebaut habe, dann habe ich einen
vollständigen Akzeptor, der jedes beliebige Wort akzeptiert.
Und immer dann im Endzustand ankommt, wenn ich einmal mindestens das
Wort M, dieses ABABB gesehen habe.
Das sind so Beispiele für Sprachen, die man akzeptieren, erkennen
kann.
Es gibt aber auch unglücklicherweise Sprachen, die man nicht
akzeptieren kann.
Und das hängt damit zusammen, dass diese Automaten endlich sind, dass
sie nur eine endliche Menge an Zuständen haben.
Und das gucken wir uns dann nächstes Mal in Ruhe an.
Für Sie als Vorüberlegung dahinter, wenn wir ganz zurückdenken an
unseren ursprünglichen Getränkeautomaten, dann hatten die Zustände die
Aufgabe, so eine Art Speicher zu sein.
Man speichert sich, was ist vorher alles passiert.
Also wurde vorher schon mal ein Euro reingeworfen, wurde vorher schon
mal ein Getränk ausgewählt, oder haben wir noch kein Getränk
ausgewählt, haben wir noch kein Euro eingeworfen.
Das wurde alles in diesen Zuständen als so eine Art Speicher kodiert.
Und wenn ich jetzt so Wörter habe, bei denen hinten davon abhängt, was
noch kommen darf, in Abhängigkeit von dem, was ich vorher schon
gesehen habe.
Und wenn das, was ich vorher schon gesehen habe und wovon das abhängt,
was später danach kommt, wenn das beliebig lang werden darf, also
letztendlich sowas wie unendlich lang, beliebig lang werden darf, dann
brauche ich beliebig viele Zustände, Speicherzellen, die mir
speichern, was bisher denn schon passiert ist.
Und dann wird halt die Anzahl der Zustände, die ich brauche, nicht
mehr endlich, sondern sie wird unendlich.
Und für solche Sprachen geht es halt schief und da werden Sie im
Theoretischen Grundlagen der Informatik, das ist im dritten Semester,
da werden Sie noch ganz viel Spaß mit haben, um festzustellen, bei
solchen Sprachen, die so ähnlich aufgebaut sind, aber viel
komplizierter, um da festzustellen, brauche ich sozusagen endlich
viele Zustände oder brauche ich unendlich viele Zustände.
Da gibt es dann aber einen schönen Satz, das ist das sogenannte
Pumping Lemma, das Ihnen hilft, dann solche Sprachen zu analysieren.
Wir machen uns das nächste Mal relativ einfach mit diesem relativ
einfachen Beispiel und schauen dann, wo wir da in Probleme reinlaufen.
Wir sehen uns dann am Freitag wieder.