Nondeterministische vs Deterministische Automaten

Und dass jede reguläre Sprache auch durch ein NEA erkannt werden kann, akzeptiert werden kann. Um jetzt zu zeigen, dass alles das gleiche ist, müssen wir noch diesen Ringschluss vollenden. Wir müssen halt noch zeigen, dass NEAs auch wirklich durch DEA simuliert werden können. Dass NEAs nicht mächtiger sind als DEAs. Und der einzige Unterschied zwischen beiden Automaten NEAs und DEAs ist ja der Nicht-Determinismus. Das heißt, wir müssen zeigen, dass NEAs nicht-Determinismus vollständig war, notwendigerweise drin hatten, um dann eine Beziehung zu den regulären Sprachen, zu den regulären Grammatiken also aufzustellen.

Und von dem müssen wir zeigen, dass der eigentlich nicht mehr wert ist, auch wenn er erstmal die DEAs generalisiert. Und das ist das, was wir jetzt machen. Wir verenden jetzt dieses Schaubild, wir machen jetzt diesen letzten Pfeil, der von NEAs nach DEAs zeigt. Und wollen diesen Pfeil jetzt gerade verweisen. Da sind wir stehen geblieben. Okay, also, sprühen wir mal vor. Ich hoffe, ihr könnt es alles sehen. Ich weiß nicht, ob man es noch heller machen kann. Und wenn es ein paar Buttons gibt.

Ich sehe es von hier unten eigentlich recht gut. Ja, auch na dann. Und vielleicht eher nicht. Wir sind hier stehen geblieben. Wir haben noch gezeigt, dass die Regelwerke-Sprachen durch NDAs akzeptiert werden. Jetzt gehen wir zu den NDAs über und müssen irgendwie zeigen, nein, dieser Niche-Terminismus, den wir dort drin haben, den wir benutzen können, der ist eigentlich gar nicht wirklich notwendig. Und der Satz, den wir dazu zeigen, ist, jeder NDA, ja,

ergibt mir eine Sprache, die auch von einem DEA akzeptiert werden kann. Also dann erfolge ich keinen NEA und das, was er akzeptiert als Sprache, kann ich austauschen durch den DEA, der genau die gleiche Sprache akzeptiert. Und dann wissen wir natürlich auch, dieser Nicht-Determinismus ist nicht mächtiger, weil ich kann NEA durch den DEA dann halt ersetzen und brauche gar nicht diese Möglichkeit der verschiedenen Folgezustände. wie der Nideterminismus mir halt eben geht.

Also umgangssprachlich ist die Aussage, NDRs sind nicht mächtiger als DRs. Und das ist irgendwie überraschend, weil das nicht immer so ist. Im nächsten Semester werden wir diese grundlegenden Komplexitätsklassen kennenlernen, wo der Nichtdefineinismus auch in der Definition vorkommt. Man kennt nichts besser, als es mit Nichtdefineinismus diese Klassen zu definieren. Und dort ist noch immer ein Millionen-Dollar-Problem, das ist ein Minimum-Problem, ob wirklich dieser nicht-determinismus gleichbedeutend ist mit dem determinismus.

der wirklich auch nicht mächtiger ist. Man glaubt sogar, dass das nicht so ist, dass dieser Nicht-Ethermismus wirklich mächtiger ist, in der Welt, aber hier bei Automaten ist er nicht mächtiger. Und das zeigt man jetzt. Also NDAs sind nicht mächtiger als DEAs, obwohl natürlich die DEAs verallgemeinert werden durch die Nicht-Ethermismus. Und auch das hier zeigen wir halt mit den Ideen, die wir eigentlich bis jetzt hatten. Wir haben diese

Vorstellungswelt gehabt, dass wir den Nicht-Ekriminismus begreifen als das Verzweigen in ziemlich viele Parallelwelten. Immer wenn wir die Entscheidung haben, welchen Folgezustand wir nehmen in einem Automat, wir sind jetzt aber im Zustand, lesen ein Zeichen, jetzt haben wir vielleicht jeweils zwischen zwei Folgezuständen, dann erzeugen wir dafür eine neue Parallelwelt und führen dort dann halt ein DER auf in dieser Parallelwelt, der jetzt in den einen Zustand gesprungen ist und in einer anderen Parallelwelt halt, dann ist das ein DER auf, der jetzt in den einen Zustand gesprungen ist und in einer anderen Parallelwelt halt,

genau das gleiche mit dem anderen Folgenzustand. Also stellt euch vor, ihr seid vielleicht bei dem Zustand Q und lest das Zeichen A und natürlich habt ihr dann irgendwo die Wahl beim Nicht-Erkennismus, in welchen Zustand ihr geht. Das kann entweder in diesem Zustand sein, hier, sagen wir mal Q1, Oder es kann vielleicht in diesem Zustand sein.

Hier wird eine Parallelwelt aufgespannt und hier eine andere Parallelwelt. Wenn ich hier einen guten Tag bin und mein nächstes Zeichen, was wirklich determiniert ist, weil ich das ist eine Eidabe lese, geht das gleiche von vorne los. Ich kann auch hier wieder verzweigen. Vielleicht habe ich drei Volllustgestände. Dann schweizt hier wieder ein 3-Parallelwelt drauf. Hier eine, vielleicht noch mal diese hier und dann vielleicht hier eine. Und so entstehen immer mehr Parallelwelten, wo eigentlich die feministische Automaten laufen.

Und ganz am Ende gucken wir, ob in irgendeiner dieser ganzen Parallelwelten existieren. Also hier, diese, diese, diese, diese und so weiter. Auch da irgendein Berechnungspfad akzeptieren kann. Wenn das der Fall war, dann akzeptieren wir das Wort. So funktioniert diese eine Vorstellung, die wir jetzt in der Stunde gestern gehabt haben. Diese Parallel-Sichtvorstellung. Und das gibt uns gleich eine Idee. Wie den Beweis, wie wir das jetzt durch deterministische Automaten simulieren können.

Weil hier haben wir doch, wenn wir festgelegt haben auf eine Parallelwelt, sagen wir mal diese hier, dann haben wir doch nur noch einen deterministischen Autopaten. Jeder Folgezustand ist hier festgelegt. Hier brauche ich diese Bahnenkörner, weil ich mich schon festgelegt habe auf diese eine Welt. Und keine Verzeihungen mehr möglich sind. Also ist die Idee, dass ich jetzt alle Parallelwelten simuliere, indem ich zu jedem Zeitpunkt festhalte, in welcher Zustand teilmänglich sein kann.

Ich halte die eine Zeile fest, dieser ganzen Parallelwelten, und sage damit, okay, in dem Moment, wo ich hier in der Zeit bin, die Zeit schreitet ja so voraus, das ist die Zeitsprache, die Berechnung, und wenn ich jetzt in diesem Zeitpunkt bin, entspricht das einer Zeile über alle Parallelwelten, so eine Momentaufnahme, dort halte ich fest, in welchen Zuständen ich zu dem Zeitpunkt überall sein kann, das ist gerade Q1 und Q2, sonst kein Zustand.

Und das ist nichts anderes als eine Teilmenge von Zuständen aus der ganzen Zustandsmenge Q. Das Ding hier ist also eine Teilmenge von Q. Und so kann ich festhalten, wo die ganzen verschiedenen Parallelen-Berechnungsfahnen sich befinden. Das ist die Idee. Wenn ich das so mache, dann muss ich halt als Zustand eine Teilmenge nehmen, also das Ganze jetzt, eine ganze Teilmenge von Zuständen, wird mal neuer Zustand sozusagen eines deterministischen Automaten. Aber der geht wirklich präzise an, in welchen Parallelen...

weil ich gerade wo bin. Und danach mache ich das natürlich nochmal. Danach kommt die nächste Seite hier. Ich bin in verschiedenen anderen Zuständen dort. Vielleicht auch das ist aber eine Teilmenge von Q. Und die kann ich auch festhalten. Wenn ich jetzt von Teilmenge von Q zur Teilmenge von Q springe, dann habe ich wieder einen Automaten gebaut, der einen ziemlich viel größeren Zustandsraum hat. Klar, weil ich muss statt einem Zustand, wo sich eine beliebige Menge von Zuständen festhalten hat. Aber ich habe trotzdem wieder einen vitaministischen Automaten.

Weil ich hier von einer Teilmengen zu einer festgelegten nächsten Teilmengen springe, da ist auch keine Wahlmöglichkeiten mehr da. Alle Wahlmöglichkeiten habe ich hier durch die Teilmengenbildung abgesetzt. Fragen dazu? Okay, wenn ihr das verstanden habt, dann müssen wir jetzt mal die Konsequenzen rausziehen. Vorher hatte ich als deterministischen Automaten hier meine Und dann sagst du ja, puh, und dann Sigma und hast ja nicht gesehen.

Jetzt brauche ich hier für einen Zustand die Information eine Teilmenge festzuhalten über alle Zustände. Was ist das jetzt für eine Menge, in der mein neuer Automat leben muss? Aus welcher Menge greife ich jetzt diese Zustände? Jedes Element muss eine Teilmenge von Q sein. Ich schreibe euch mal die Elemente hin, ich möchte eine Menge bilden. Das erste ist die Wehrmenge, dann vielleicht die Menge, die nur Q1 enthält, oder nein, sagen wir mal Q0.

Dann möchte ich aber auch die Möglichkeit haben, in den Zustand Q0 Q1 zu springen oder Q1 Q2, weil ich dort dann genau diese Zeit veredigt habe. Diese Auswahl von Zuständen in den Parallelwelten, in denen ich halte. Welche Menge binde ich dann? Aus welcher Menge schöpfe ich jetzt meine Zustände? Jedes Element ist eine Teilmenge von Q und die ganze Menge ist die Potenzmenge. kennt ihr alle aus der Schule.

So geschrieben von Potenzmengen von Q oder etwas neuer so geschrieben, 2 hoch Q. Wir merken, dass hier oben keine Zahl ist, sondern eine Menge. Wie komisch, 2 hoch Q ist eine Zahl und man erweitert hier auch eine Zahl in Exponenten. Aber Leute, ich schreibe das eigentlich so, das ist eine ganz schöne Schaltweise, weil man meint jetzt nicht die Anzahl hier und damit wirklich eine Zahl, Sondern indem man hier eine Menge oben hin macht, meint man wirklich dann die Menge,

jedem Q zwei Möglichkeiten zu ordnen, entweder drin in der Menge oder nicht. Also das Q0 zum Beispiel ist drin oder nicht. Das Q1 zum Beispiel ist drin oder nicht in der Teilmenge. Insofern ist das hier tatsächlich die Potenzmengen von Q, die Menge aller Teilmenge. Und ja, insofern hat sich unser Zustandsraum gerade massiv erhöht, aber wir haben dadurch Determinismus erzwungen. Und genau so bilden wir jetzt diesen Automaten.

dann ist er deterministisch. Okay, also hier 2 hoch Q, alles andere Sigma und Q0 zumindest bleibt gleich. Jetzt müssen wir aber noch klären, was ist denn, wann akzeptieren wir wirklich? Wir wissen das eigentlich. Bei diesen nicht-aterministischen Maschinen ist es doch so, dass wir alle Rechnungsfälle wirklich durchgehen müssen und wenn einer akzeptiert, akzeptieren wir das dann ist es doch. Und das muss ich jetzt abbilden hier.

Das heißt, wenn ich irgendwann in einem Zustand bin und dort ende und auch nur irgendeiner von diesen verschiedenen Möglichkeiten, Q7, Q11, Q5 in dieser Zeile akzeptiert ist, zum Beispiel Q5.

dann ist auch meine Teilmenge akzeptiert. Dann ist diese gesamte Teilmenge akzeptiert. Weil der Einfad ausreicht und dieser Fad, der jetzt zu diesem akzeptierenden Zustand führt, reicht halt aus dafür, dass ich das Wort halt auch akzeptieren kann. Also definiere ich mir jetzt meine Menge der akzeptierenden Zustände fm, dieses grüne Ding dort oben, definiere ich mir jetzt so, dass alle Teilmengen akzeptierend sind, Die hat eine Analyse in diesem Fall.

die mit der alten akzeptierenden Zustandsmengen sich schneiden. Also wo wirklich ein Q5 zum Beispiel drin ist, was schon eben beim NER akzeptieren ist. Und das in dieser Teilmenge drin ist. Hier ist das X gerade die Teilmenge und hier ist das gerade akzeptieren, weil das eine Zustand in der NER akzeptieren muss. Nichts anderes steht dort. Sieht ein bisschen kompliziert aus, aber da steht halt naja alle Teilmenge X von Zuständen werden genau dann akzeptiert, wenn sie ein Element enthalten.

akzeptiert wird. Diese Elemente sind natürlich Zustände wie dieses Q5. Okay, also das ist auch nicht überraschend wegen der Definition der Akzeptanz von NEAs. Und jetzt müssen wir nur noch klären, wie unsere Zustandsübergangsfunktion ist, weil wir jetzt wieder deterministisch sind, ist es wieder eine Funktion und die springen natürlich von einer Teilmenge von Zuständen zu einer anderen Teilmenge von Zuständen. Und dadurch gibt es keine Wahlmöglichkeit mehr.

Die sieht dann so aus, dass ich nicht im Zustand Q habe, sondern in dieses Delta jetzt ein x langes Eben. Hier sehen wir dieses x. Das ist ja aus der Potenzlänge von Q genommen. Und jetzt muss ich lernen, wo bin ich dann eigentlich eher. In dieser Seite diese x vertreten sich mehrere Zustände.

Zum Beispiel diese Zustände Q0, Q1. Ich kann jetzt ein Zustand sein, der Q0 und Q1 enthält. Das ist ja der Keimung. Ich bin jetzt gleich hier, in diesem Zustand des ähnlichen Automaten, den ich gerade erstelle. So, und jetzt kann ich im ursprünglichen NER, kann ich von Q0 ausgehen und das Wort A lesen. Oder den Buchstaben A lesen. Dann komme ich hier vielleicht wieder zu Q0 zurück. Oder ich komme zu Q1. Oder ich kann von Q1 aus das Buchstaben A lesen und dann komme ich möglicherweise woanders hin.

Und alle erreichbaren Zustände, die ich da so haben kann, durch das Lesen des Zustands A, die kommen jetzt in eine Menge und die verabschieden ich, diese Menge, das sind jetzt quasi alle Nachfolgezustände des NEA, die ich habe, und die nehme ich dann als neue Teilmenge von Q. Und jetzt machen wir das dann gleich am Beispiel. Ich glaube, hier steht sogar alles. Ich starte einfach mal, der einfache Teil war mit dem Zustand, der nur aus einem

mit der Teilmenge, die nur aus einem Zustand besteht, nur aus Q0. Dann habe ich hier die Menge Q0. Ich lese den Buchstaben A und jetzt gucke ich halt, wo kann ich herauskommen. Einmal kann ich dem Fall folgen und ich lande bei Q0. Andererseits kann ich auch mit A dem Fall folgen, das ist ein MEA, und ich lande bei Q1. Also es ist die Menge meiner möglichen Folgezustände, Q0 und Q1, und ich nehme das als Teilmenge. Deswegen nennt man das auch die Potenzmengkonstruktion oder hier die

diesen erstellenden Automaten, den wir hier erstellen, den Potenzmengeautomaten, weil wir halt uns der Potenzmenge bedienen und nur von Teilmenge zu Teilmenge handelegen. Das heißt, der nächste Zustand ist jetzt Q0 und Q1, ist also genau dieser Zustand. Und deswegen habe ich hier den Pfeil A hingemalt, weil diese Teilmenge beim Lesen von A in diese Teilmenge überführt wird. Und jetzt ist es deterministisch. Jetzt gibt es keine Wahrnehmung.

Alles was hier reichen kann ist ein Teilmesser. Was passiert, wenn ich jetzt aus der Menge Q0 herausgehe mit Lesen von Buchstaben B? Dann gibt es keine Wahlmöglichkeit. Hier ist es deterministisch. Dann lande ich in Q0 wieder. Das ist aber schon der Zustand, den ich habe. Die Menge Q0 ist auch eine Teilmengel. Also male ich hier diesen Pfeil B. Jetzt muss ich weitergehen. Ich habe hier noch einen Zustand, der besteht aus zwei Elementen. Das ist auch wieder eine Teillinge.

Jetzt frage ich mich beim Lesen von Buchstaben A, wohin komme ich dann? Und das ist immer wieder dasselbe Prozedere, machen wir jetzt noch einmal hier. Ich gehe alle Elemente durch, zum Beispiel Q0, gucke in den ursprünglichen NM a, lese in den Buchstaben A und gucke nach, wo ich halt rauskomme. Also hier wieder Q0 oder Q1. Das heißt, es ist möglich, wenn ich den Buchstaben A lese, dass ich wieder in genau diese Menge zurückkomme. Und was anderes ist noch nicht möglich, weil wenn ich bei Q1 A lese, kriegt ja nichts. Ja, da ist die leere Menge da. Die wird vereinigt, mit dem Buchstaben,

mit Q0, Q1, also komme ich wirklich nach Q0, Q1 zurück. Wenn ich aber B lese, dann kann ich entweder von Q0, durchlesen von B zu Q0 zurückkommen, oder von Q1, durchlesen von B, nach Q2 kommen. Mein Ziel, mein Folge zwischen jetzt also entweder Q0 oder Q2 in den Parallelselten, ich schmeiße wieder zusammen, ich vereinige das und habe jetzt mein Timing. Die besteht jetzt aus Q0 und Q2. Das ist verschieden von dieser Teilmenge.

Deswegen wird hier ein neuer Zustand aufgemacht. Bestehen aus Q0 und Q2. Und mit D erreichbar gemacht werden. Klar rechnet ihr euch tot, wenn ihr das händisch macht. Und dieser Automat groß ist. Denn ihr seht jetzt ja schon, dass die Zustandsmenge exponentiell wächst. Die Potenzmenge hat. Auf der anderen Seite, nicht alle Zustände sind erreichbar. Von unserem Startzustand raus. Denn ich starte ja immer hier bei Q0. Also wo es jetzt hier vielleicht noch weitergehen. Ich hab die Rade erstellt.

Ihr seht, dass zum Beispiel der Zustand Q1, Q2 ist gar nicht unter den vier Zuständen, die ich hier hingemalt habe, dabei. Weil er gar nicht erreichbar ist durch den Automaten. Das ist vom NER abhängig, den ihr dann als Eingabe habt. Sofern hier ist es noch gut handelbar und natürlich stellen wir immer solche Aufgaben, dass man dann auch wirklich handelbar schrägern kann, wenn man es mal gefordert ist, das zu tun. Dann ist jetzt die Frage, wenn wir diese Zustände aufgestellt haben,

welche davon sind akzeptierend. Dieser hier, den ich gerade habe, der ist nicht akzeptierend, weil weder Q0 noch Q1 ist akzeptierend im NEA. Dieser hier, Q0, Q2, ist akzeptierend, weil Q2 akzeptierend war. Einer davon, ein Element, das akzeptierend ist, reicht aus. Jetzt haben wir wirklich die Definition von NEAs hier nochmal verwirklicht, das Akzeptanzverhalten nochmal wirklich. Elementweise sind wir jetzt durchgegangen und wir wissen jetzt, okay, wenn wir hier halten sollten,

Also wenn der DEA nur A und B liest, dann ist er definitiv hier, weil es deterministisch ist, dann akzeptiert der DEA. Das Wort AB wird also hier akzeptiert. Jetzt gucken wir mal nach beim Ende, ob das hier auch so ist. Das Wort AB wird auch, naja, wenn ich hier A lese und hier B lese, wird akzeptiert bei Punkt 2. So haben wir es ja auch erstellt. Und der jetzt sagt, okay, ich kann aber A auch hier lesen und dann komme ich mit B vielleicht auch wieder hier hin und der dann nicht akzeptiert,

stimmt. Wird dann nicht akzeptiert. Das Wort wird trotzdem akzeptiert, weil ein anderer Berechnungsfall existiert in diesem NEA, nämlich der, der hier Q2 erreicht. Und der reicht aus. Ja, und wenn jetzt Q0, Q2 nennen und dieses Spiel weiterführt, könnt ihr auch zuständig drei Elemente haben. Und dann gibt es vielleicht auch schöne Rückfalle, die ihr machen könnt. Und irgendwann merkt ihr, okay, all diese Zustände erreichen jetzt keinen anderen Zustand mehr und dann ist eure

Beschreibung von dem deterministischen Automaten zu Ende. Weil die Zustände, die ihr gar nicht erreichen könnt, mit irgendeinem Eingabeport und dem Lesen vom Buchstaben, die müsst ihr natürlich auch nicht hinschreiben, weil die unerheblich sind für die Berechnung der DDR. Die habe ich hier auch nicht hingeschrieben. Ich habe also hier ohne unerreichbare Zustände gezogen.

dazu? Ja, der letzte Anzertifizierung aus Q0 und 1. Okay, können wir mal gucken. Vermutlich hängt er von Q0 und Q2, also von diesem Zustand hier ab. Also gehe ich nochmal durch. Ich verbinde die Vereinigung über alle Q-Elemente von X, das heißt hier, ich mache das erstmal für Q0 und dann für Q2, von Delta Who are? Who are?

Das heißt, ich gucke jetzt für dieses Q0 beim Lesen vom Buchstaben A nach, wo ich im Ende A dann bin. Ich bin im Q0, lesen Buchstabe A, das wissen wir, dann kommt man noch bei Q0 raus und bei Q1. Also im Folgezustand beim Lesen von A bin ich auf jeden Fall Q0 und Q1 muss ich drin haben. Die Schreibung ist dann hoch. Jetzt enthält das Ding ja noch ein anderes, nämlich Q2, ein anderes Zustand. Und den müssen wir auch noch links auf der Seite überprüfen. Wo komme ich...

Q2 aussehen beim Lesen von Buchstaben A. Naja, hier hin, wieder nach Q2. Also wird Q2 auch hinzugefügt, hier sind die Vereinigungen. Zu dem, was ich bisher hatte. Bisher hatte ich von 0,2,1 hier stehen im neuen Zustand, jetzt kommt noch Q2 hinzu. Also habe ich diese drei. Mehr Ausgangszustände gibt es nicht. Ich bin jetzt wirklich das ganze Groß X durchgegangen, das ist entstanden aus diesen beiden Zuständen. Ja, und jetzt habe ich diesen Fall A einmal zu diesem neuen Zustand.

Jetzt sind wir bei dem neuen Zustand, jetzt machen wir mal weiter. Jetzt gucken wir, wo kommen wir von dem aus, wenn ich A leze. Naja, dann stellt sich heraus, wir kommen wieder in den gleichen Zustand zurück. Jetzt fehlt noch, das ist deterministisch, wir müssen eine Funktion beschreiben. Jeder Pfeil muss da sein, also wir müssen uns auch noch fragen, wo kommen wir hin, wenn wir hier B lesen von dem Zustand aus. Weil das eine Abort kann ja auch B enthalten, an der Stelle, ist ja möglich. Und wenn wir das aber tun, kommen wir glücklicherweise schon zu dem Zustand zurück, den wir gerade aufgestellt hatten, zu den dritten hier. und wissen deswegen, wir haben eine vollständige Beschreibung,

aller erreichbaren Zustände und hören in dem Moment halt auf. Okay, also das ist die recht schöne Potenz-Zwellen-Konstruktion und auch mit der recht, ich denke, eigentlich plausibel Idee, dass wir diese Parallelwelten haben unter dem Trick, eine Momentaufnahme festzuhalten über alle Parallelwelten und das als neuen Zustand zu nehmen, obwohl es eigentlich eine Teilmenge aller Zustände ist. Ein Zustandsraum wird größer dadurch, das stört uns aber nicht, weil wir dadurch den Determinismus wieder hingebogen haben und erreicht haben.

Ja, nochmal ganz klar aufgeschrieben, ab dem Moment ist jetzt plötzlich Delta M wieder eine Funktion geworden, weil ich jetzt ja von einer Teilmenge nach einer Teilmenge abbilde, zu einer Teilmenge abbilde. Das ist eine Funktion. Ich kriege 2 hoch Q rein, also Potenzmenge und einen Buchstaben und daraus mache ich wieder ein Element von 2 hoch Q. Das spielt auch ein Teilhänge ab. Und das ist natürlich deterministisch.

Also M ist deswegen wirklich ein DEA. Okay, ah, Frage. Was bedeutet ohne unerreichbare Zustände? Unerreichbar durch den DEA? Unerreichbar durch den DEA jetzt. Also ein Zustand ist dann erreichbar, wenn ich überhaupt eine Sequenz von Transitionen habe, die von Q0 ausgehen und diesen Zustand erreichen. Dann ist dieser Zustand erreichbar. Wenn ich jetzt gar nicht von Q0, also von diesem Zustand hier,

aus irgendwie einen Pfad, eine Sequenz von Transitionen bis zu diesem Zustand hier oben, den Energiener, den er haben kann, dann werde ich den auch nie erreichen. Insofern brauche ich ihn gar nicht hinzumalen. Der ist deswegen unerheblich, weil die Akzeptanz von Wörtern ist davon unabhängig, wie dieser Zustand überhaupt aussieht. Wenn es nicht ganz klar ist, ich kann jetzt nochmal versuchen klarer zu machen. Stell euch mal in den Björnens mal konkret klar.

immer schön an Beispielen umzurechnen. Hier oben ist ein Element der Potenzumenge nicht drin, sogar mehrere. Wir haben ja drei Zustände, 2 hoch 3 sind 8, ich habe aber nur vier Zustände hier. Zum Beispiel ist der Zustand Q1, Q2 nicht drin. Den habe ich hier nicht hingewahrt. Grund ist, der ist nicht erreichbar von Q0 aus. Denn wenn ich den erreichen möchte, muss ich ja bei Q0 anfangen. Ich habe aber alle Pfeile hingeschrieben, die es überhaupt gibt.

Eingabezeichen, die ich lesen kann. Ich komme zu dem zweiten Zustand, der dort steht, auch zu dem dritten, dann auch immer zu dem vierten. Ich komme auch wieder möglicherweise ein bisschen zurück, aber dadurch, dass ich alle Pfeile, alle Buchstaben, die gelesen er können, dort aufgemalt habe, und dieser Zustand nicht dort rausgekommen ist, ist der nicht erreichbar durch ein Zeichen, was ich lese. Insofern ist eigentlich ziemlich egal, was sich hier dann abspielt. Wir könnten das berechnen. Aus Spaß kann man es ja wirklich mal machen. So, eins wird jetzt bei Lesen von A, naja, bleibt, also die leere Menge.

Q2 ist beim Lesen von A, bleibt Q2. Also der hier wird in den Zustand Q2 beim Lesen von A positioniert. Könnte ich hinschreiben. Stimmt auch, aber ist unerheblich, weil die Erreichbarkeit von Q0 aus, von unserem Staat, den ich immer ganz häufig habe, für die Akzeptanz eines Wortes, die findet in dem Bereich statt. und dieser Bereich ist komplett getrennt vom diesem Bereich.

Also ich dachte jetzt unerreichbar mit dem NEA, also dass man keinen Zustand im DEA und Bauungsverfahren mit dem DEA kann sein. Ne, als Gemeins finde ich unerreichbar im DEA, weil im DEA ist ja immer die grundlegende Frage, das Wortproblem zu lösen. Ich kriege ein Wort rein, ich lese Buchstaben für Buchstaben, von links nachher jetzt durch und dann entscheide ich, okay, ist dieses Wort in der Sprache drin, wie ich es akzeptiere oder nicht, je nachdem ob der Endzustand akzeptierend war oder nicht. Das ist ja immer die Frage. Wenn ich das jetzt hier mache, starte ich bei dem Zustand Q0 mit gesparten Klammern,

lese mein Wort, trage also A, eingehe diesen Transitionspfeil entlang, lande irgendwo in dem Zustand und gucke dann nach, ob der akzeptiert ist. Und für dieses ganze Prozedur ist das unerheblich. Also das ganze Prozedur findet deswegen hier statt. Gehe den Transitionspfeil entlang, bei Wesen von A, vielleicht auch B, nachdem wie das Eingabewort ist, lande irgendwo hier und wenn der Akzeptieren ist akzeptiert und sonst halt eben nicht. Kein Fall geht hierüber in den Bereich des Automatik.

ist zwar da, aber er ist unerheblich, weil kein Pfeil darüber gibt. Also kann ich beim Lesen von irgendeinem Buchstaben gar nicht mehr hinkommen, mir ist also herzlich egal, was ich hier anspiele, auch wenn es dem Automaten eigentlich dazugehört. Das heißt, der Potenzialenautomat konstruiert eigentlich alle Zustände, aber man visualisiert eigentlich nur die, die erreichbar sind von Q0, weil für das Akzeptanzverhalten nur diese, die erreichbar sind, noch alle die Erreichbar sind. Für den DEA alleine.

gedacht und das Wortproblem auch dem DEA. Okay, also das war dann die Potenzwertkonstruktion abschließen. Jetzt haben wir den halt angegeben, diesen DEA, den wir jetzt schon auf dem Magen. Wir haben Beispiele gesehen, wie er erzeugt werden kann und jetzt müssen wir eigentlich noch zeigen, dass das auch wirklich dieselbe Sprache akzeptiert. Dann haben wir wirklich die Gleichheit von NEAs und DEAs.

müssen noch was beweisen, wir müssen noch zeigen, dass diese Sprachen, die jetzt die Sprache des NEA, eine Teilmenge der Sprache von dem DEA ist und umgekehrt. Dass die selben Sprachen erzeugt werden oder akzeptiert werden. Jetzt gehe ich davon aus, dass wir hier die Sprachen Wort haben aus dem NEA, das akzeptiert wird, das ist also in LN drin. Es gilt, dass dieses Wort B in LN drin ist, das Wort besteht wieder aus N Buchstaben, sagen wir mal, OBDA.

Und die Definition davon, dass es akzeptiert wird, also in der Sprache drin ist, ist ja wieder, es gibt eine N-Berechnung. Eine Berechnung auf der Maschine N mit vielen Zuständen, die durchlaufen werden, und natürlich, dass jeder Zustand über diese Delta-Relation erreicht wird. Natürlich muss man am Ende auch dann einen akzeptierten Zustand haben. Das ist einfach nur die Definition. Jetzt wollen wir daraus eine N-Berechnung machen. Eine Berechnung auf dem DEA und gucken, ob das wirklich genau das Gleiche hier rauskommt.

Das könnt ihr auch konkret machen mit dem Wort AB. AB landet hier im Zustand Q2 links, wird also akzeptiert. Und rechts bei dem BA kann ich A abtragen, landet im zweiten Zustand, kann B abtragen, landet im dritten Zustand und der ist auch akzeptiert. Das muss ich jetzt in Allgemeinheit verifizieren und das kann ich machen, weil diese N-Berechnung ja zwischen den Qis hier umsträngt mit dieser Delta-Relation. Ja, und ich habe diese

diese neue Delta-Funktion, das dA, genau so erstellen, dass diese alten Delts genommen werden, dass die neue Teilmenge hier mit dem Delta erstellt wird, was ich hier gemacht habe, was das alte Delta benutzt. Das heißt hier, wenn so eine Zustandsfolge existiert, gibt es auch Mengen x0 bis xn plus 1, die diese Zustände enthalten und als Teilnehmung

durchdämpfe erreichbar sind jeweils. Jetzt kann man sagen, wir können uns immer was wünschen. Wir wünschen uns, dass das qi dann gmx ist für jedes i, also dieses spezielle qi. Wir wissen auch, dass dann der letzte

die letzte Zustandsteilmenge hier auch im Akzeptieren ist, weil ja einer dieser Zustände, jetzt hier für zwei zum Beispiel, akzeptieren gewesen sein muss, weil das Wort ja hier akzeptiert worden ist und weil es ja hier dann auch Teil dieser ganzen Teilmenge ist, die zwei ist ja Teil dieser Teilmenge, ist auch das Ding hier akzeptieren und deswegen akzeptieren wir auch für den DEAM. Nach der Faktion der Faktion, der dort ist ja hier dann auch ein Doppelkring zu machen.

Folgt daraus auch, dass wir eine M-Berechnung haben, auch diese Mengen XI. Wir enthalten diese einzelnen Zustände der Berechnung von dem NER jeweils. Und das ist die Definition davon, dass wir akzeptieren, auch auf dem DEA. Wenn wir also auf dem NER akzeptieren, akzeptiere ich auch auf dem DEA. Das eine, dass es noch übrig bleibt, ist, dass wir die Rückrichtung auch machen, dass wir sagen, wenn wir rechts akzeptieren auf dem DEA, dann müssen wir auch links auf dem NER akzeptieren. Und da fehlt eigentlich nur, ich meine, wir gehen jetzt rückwärts, hier ist eigentlich nur ein Vollbefall.

Wir haben eigentlich das jetzt zur Verfügung und jetzt dann der Trick, dass wir einfach nur irgendeinen QI wählen aus diesen Mane-Mixen. Das können wir uns hier, wir starten natürlich mit dem letzten Akzeptionzustand, das ist dann hier dieser große. Wir wählen uns dann ein QI aus, hier dann das Q2 zum Beispiel, was akzeptierend ist. Das muss auch existieren, weil hier ein Doppelfinger ist. Dann existiert ein Vorgängerzustand und naja, jetzt könnte man irgendwas wählen.

ich meine, der Buchstabe, der letzte gelesene war jetzt D, also jetzt könnte ich sagen, mein Vorgängerzustand ist dieser, die ist hier rausgenommen, aber das stimmt ja nicht, weil meine XIs sind genauso viele, wie es Buchstaben gibt. Wir haben nur zwei Buchstaben, A und B. Wir müssen von Q0 ausgegangen sein, also das erste XI, das X0, der muss dieses sein, X1 muss dieses sein, und das X2 muss dann dieses sein, in dem Moment. Also muss ich hier zurückgehen, zu diesem Zustand und einem Zustand daraus nehmen, sagen wir mal Q1, dann muss ich hier zurückgehen,

Dann gehe ich weiter, wie komme ich jetzt zu dem Vorgängerzustand zurück? Naja, indem ich hier auch einen rauswerde, einen Vorgängerzustand, mit dem ich zu Q1 komme. Und das ist dann hier in dem Fall auch noch ein, hier ist also gar keine Wahlmöglichkeit im Moment. Sonst kann ich Wahlmöglichkeiten haben, aber durch eine Wahl, die immer existiert von diesen QIs, kann ich mir auch von den Dixielfolgen hier eine QI-Folge basteln.

Und dann habt ihr auch die N-Berechnung, die existiert und damit akzeptiert ihr dann diesen Wort B. Genau, ich wähle also einfach die Elemente, die Eignung aus diesen X-I's. Und das ist dann der Bereich. Jetzt haben wir wieder ein gleiches Akte-Transverhalten für jedes Wort. Und ihr wisst, dass NEA's ganz mächtiger sind als DEA's. Alles ist das Gleiche. DEA's und was sie akzeptieren können, NEA's und was sie akzeptieren können und regulierende Grammatiken und deren erkannte Sprache.

dann auch regulär heißen. All das hat dieselbe Mächtigkeit. Das haben wir jetzt in diesem Ringschluss bewiesen. Das ist relativ generell, relativ schön, dass auf dieser untersten Stufe der Chopsie hier ein sehr vollständiges Bild und können uns dort wirklich zwischen diesen ganzen Modellen bewegen und diese Austauschung gegeneinander. Wenn ihr lieber euer auszudrückendes Problem als NEA darstellt, dann macht das, weil ihr wisst, dahinter steckt auch irgendwo ein DEA, der das kann. Und für DEAs gibt es

Programme und Tools, die automatisiert ein Programm schreiben, zur Erkennung von Textsequenzen, von Zeichen, die durch DEA beschrieben werden. Also euer Problem könnt ihr wirklich als DEA dann auch hinterher formulieren lassen, wenn es durch DEA ausdrückbar ist oder durch NEA. So, wir abschließen mit dem Kapitel. Oder gibt es noch Fragen?

Gut, wir müssen auf die Uhr gucken, weil wir schon so viel Delay hatten hier. Dann verlassen wir jetzt dieses Thema, kehren aber sofort wieder zurück zu derselben Mächtigkeits-Ebene und lernen was Neues kennen, nämlich die sogenannten regulären Ausdrücke. Also jetzt das vierte Objekt, was irgendwie regulär im Namen oder mit regulären Sprachen vielleicht verbunden sein könnte. Und wir gucken mal, ob das Sinn macht, so ein viertes Objekt auch noch kennenzulernen und wie es sich verhält zu...

diesen schon bekannten. Hier kommen reguläre Ausrückungen. In der nächsten Vorlesung werden wir einen schönen Beweis kennen, der zwar schwierig ist, schwieriger als der jetzt gerade, der aber eine sehr schöne Anschauung kann. Im Sinne von Zauberung kann man das schön visualisieren. Da hoffe ich mal, dass ihr mit mir dabei bleibt.

Oder dann Christian Roselko, je nachdem er das jetzt dann hält. Aber erst mal, was sind denn reguläre Ausdrücke überhaupt? Das ist jetzt einfach was Neues. Wir werden erst mal die Syntax und die Semantik klären. Und dann das Verhältnis dieser regulären Ausdrücke beschreiben, dass die zu den regulären Sprachen haben. Aber dort gibt es auch wieder ein bisschen. Und die Motivation dafür ist, dass wir reguläre Sprachen eigentlich nur ziemlich komplex bestanden. Ja, Grammatiken sind eigentlich toll dafür, sonst ist es ja auch definiert. Wir wissen dann irgendwie, welche Regeln wir ableiten und so weiter. Aber wer schreibt denn eine reguläre Grammatik explizit auf, um wirklich abzuschreiben?

ein Ausdruck darauf hin zu überprüfen, ob eine gerade Anzahl A drin vorkommt, um ein leichtes Beispiel, ein leichtes Problem hinzunehmen. Ich möchte keine explizit machen, diese Regeln aufstellen, das ist ziemlich mühselig, auch wenn es der richtige Formalismus dahinter ist. Insofern, in der Praxis wird es häufig so gemacht, dass man stattdessen in Textform regulärer Sprachen beschreiben möchte. Und das wird tatsächlich so gemacht, mit diesem Ausdruck.

Das sieht komplett kryptisch aus. Es ist auch dann nicht einfach oder so. Aber wenn man weiß, was diese Zeichen jetzt hier bedeuten, dann kann man das eigentlich so unterschreiben und sagen, okay, ich möchte jetzt hier diese Datum in dem Format haben, diese Datumsangabe oder diese Textsequenz nur zulassen und mehr nicht. Das zum Beispiel hier, das kryptische Ding, ist wirklich, und es wird auch genutzt, ein regulärer Ausdruck, der sogar noch vereinfacht ist. Also der wirkliche dahinter ist noch ein bisschen komplizierter als der.

mit dem Emacs, also einem Texteditor, Satzenden erkennt. Das wird damit gemacht. Dadurch wird jetzt endlich so etwas wie eine reguläre Sprache beschrieben, die nur Satzenden zulässt. Und die werden dann in dem Textverarbeitungsprogramm auch wirklich so erkannt. Und weitere Anwendungen sind dann halt so Streameditoren oder ganz normale Editoren. Word ist auch dabei, SED, ADK, alles was ihr benutzt. Dafür braucht man so welche regulären Ausdrücke, um anzugeben, was man dort gerade eben suchen möchte oder ersetzen möchte.

Oder, denken wir ans Web, wenn ihr irgendwelche Datumsangaben habt, dann dürfen die nicht irgendwie eingegeben werden. Wenn ihr dort Buchstaben reinhämmert, dann soll es einen Fehler geben. Wie wird das erkannt? Naja, durch reguläre Ausdrücke. Reguläre Ausdrücke beschreiben, wie ihr dort syntaktisch das beschreiben müsst, diese Datumsangaben. Die stecken dahinter und die finden ihre Anwendung. Oder wenn ihr eine Uhr in bestandlichen Bestandteile zerlegen möchtet oder wenn ihr irgendwas anders machen möchtet, was mit Textsuche zu tun hat, dann

Zum Beispiel diese Diff-Tags. Mit dabei existieren dann auch Bibliotheken dafür, die diese regulären Ausdruck sofort in Automaten umwandeln, die dann sehr effizient berechnen können, ob so ein Text valide ist, den ich gerade schreibe oder nicht. Warum ist das effizient? Weiß das jemand? Bei Automaten? Warum rechnen sie das effizient? Warum ist das sehr stehenswert, alles automatisch auszudrücken?

Warum möchte ich einen Automaten haben, der mir hinterher für eine Textfolge, die ich einlebe, erkennt, hier kommt jetzt meine Eingabe rein, und das ist vielleicht 13.12.1900 A 9. Jetzt haben wir einen Fehler gemacht und haben hier irgendwie über Prudence angegeben. Mein Automat soll eben das erkennen, dass diese Datumseingabe leider falsch ist. So ein Fehler ausgehen, nicht richtig ausgefüllt, sondern er steigt.

wird durch Automaten gemacht. Warum eigentlich? Warum wollen wir Automaten haben? Müsst ihr die eigentlich wissen. Also, hoffentlich. Das ist ja die Eingabe. Der Punkt ist auch noch ein Eingabezeichen. Erkennen wir das Alphabet dahinter? Wahrscheinlich die Ziffer, der Punkt gehört dazu. Wahrscheinlich auch die Buchstabe, als ob wir eine Fehleingabe-Buchstabe gemacht haben. Aber Automaten sollen damit akzeptieren werden. Das ist das Einnahmewort, bestehend aus...

Zeichen. Und jeder Automat geht da wie durch? Ja, man kann es auch inklusive ausdrücken, aber wichtig ist es auf eine ganz einfache Art und Weise, von links nach rechts. Und er merkt sich nichts, das heißt hier gibt es kein großes Speicher dran. Der einzige Speicher, der ein Automat hat, findet in seinen Zuständen statt. Dort kann ich Sachen speichern. Aber der Zustandsraum ist endlich, haben wir immer gesagt. Also endlich einen Speicher habe ich.

konstante, wie er vorgibt, so viel Spannung, aber nicht wachsend mit der Eingabenlenkung, wie wir uns sonst auf diesem Handelsgesuchten Rechler eigentlich annehmen. Also, ressourcensparend ist er und er ist unglaublich schnell. Er geht hier Zeichen für Zeichen durch, braucht konstante Zeit für jedes Zeichen, weil alles, was hier passiert, ist einfach nur eine Zustandstransformation zu einem neuen Zustand, die einen Teil entlangt. Das geht schnell, in konstanter Zeit. Also brauche ich für n...

Eingabezeichen, brauche ich Laufzeit n. Und das ist optimal. Da gibt es nichts schneller. Und deswegen sind Automaten gut. Und deswegen sind Automaten recht einfach, auch von der Mächtigkeit her. Weil nicht alle Sprachen, nicht alle Probleme kann ich durch Automaten beschreiben. Sonst würde ich erwarten, dass alle Probleme in lineare Laufzeit zur Eingabe länger haben. Das ist halt leider nicht der Fall. Das hätten wir gerne. Aber ganz leid, dass es nicht so ist. Automaten sind gut, Automaten sind schön, wenn sie dort erstellt werden können. Aber wir möchten sie nicht händisch erstellen.

möchten sie durch reguläre Ausdrücke erstellen. Naja, zum Beispiel um noch irgendwelche SQL-Ansprache zu machen, auch dort gibt es regular Expressions oder Mustervergleiche, wenn jemand jetzt wirklich Word macht oder Grat oder hast ja nichts. Okay. Was sind denn jetzt eigentlich reguläre Ausdrücke? Naja, die definieren wir jetzt wirklich mal Induktiv oder anderswo auch dafür Dekursiv. Ist nichts anderes. Induktion ist nichts anderes als also wenn wir das in einem Grundwand anwenden, dann Rekursion, weil wir dann rekursiv in einen kleineren Teil reinsteigen.

Und hier starten wir jetzt mit den kleinsten regulären Ausdrucken, die es gibt. Das wäre eigentlich das leere Wort. Wir wollen auf Automaten hin, da sind wir wieder bei regulären Sprachen. Das Einfachste, was ich überhaupt machen kann, ist vielleicht das leere Wort anzufassen. Und dafür muss ich den Ausdruck machen. Also hier habe ich einen Ausdruck für das leere Wort. Ich brauche mal noch einen zweiten Ausdruck, und das ist dieser hier. Das ist der leere Ausdruck. Und zwar soll der für die leere Sprache stehen.

nicht das leere Wort, sondern die Sprache, die kein Wort enthält. Auch nicht das leere Wort. Eigentlich habe ich dafür doch diese Mengenklammer. Sonst hat man dafür doch immer, okay, ja, das ist hier die leere Sprache. Eine Abkürzung dafür war immer das Ding. Warum brauchen wir jetzt dieses Zeitsymbol dort oben? Weil wir haben für reguläre Ausdrücke leider keine Mengenklammern zur Verfügung. Deswegen können wir diesen auch gar nicht so hinschreiben.

Wir können den nicht vom leeren Wort unterscheiden, weil uns die Menge anbieten, die sind nicht erlaubt. Also brauchen wir für diese spezielle Menge, die nichts enthält, ein eigenes Symbol. Und das ist eben dieses, was wir da noch wissen, dieser Leereausdruck. Und ich möchte auch für jeden Buchstaben des Alphabetes, was hier hinter dem Grund steht, einen regulären Ausdruck definieren. Ich möchte sagen, jeder Buchstabe ist auch ein regulärer Ausdruck. Und das sind jetzt die wirklich kleinsten Teile, die man definieren kann, von regulären Ausdrücken. Also einmal der Grund, der Grund, der Grund, der Grund, der Grund.

Der leere Ausdruck, einmal das leere Wort, Epsilon, und einmal jeder Buchstabe des Alphabetes ist auch ein regulärer Ausdruck. Und jetzt kann ich zusammensetzen. Jetzt kommt die Induktion oder die Rekursion, wenn man das Algorithmus macht. Jetzt sage ich, okay, ich habe zwei reguläre Ausdrücke, die sind dann halt so atomar, wie ich jetzt hier definiert habe, und jetzt füge ich sie zusammen, um komplexe Objekte zu erstellen. Und die Frage ist nur, wie kann ich jetzt diese kleinen Ingenäuren Ausdrücke, die ich hier schon definiert habe, wirklich zusammen verschweißen. Wie geht das, auf welche Art und Weise?

Und das wird hier festgelegt, wenn x und y schon reguläre Ausdrücke sind, dann sind auch x plus y, wir machen dann technisch runde Klammern, damit die Klammer nicht so wichtig ist, reguläre Ausdrücke, andererseits auch hier x konkateniert y, ist auch ein regulärer Ausdruck, und auch die Potenz. Bis dann!

Es ist nur syntaktisch, wir wissen noch nicht, was das bedeutet. Aber so werden komplexe Regulier-Ausdrücke aus kleineren zusammengesetzt. Okay, und in dieser Reihenfolge findet auch die Spindungen der Klammern statt. Das heißt, dieser kleine Sternensatz am Ende, oder der Sternensatz am Ende, wird am stärksten abhinden. An der Klammern. Hier ist ein Beispiel. Wir haben wieder Datumsangaben, habt ihr da schon versucht zu motivieren. Könnt ihr so darstellen? Ihr habt dann wirklich die ersten zwei Ziffern als ein Alphabix-Symbol. Das ist 01 oder 02 oder 03 bis 31.

klar muss man dann gucken, auch konsistent, bei VV gibt es vielleicht nicht die 31, das ist zu kompliziert, aber zumindest so. Dann kommt ein Punkt, das ist auch ein Alphabetszeichen, die Klammerung gibt hier eigentlich nur an, dass wir von diesem 0,1, 0,2 und 0,3 jeweils nur 1 nehmen, das ist jetzt schon ein bisschen semantisch, das ist dieses Plus und als zweites Zeichen folgt dann irgendeine Zahl zwischen 0,1 und 12.

Das heißt, die Monatsangabe, da kommt ein Punkt und dann zwei Jahresziffer. Also hier könnte ich schon eine ganz elementäre Datumsangabe mit Schreien, mit diesen regulären Ausdrücken. Okay, und ein kleines Wort der Warnung ist, hier ist nichts standardisiert, leider bei dem Ausdrücken, was ein bisschen hakelig ist, weil jedes Tool wirklich eine andere Symbolik nutzt. Also statt Plus wird auch echt häufig dieser rettifende Schrift geschrieben.

aber ich wähle ich lesbar. Statt A Stern wird auch häufig dann das Stern nach unten gezogen und so ausgedrückt und statt A B wird auch A mal B häufig geschrieben. Je nachdem welches Tulip-Leute nutzt. Nur als Wort der Warnung. Wir werden auf jeden Fall der Lesbank der Fall bei den Klammern weglassen, wenn das überflüssig ist. Wenn ihr euch also diesen Aufzug hier links anseht, sieht der kompliziert aus. In der Mitte habe ich aber alle Klammern, die überflüssig sind, weil die Bindung E geordnet ist, weggelassen. Also zum Beispiel da vier Klammern.

1 plus 2 oder um 1 plus 2 herum, das ist ja so eine grüne Klammer, die kann weggelassen werden, weil danach wieder ein Plus folgt. Das Ganze hier unerheblich ist von der Reihenfolge, wenn ich eine Veroderung, die das hinterher meint habe, ob ich dann das 1 mit der 2 verodere oder die 2 mit dem da aufholenden Term. Ja und das Resultat sieht ihr dann ganz rechts, dass es ohne die überflüssigen Klammern, da ist ja noch eine Klammer übrig, die notwendig ist, damit das Stern sich nicht nur auf das y bezieht, sondern wirklich auf die gesamte Klammer.

Jetzt kommen wir zur Semantik, was soll das eigentlich ausdrücken? Heißt das plus wirklich oder? Und was heißen die anderen Sachen? Und dann kommen wir also zur Sprache, die dieser reguläre Ausdruck beschreibt. Wenn wir jetzt diesen Ausdruck der leer ist haben, dann soll das tatsächlich auch die leere Sprache beschreiben. Hier ist der Ausdruck, das ist dieses spezielle Zeichen. Das gibt mir die leere Sprache B.

leeren Mengeklammern. Ja? Als Sprachen. Sprachen sind ja eine Menge. Wenn ich als Ausdruck dieses Epsilon habe, dann ist eigentlich klar, was das dann soll. Das soll die Menge sein, die Sprache sein, die nur das leere Wort enthält. Das muss ja auch irgendwie abhängen können. Und hier noch immer bei den atomaren Sachen, wenn ich irgendwie nur einen Buchstaben habe, als leeren Ausdruck, dann sollen wir natürlich als Sprache auch wirklich nur diesen Buchstaben dort enthalten. die Zusammensetzungen, die

die die Semantik von den komplexen Ausdrücken wieder. Und hier bedeutet das plus dann das oder. Das ist so etwas wie die Vereinigung auf der Sprache. Also definiert ist es so, dass ich x plus y schreibe und in den Sprachen dann aber die Einzelsprachen nehme, und auch die Einzelsprachen von x. und die dann einfach vereinigen. Das ist eine Vereinigung. Oder, oder. Hier, beides war. Das heißt, ich kann jetzt wirklich 1 plus 2 nehmen.

oder 1 plus 2 nehmen und dann steht entweder dort das Wort 1 oder das Wort 2 und das ist meine Sprache, die dadurch erzeugt wird. Also Vereinigung. Und dieses hintereinander schreiben, naja, das heißt nicht anders, als dass ich die Sprachlänge von x, die Sprachen von x und die beiden hintereinander konkateniere. Wir kennen die Konkatenation von Sprachen ja. Und der Stern, oh Wunder, ist der kleine Stern.

dann nehme ich die Sprache von x und mache den kleinen Abschluss. Hier ist ein Beispiel. Wenn ich diesen Ausdruck habe, wählt ihr es noch eigentlich, weil das Licht wird heller. Okay, wenn es so stehen wird, sagt Bescheid, dann mache ich noch die Hänge runter. Das ist unser Ausdruck. Hier A plus 10 kann man mal 10 oder konkreten mit 10. Und L da drumherum meint, ich soll die Sprache angeben, die das meint. Wie das zu beurteilen.

So, gestrickt nach der Intervention der Semantik ist das aber leicht. Ich habe mir zwei Teile, einmal die Klammer und einmal das C und darauf kann ich es runterbrechen. Ich ziehe das L jetzt erstmal auf die Klammer zurück, konkontriere damit L von diesem zweiten Teil, genauso wie das hier bei der Konkontaktion definiert ist. So, das hier habe ich gerade als Analyse. Und jetzt kann ich auch die einzelnen Teile runterbrechen, fragen mich nicht, was ist ein L von A plus D? Naja, das kann ich wieder aufbrechen mit der Definition. Das ist die Vereinigung von...

Sprache von A, das ist A selber und der Sprache von B, das ist D selber. Also habe ich das Ding hier. Und LC ist automatisch, das ist einfach nur die Sprache, die C enthält. Deshalb ist C. Jetzt habt ihr zwei Sprachen ineinander geschrieben und ihr wisst, was das bedeutet. Konkretion von Sprachen hattet ihr ja schon in der zweiten Vorlesung. Hier wird jetzt einmal das C an das A drangehangen und einmal an das D und dann habt ihr halt final das D.

Satzsprache aus. Die beiden Wörter werden akzeptiert. Mit dem regulären Ausdruck.

Ich würde eigentlich noch etwas zeigen. Ich muss dann noch fragen, aber das ist ja okay. Schauen wir mal den Ausdruck. C, kontaktioniert, A plus B. Stern. Welche Sprache? Welche Sprache steckt da?

- Thank you.

Ich setze das jetzt auf.

- Yeah.

der kleine sterbe ist und endlich viele objekt hinzuschreiben

CA ist das auch drin.

And yet?

Den lässt sich dann nicht so, wenn man mit von der ...