Deterministische Automaten und reguläre Sprachen

Deterministische, etliche Automaten auf Deutsch. Auf Englisch steht ein Pass für Highlight von Thomas. Ich gebe es erst mal noch zu den Händen, was machen wir letzte Stunde? Macht noch Fragen? Okay, das ist nicht der Fall. Dann werden wir heute eine Verbindung von den etlichen Automaten kennenlernen zu den sogenannten regulären Sprachen, die wir auch schon kennen, weil wir die Chance, die wir euch hier kennen. Und die nächste Stunde werden wir tatsächlich noch was anderes, nämlich hätten wir ihre Ausdrücke kennenlernen, die ihr vielleicht auch schon mal gesehen habt.

Wenn ihr vielleicht Regular Expressions mal irgendwie eingegeben habt, unter Linux zum Beispiel, in Fahrerprogramm oder unter Bird gibt es sowas auch, dass man auf eine bestimmte Art und Weise Sachen ersetzt. Das wird dann auch mit den Regular Expressions gemacht. Das sind reguläre Ausdrücke, die wir in der nächsten Stunde auch kennenlernen. Auch die haben was mit diesen ähnlichen Automaten zu tun, die wir in der nächsten Stunde gelernt haben. Auch in der Praxis. Insofern fangen wir erstmal an.

dass eine Verbindung herrscht zwischen diesen endlichen Automaten, die ihr jetzt schon kennt, und diesen regulären Sprachen, die er hat. Und die Verbindung ist erstmal, und wir beweisen das jetzt auch, keine Angst vor dem Wort beweis, dass jeder endliche Automat eine reguläre Sprache akzeptiert. Das heißt, das, was die endlichen Automaten akzeptieren, das was sie berechnen können. Das ist nicht mehr wert,

Nicht mächtiger, nicht uneinsichtiger für eine Maschine als eine reguläre Sprache. Jede akzeptierte Sprache eines sämtlichen Automaten ist so einfach, dass sie eine reguläre Sprache ist. Und sie ist nicht komplizierter als eine reguläre Sprache. Das sagt dieser Verweis jetzt hier. Das ist die Aussage. Und das soll man natürlich beweisen. Die sämtliche Automate ist natürlich so, wie man ihn auch kennt. Hat hier diese Zustandsmenge, hat ein Alphabet, hat ein Startsymbol, eine akzeptierende Zustandsmenge und natürlich die Zustandsübergangsfunktion, Delta.

Und ja, jetzt ist natürlich die Frage erstmal so generell, wie können wir so ein wirklich generelles Resultat überhaupt beweisen? Wir wissen ja nicht, wie das eigentlich auch so mal aussieht. Es ist völlig beliebig. Und dadurch, dass es also völlig beliebig ist, macht es das uns schwer, Sachen darüber zu beweisen, was wir nicht konkret kennen. Aber es stimmt nicht ganz, weil wir wissen, wie ein Endschlag auch normal definiert ist und das allein reicht uns. diesen Beweis zu führen,

alles was dort akzeptiert werden kann von diesem Automaten, hat eben nicht allzu mächtig ist, sondern in der Chomsky-Chierarchie ganz unten auf Typ 3. Hier ist ein Beispiel dafür, links ist der ähnliche Automat, das Alphabet ist jetzt A, B. Die Zustandsmengen seht ihr auch, fängt natürlich mit dem Startzustand von 0 und ist aber noch auf zwei weiteren Zuständen, Groß A, Groß B. Wir nennen das die Maschine M, aber sie ist nur ein Beispiel. Wir möchten das über alle Maschinen M hier gerade führen.

Nicht nur über dieses Beispiel, aber wenn wir uns auf das Beispiel konzentrieren, würde das vielleicht eine Dramatik ergeben, die tatsächlich regulär ist. Und damit auch eine reguläre Sprache erzeugen, nämlich die, die ihr auf der rechten Seite seht. Und ihr seht vielleicht ein paar Parallelen dazwischen. Ihr seht zum Beispiel, dass wir hier links auf der Maschinenseite anfangen mit einem speziellen Zustand, nämlich dem Zustand von Null. Ja, ist ja immer so. Aber das ist...

Nicht nur beim Beispiel, sondern bei allen ähnlichen Automaten. Und auf der anderen Seite, auf der Grammatikseite, fangen wir auch immer an mit einem speziellen Symbol, nämlich dem Staatssymbol S. Und da haben wir schon unseren ersten Einflugspunkt gefunden, was wir in diesen beiden Welten miteinander vereinen können. Was in der einen Welt, einem Objekt, entspricht in der anderen Welt. Nämlich Q0 entspricht hier einfach dem Staatszustand S. Wahrscheinlich auch umgekehrt, wenn man diese beiden Wänden nochmal zurückführen wollte und hinterher noch

dass die regulären Sprachen tatsächlich alles sind, was WEA ist. Dass die WEA auch nicht mehr können als reguläre Sprachen und umgekehrt, dass die regulären Sprachen auch genau von WEA auch wirklich akzeptiert werden. So, gibt es noch mehr Parallelen? Erstmal, bevor wir jetzt in den Beweis entsteigen. Seht ihr noch irgendwelche Parallelen zwischen endlichen Automaten und Grammatik?

Ich würde sagen, dass der akzeptierende Zustand immer auf das leere Adoption geht. Ja, das ist eine gute Idee, denn hier kann ich ja gar nicht aufhören. Wenn ich ein Wortwetraglich ableite in der Grammatik, dann muss das mit nur Terminalen. Es darf kein Nicht-Terminal dabei sein. Das heißt, alle Nicht-Terminalen, die dort erzeugt werden, wie zum Beispiel Groß-B hier bei dieser Ableitung,

müssen irgendwann herausgeklickt werden. Wie mache ich das? Ich habe keine Wahl. Wenn ich jetzt B wieder ableite zu B, Groß B, dann ist das Groß B wieder drin. Ich habe keine Wahl, außer dass ich irgendwann das Epsilon annehmen muss, dass das abgelandet wird, um dieses V-Terminal wegzukriegen. Sonst kann ich nicht nur Terminale übrig behalten. Also, stimmt, mit dem Epsilon auf der Grammatikseite schließe ich ein Wort dann ab, Kann es zumindest abschließen.

Und ja, was entspricht dem jetzt nochmal auf die Maschinenseite? Also du hast gesagt, hier auch irgendwie das, also was meinst du, das entspricht dem auf der Maschinenseite? Einmal, der Pfeil A, ist das ein Delta? Also der Übergang-Funktion? Ja, aber der bestreibt ja alle Pfeile, oder? Ja, aber wir können ja überall anhalten. Also wir sehen schon, dass ihr es irgendwie kompliziert habt. Ja, ich mache das wegen, weil...

Also rechts auf der Grammatikseite kann man mit dem Epsilon gut bestimmen, wann das Wort wirklich aufhört. Ja, ich würde sagen, es ist leicht, dass ich immer noch von einem Zustand, also da es sein, nicht Terminal, auf beiden Sprachen, weil auch mal ein Zustand, mit Hilfe von einem Terminal, beziehungsweise einem Welter, entweder zu einem Weitungszustand gehe oder zu einem Lerbevor. Und wenn ich jetzt ein Lerbevorstehe, dann könnte das ein Akkultiererzustand sein.

Wenn wir nur das leere Wort als Eingabe haben, wenn nur das leere Wort abgeleitet werden soll, dann wird B, groß B, hat Exel abgeleitet, wenn nur eine Regel an. Das würde jetzt entsprechend, Moment, das würde jetzt entsprechend hier diesen echten Automaten, dass wir wirklich hier in dem Zustand von unserem Anfang und gar nichts lesen. Wir haben das leere Wort als Eingabe. Da haben wir uns die Autobahn nachzudenken. Und wenn wir das leere Wort als Eingabe haben, dann kommt gar kein Buchstabe rein. Der Automat bewegt sich überhaupt nicht, weil er gar kein nächstes Zeichen mehr lesen kann.

Das ist ja das leere Wort als Eingabe, wo kein Zeichen drin ist. Also verbleibt der automatischen Zustand von 0 und das ist auch gleichzeitig ein Zustand. Da haben wir zumindest mal eine Position gefunden, wo wir eine Äquivalenz haben. Wenn wir hier mit Epsilon nach Epsilon abbleiben, bleiben wir hier auf der Maschinenseite einmal bei 0 stehen. Und jetzt müssen wir aber gucken, wenn hier wirklich wie ein Beispiel Epsilon abgeleitet werden kann. Von dem Startsymbol zum Beispiel, das ist jetzt hier in der Grammatik nicht so. Dann wäre ja nur das leere Wort in der Sprache drin.

dann muss hier auf der Maschinenseite auch dieser Zustand, in dem wir ja bleiben, akzeptieren sein. Wenn nur dann ist Epsilon rechts in der Grammatik drin, kann abgeleitet werden, und gleichzeitig auch links in dem Automaten akzeptieren. Muss ja weitseitig das Wort Epsilon dann in der Sprache sein, die jeweils generiert wird. Hier ist das aber tatsächlich nicht der Fall, aber zum Glück auf beiden Welten nicht, weil S nicht nach Epsilon abzuleiten wird, wie er es kann. Also das Lehrerwort ist hier nicht drin. Ja.

Auf der anderen Seite ist das auch nicht so drin, hier in der Maschinensicht, weil von 0 eben kein Doppelkängel hat und nicht akzeptiert ist. Zum Glück sind wir hier wieder auf derselben Seite, Y ist in beiden herrlichen Sprachen nicht drin. Insofern ist es ein lieb dafür, dass diese Sprachen tatsächlich reißen, die wir hier in dem Beispiel erzeugen. Und jetzt steigen wir mal ein in den Beweis, wir wollen, also diese Maschine ist gegeben, dieser Endliche Automat und wir wollen daraus jetzt eine Dramatik generieren.

Ich sage euch jetzt erstmal, wie die Grammatik aussieht, wie wir generieren. Das ist dann sehr, sehr festgelegt, da muss man natürlich sehr, sehr genau sein. Hinterher muss man zu beweisen, dass das auch wirklich dieselben Wörter generiert. Dass dieselben Wörter in der Grammatik abgeleitet werden können, die von dem endlichen Automaten akzeptiert werden. Nur genau die. So, und das, was wir jetzt irgendwie schon gesehen haben, das wenden wir direkt an. Dann hat das Startsymbol von Null, auf der Maschinenlicht sollte hier in der erstellenden Grammatik das Startsymbol S sein. Das ist der Anfang. Das heißt, ich eröffne.

Wir stellen das jetzt so, dass hier die Grammatik S besteht natürlich aus den ganzen Zustand, die wir hatten, aber das Startsymbol ist einfach das Symbol Q0, derselbe Start sozusagen. Bei der Zustandsmeter, naja, müssen wir mal überlegen, der Automat springt hin und her von Zustand zu Zustand, und liest jeweils ein Zeichen. Das Zeichen steuert sozusagen, zu welchem Zustand wir danach kommen. Das Zeichen, das wir lesen und der Zustände, in dem wir aktuell sind, steuert.

in welchem Zustand wir kommen. Wenn wir hier jetzt das A lesen, gehen wir hier also in einen Zustand bei dem in den Kuhn 0 sind, gehen wir in den Zustand A über, Großteil. Was könnte dem auf der Dramatikseite entsprechen? Naja, ich starte hier nicht mit Kuhn 0, sondern mit S. Das Lesen des Buchstaben A wird durch eine Ableitung natürlich irgendwo abgebildet werden müssen. Also gucke ich mal, diese Regel nutze ich nicht, weil da kommt das Terminal B vor. Aber das ist nicht das Zeichen, das ich lese.

Also nehme ich doch lieber die Regel, die ich hier nach A ableiten kann. Eine andere Regel gibt es auch nicht. Dann habe ich das kleine A als Terminal dort stehen. Und dann bin ich in einem, naja, anderen Zustand. Eigentlich hier auf der Maschinensicht. Aber auf der Grammatikseite müsste ich den Zustand dann als Nicht-Terminal schreiben. Zustände auf dieser Automatensicht sind also nichts anderes als Nicht-Terminale in der Grammatik. Zustände? Nichts.

Und deswegen setze ich die Nicht-Terminale auch wirklich genau auf die Zustandsmethode. Das ist dieselbe Menge, da stecken dieselben Zustände hinter, also hier, Groß A, findet die auch hier. Das ist einfach die Menge der Nicht-Terminale. Wenn ich jetzt weitergehe und hier bin in dem Zustand und dann die kleinen Buchstaben B lese, würde ich in den nächsten Zustand, der durch die Maschine determiniert, festgelegt ist, kommt also hier in Groß B. Ja, da muss ich halt hier eine Regel aufstellen, dass ich von dem Zustand A, das ist

ja meine Nicht-Terminal-Galde in der Grammatik-Sicht, durch Lesen des Buchstaben b zu diesem neuen Nicht-Terminal b auch komme, also habe ich hier auch b b stehen. Jegliche Übergangstransition, die ihr habt in Delta, entspricht dann einer Regel, die ihr erstellt für die Grammatik. Und so könnt ihr den Automaten auf der linken Seite simulieren, in dem ihr Regeln auf der rechten Seite ausführen. Schritt für Schritt. Ein Zustandsübergang aus der Automatensicht ist nichts anders als eine Regel, die ihr auswirkt.

der Dramatik. Das ist die Hauptidee des ganzen Beweises und auch der Grund, warum jetzt die Terminale gleich der Zustandsmenge gleich ist. Okay und das was ich jetzt gesagt habe von der Idee, das machen wir jetzt nochmal ein bisschen formal. Wir gehen langsam durch. Wir stellen jetzt die Wir legen konkret auf. Und zwar nach der Maschine, die uns vorliegt.

Das erste was ich mache ist, dass ich hier gerade motiviert habe, wir hören immer dann in der Grammatik-Sicht auch mit dem Exilon, ableiten, weil dann haben wir kein Nicht-Triminal mehr. Dann ist das Wort vollendet und wir sind mit dem Wort in der Sprache drin. Wir haben ein Wort abgeleitet. Und das möchte ich natürlich nur dann machen, wenn das Wort auch wirklich in der Sprache des Automatenkennels, wenn das Wort also akzeptiert wird. Man wird ja im Wort akzeptiert, naja, wenn ich einen Doppelkennel habe. Das heißt immer dann, wenn mein b, mein Zustand in der Automatensicht in Groß F ist, der Menge der akzeptierenden Zustände, wenn mein Zustand groß wie gerade einen Doppelkennel also hat,

dann möchte ich auch zulassen auf der Grammatik, dass ich hier groß D auch ableite nach Epsilon. Damit das Wort vollendet werden kann und dann auch in der abgeleiteten Sprache der Grammatik ist. Und wenn nicht, dann eben nicht. Bei Q0 ist das Wort ja nicht akzeptierend, also habe ich hier auf der Q0-Regelseite nicht das Epsilon mitgegeben, weil ich dann auch sonst das Epsilon in der Sprache hätte, auch wenn er automatisch akzeptiert ist Epsilon. Dann würde er dann fehlbar aufregen und ich würde eine andere Sprache mitgegeben.

Darf ich aber nicht, ich möchte genau die gleiche Sprache finden. Also fehlt hier oben das Epsilon. So, und das mache ich natürlich auch für jeden akzeptierenden Zustand. Für jeden akzeptierenden Füge ich dann die Regel B mit abgeleiteten Epsilon zu. Genau dann halt wenn B in der Menge F der akzeptierenden Zustand. Das war die erste Idee, die wir hatten. Die zweite Idee war, jeder Zustandsübergang entspricht einer Regelanwendung der Grammatik. Und das habe ich mir hier nur mal aufgespielt. Das ist nichts anderes als

genau diese Idee. Sieht ein bisschen formaler aus, wir kämpfen uns da durch. Wenn ich hier einen Zustand B, Groß B habe, ihr könnt jetzt ruhig auch wieder hier dieses Groß B nehmen, auf der Maschinenseche, und ein Zeichen A, zum Beispiel dieses hier, was ich gerade lese, dann sagt die Maschine ja, okay, mein Folgezustand ist jetzt dieser. Wer das ist, weiß ich nicht. Wie der heißt, weiß ich nicht, aber ich kann es ausdrücken. Das ist Delta von W A. Das

Das ist der Folgezustand. In dem Fall, wo ich hier wirklich B und A nehme, ist mein Folgezustand der, den ich kriege, wenn ich diesen Teil entlang gehe, also Groß B. Hier können Sie ihn komplett hinschreiben, aber das will ich nicht, weil ich ihn generell ein Beweis für mich. Also schreibe ich hier Delta von B A hin, das ist der Folgezustand. Und jetzt nehme ich die Regel auf in die Dramatik, die da sagt, ich starte mit B, die ist nicht terminal, ich lese das Wort A, das heißt, mein Terminal, mein erstes ist A, ihr erinnert euch, die regulären Dramatiken sind so aufgebaut, dass sie erst ein Terminal auf der rechten Seite haben, dann ein groß geschriebenes Litterminal, das ist ein Terminal.

Das Großgeschriebene nicht erkannt ist genau dieser Folgezustand, den ich damit ausdrücke. Und jetzt habe ich genau diesen Zustandsübergang, das von B über das Lesen des Zeichens A übergegangen wird, wieder in den Folgezustand B ausgedrückt mit genau dieser Einregel. Und genau das, was mit dem Automaten möglich ist, kann ich jetzt auf der Dramatik-Sicht durch Anwendung dieser Einregel auch machen. Und das Schöne ist, das funktioniert für jede Regel. Ich muss das nicht konkret für dieses Großgeber machen, Ich mache das für jedes B aus der Zustandsmengel.

Also auch für dieses Plus A, auch für dieses Q0, wenn ich das Teil B lese. Und, naja, halt auch jedes Zeichen A generell, was ich lese und wir stellen dann hier dann diese Regel. Und das ist die ganze Definition der Dramatik erstmal. Das ist jetzt wohl definiert, dass wenn ich jetzt den Auton haben, mir diese Dramatik von B erstellt. Und für jeden Zustandsübergang hier habe ich hier eine Regelanwendung dort. Für jeden akzeptierenden Zustand auf der linken Seite habe ich auch eine Epsilon-Regel auf der Dramatik-Seite.

Und jetzt könnte man sich fragen, okay, das ist aber ein bisschen komisch, weil das, was ich jetzt eigentlich erstelle, ist zwar eine reguläre Grammatik, ihr seht das ja auch, ja, hier steht immer auf der rechten Seite ein Terminal, gefolgt von einem Nicht-Terminal, aber es kommt ein bisschen aus, noch mit weniger Regeln. Wir haben zum Beispiel nicht mehr die Regel, wie rechts nur ein Terminal steht.

nutzen wir dann. Die vermeiden wir komplett. Ist das also noch irgendwie kosher hier? Ist das noch korrekt? Ja, ist es. Weil, wenn ihr so eine Regel habt, wie B abgeleitet nach A zu einem einzigen Terminal, dann könnt ihr natürlich auch eure nicht Terminalmenge erweitern, sagen wir mal durch diesen Buchstaben Z, die

Regel aufstellen, dass b nach a z ableitet. Z ist jetzt wirklich ein neuer Buchstabe, der noch nicht benutzt ist, das ist natürlich wichtig, sonst gibt es Verwirkungen mit den übrigen Regeln, die er hat in der Mathe. Und jetzt habe ich noch meinen zweiten Typ Regeln, z wird abgeleitet nach Epsilon, den erlaube ich nach wie vor, den nutze ich ja auch hier in dieser akzeptierenden Zustandstattung um die Epsilon-Typen. Und ihr seht, dass bei z mir so anders vorkommt, muss ich ja das I-Terminal z irgendwann ableiten. Es kann nur durch diese einzige Regel abgeleitet werden, weil z nun hier vorkommt, auf der linken Seite, dann wird es also notwendig bei Epsilon abgeleitet. In der Suche habe ich genau das, was vorhin erzeugt werden konnte, genau wieder erzeugt.

Ich verändere das. Insofern sind solche Typen von Regeln in der regulären Grammatik eigentlich redundant. Wir können ohne diese auskommen. Es gibt viele, viele redundante und alternativen Formulierungen von regulären Sprachen, auch von Perfekt-Pensitiven und so weiter. Ihr findet im Netz also wirklich bestimmte verschiedene Definitionen von regulären Sprachen oder anderen Elementen in der Choms-Liegerhie. Und dieser Beweis hat uns gerade, ja, wir kommen ohne diesen Typ aus. Nur diese beiden sind wichtig.

Und das nehmen wir einfach mal so mit, weil wir können jetzt auch mit dieser ganzen Konstruktionen ziemlich easy auch diesen Regeltyp natürlich vermeiden. Ist aber erstmal auch ganz wichtig zu wissen, ja, keine rechte Seite besteht aus genau einem Terminal. Ja, brauchen wir auch gleich noch. Einfach durch diese Erzeugung. Jeder sieht schon einen Beweis. Was weint ihr? Sind wir fertig mit dem Ding? Ja. Ist B hier jetzt nicht nur auf den einen Automaten zu tun?

Nein, das ist mein Sprungpunkt. Hier steht für jedes B aus Q. Das heißt, es ist ganz generell für jeden Zustand, den ich jetzt mal B nenne, nenne ich diese Länge. Das ist ganz generell. Das ist auch nicht so ein Beispiel, braucht ihr für eure Motivation, für die Ansicht, um etwas auszuprobieren an diesem ähnlichen Automaten. Aber bitte versteht und überzeugt euch, dass all das, was hier in dem Beweis steht, verfolgt.

komplett generell ist und nicht die Beispiel-Dramatik oben überhaupt eingeht. Ja, hier steht nur: Jeder Zustand b aus q. Dafür habe ich ja etwas. Für jedes b aus erklärt man die Zustandsfänge, das ist für jedes. Okay, aber ist es ein Beweis bis jetzt? Bin ja, warum nicht? Naja, wir haben ja jetzt quasi nur gewiesen, dass jeder determinist geschäftliche Automat eine literarische Sprache.

nicht, dass jeder Regulierer und den Regulierer scheinen hier auch gemacht wird. Das machen wir hier auch gar nicht. Das möchten wir am Ende der Vorlesung vielleicht noch schaffen. Ich möchte wirklich nur die eine Richtung gerade beweisen. Aber wer es abwärtsbeweist bis jetzt, was habe ich denn gemacht bis jetzt? Ich habe nur gesagt und festgelegt, wie ihr diese Regeln erstellen sollt, wenn ihr den Automaten habt. Mehr nicht. Der Automat steht dort, dann habe ich festgelegt, Hier ist die Regelung.

aber auch noch nicht gezeigt, dass ein Wort, was hier im Automaten akzeptiert wird, auch wirklich hier dann in der Grammatik drin ist und abgeleitet werden kann. Ich habe es motiviert, anhand des Beispiels, aber von diesen habe ich das nicht. Vor allem habe ich auch noch nicht gezeigt, dass jedes Wort, was in der Grammatik abgeleitet werden kann, auch wirklich in den Automaten akzeptiert wird. Das habe ich auch nicht gezeigt. Da müssen wir noch mal durchgehen, dass die Sprachen, die erzeugt werden, die Sprache, die hier von Automaten

die Sprache, die hier von der Grammatik abgeleitet wird, also erkannt, generiert wird, dass die dieselben Sprachen sind. Ansonsten löst mir die Grammatik ein anderes Problem als die ähnliche Automaten. Und das möchte ich natürlich machen, dass die beiden dieselben Probleme, dieselben Sprachen setzen. Und das mache ich jetzt. Ich möchte beweisen, und das ist jetzt nur Definition, wie ich die Grammatik aufstelle,

Motivation hat, deswegen warum ich das so tue. Aber jetzt kommt dann der Beweis, dass wirklich die generierte Sprache von der Dramatik hier die gleiche ist, die der Automat M akzeptiert ist. Und ich kann das so einfach als Gleichung schreiben, weil wir das hatten. L von M ist die Sprache, die durch dem Automaten akzeptiert wird und L von G ist die Sprache, die durch die Dramatik abgedeckt wird. Ja. Ich wollte noch fragen, hätte man für D auch allgemein ein Entwettnis-Einerschein? Nein, das muss man gleich machen. Nein, weil die Länder alle nicht kennen. Das ist ja nicht.

eine Menge aller Nicht-Terminalen. Ihr müsst hier diese N und diese Qs, die hier vorkommen, die sind euch verkannt. Die kommen natürlich hier oben schon ganz vor. Q ist hier die Zustandsmengel. Ihr wisst, dass die verschieden sein muss von der Menge des Alphabets zum Beispiel. Und N hier ist dann die Menge der Nicht-Terminalen, die wir erstellt haben. Wie habe ich es erstellt?

indem ich einfach gesagt habe, N ist gleich die Menge der Zustände. Die habe ich hier definiert. Okay, aber warum sind jetzt diese beiden Sprachen gleich und wie können wir das zeigen? Das ist der eigentliche Verweißkerl. Und auch das ist nicht schwierig, wir müssen einfach nur durchgehen. Wie beweist man eine Gleichung zwischen Mengen? Wie beweist ich, dass zwei Mengen X und Y gleich sind?

Ja, beide sind jeweils drei Mengen. Genau, Gleichheit unter Mengen beweisen wir in dem Jahr zwei Sachen zu sein. Einmal das hier, jetzt das geteilt in den Korinpsen und einmal das hier. Richtig. Und genau so machen wir es jetzt auch. Wir machen jetzt die eine Richtung, dann die andere Richtung und dann wissen wir, beide Mengen sind gleich. So, als Sprachen, sie erzeugen dieselben Wörter oder akzeptieren dieselben Wörter. Also habe ich genau mein Problem auf der einen Seite wie auf der anderen. Ja, und dann geht es nicht.

Okay, machen wir mal die eine Seite. Hier fange ich an mit dem, was durch die Maschine akzeptiert wird. Also hier stecken Wörter drin, die akzeptiert werden von der Maschine. Ich vermengte es genau so mal. Ich nehme mir jetzt in Gedank, ich nehme mir ein Wort dort aus. Weil diese Teilnehmens hier, kann man auch nochmal aufgrösen. Wie zeige ich denn das hier? Das zeigt, indem ich ein Wort hier aus der Menge rausnehme, also W-Elemente. Und dann zeige, dass dieses W auch tatsächlich in Groß-Y ist.

Das muss ich machen. Und bedanklich mache ich das für diese Timing-Beziehung. Ich nehme jetzt ein Wort heraus, was wirklich vom Automaten akzeptiert wird und muss zeigen, dass das dann auch in der Sprache drin ist, die die Grammatik generiert. Okay, dann muss ich es benennen. Sagen wir mal hier, dieses Wort B ist akzeptiert von dem Automaten. Dann schreibe ich das mal etwas,

So ein Wort W besteht aus einzelnen Zeichen, nur dass ihr da nicht durcheinander kommt, dass das W ein einzelner Buchstabe ist. Das ist das generell. Es besteht aus vielleicht N Buchstaben. Dann habe ich N Buchstaben, jetzt kann ich ein bisschen darüber reden, was der Automat dort als Buchstaben hintereinander liest. In welche Zustände er herangeht. Ich weiß auf jeden Fall, dass dieses Wort W in der Sprache des Automaten drin ist, das heißt vom Automaten akzeptiert. Frau Obenbach, danke dir.

Und damit weiß ich auch nach Definition, was das, wann der Akzeptanz eines Automaten, weiß ich, dass hier eine Berechnung existiert. Eine Berechnung des Automaten, die eine Zustandsfolge gibt, die der Automat durchgeht, bis er irgendwann an einem akzeptierenden Zustand steht. Insbesondere wisst ihr, dass der letzte Zustand, den ihr erreicht, wenn ihr hier in diesem Zustand die Q0, bis danach, naja, wenn wir N-Buchstaben haben, dann haben wir halt N plus 1 Zustände, also insgesamt, wenn wir bei 0 anfangen, hört ich bei Qn auf.

Qn ist mein letzter Zustand der Berechnung des Automaten. Von Q0 komme ich durch Lesen des Zustands W1 nach Q1. Und so weiter und so weiter. Beim Lesen des Zustands Wn bin ich immer im Zustand Qn. Und dadurch, dass das akzeptierend ist, heißt das jetzt nicht anders, als dass dieser Zustand Qn in Großstelle sein muss. Weiß ich, weil das Wort akzeptiert wird. Also muss der letzte Zustand, zum Beispiel hier dieses bei Wort AB,

Wenn ihr euch das Wort AB anguckt, akzeptieren soll. Wenn ihr das kann echt schnell hochgucken, aber wenn ihr jetzt klein A mal liest, dann seid ihr im Zustand Groß A. Wenn ihr dann klein B liest, seid ihr zwangsläufig im Zustand Groß B und ihr seht, da ist die Doppelung. Also akzeptieren. Deswegen wird dieses Wort AB akzeptiert, deswegen ist das Wort AB auch in der Sprache gesprungen. Also, ähm...

Der letzte Zustand, den wir hier durchgehen, ist, der erste war Q0, dann war A der zweite und der letzte war B. B ist damit N F. Muss ja so sein. Und generell kann ich das auch folgen. Wir wissen also, Qn ist N F. Okay. Wenn Qn in den Groß F drin ist, dann habe ich ja gerade meine Dramatik auf eine spezielle Art und Weise erzeugt. Nämlich so, dass alle, die im Groß F drin sind,

eine Epsilon-Regel erzeugen. Weil Qn die Groß F drin ist, existiert auch so eine Regel, Qn leitet nach Epsilon. Ich möchte die Definition der Dramatik nicht erstellen. Da steht ja drin, Qn muss abgeleitet werden. Okay. Kann mich auch daraus folgern. Und weil ich das jetzt habe, weiß ich, dass ich jeden Zustandsübergang, der hier stattfand, von Qn Bei dem ist das Ampel 1 A, bin ich ja ein großer Einfrau, dass ich das in Zuständigkeit habe.

dass ich den jetzt durch diese Regeln auf der Grammatikseite ausführen kann. Sprich, bei dem Beispiel würde ich jetzt hier mit S anfangen, mit Q0. Ich bin jetzt auf der rechten Seite, ja, S. Ich würde den Buchstaben klein a lesen, das heißt, es muss hier eine Grammatik erstellt worden sein, die mit klein a anfängt. Und weil hier die Maschine auch groß a irgendwie abgebildet hat, gibt es auch noch Dinge, die nach Groß A übergeht.

Da gibt es auch ganz rechts rum. Super. Ganz gut, passt. Weil die Maschine bis hier Groß A hingekommen ist, kann man per Regelzeit auch diese Regeln jetzt anwenden. Es bleibt eigentlich hier nur nach Üblich, das ist nämlich Groß A und damit weiter. Bei Groß A gibt es auch wieder, weil Zuständigkeit bei der Regel nach Groß A steht, gibt sie dann eine Regel, die nach Groß A steht. Bei Babys, also so raus. Ah, das sollte man Zeitung sein. Also kann ich jeden Zustandsübergang, den ich habe auf der Maschine, sich natürlich auch durch die Regel, auch hier ganz generell, durch das, was hier jetzt gelbmachtiert ist,

ausführen und ableiten. Und dann bin ich hinterher bei Groß B. Und jetzt weiß ich aber, da habe ich ja gerade gezeigt, dass Groß B in der Menge der Aztapiener-Zubstent ist, also auch hier eine Regel da sein muss, B leitet ab Epsilon ab. Und die wende ich jetzt an. Und dann bleibt von diesem Groß B nur noch B übrig. Hier von dem Ding weiß ich dann,

dass ich dann hier das A mit N nach B ableiten kann. Und dann kann ich also von S ableiten nach AB. Und habe auch das Wort AB erzeugt in der Grammatik. Durch eine Ableitung. Sprich, wenn AB akzeptiert werden kann in der Automaten, kann es auch in der Grammatik abgedeilt werden. Und das habe ich jetzt ganz gerne in der Zeit. Mit dieser Einzelschrift. Okay. War eine Hitzung? Ja, der SQL nennt man in einem Zustand oder? Ja.

Was ist ein echte Zustand? Da, wo man hier noch letzte Mal nach der Seite hat. Jetzt hier ja. Hier tatsächlich ja. Auf der Maschinensicht meint ihr, dass der Zustand der letzte, der erreicht wird. Der Maschinen. Genau. Ist es immer, weil ich habe hier ein Eingabe-Wort und ich nehme an, dass es akzeptiert wird von dem Automaten. Und wenn es akzeptiert wird, endet dieses Wort ja auf einem Buchstaben.

sodass die Berechnung, die dahinter steckt, geht dann anders aus. Wenn ich dieses Wort reinlege und es akzeptiert wird, dann habe ich eine Zustandsfolge, nämlich die Berechnung des Automaten, die nach Lesen von Wn mir in einem Zustand endet. Den Zustand meint sogar in der Zustand. Und dieser Zustand muss akzeptierend sein, weil das Wort hat akzeptiert. Genau das, deswegen höre ich damit auf. Ja, und dieser Zustand ist jetzt auf jeden Fall Wn, weil ich ja nicht mehr lese im Automaten. Im Automaten geht ja von links nach rechts vor und liest immer Zeichen, liest immer Zeichen.

weswegen kein Zeichen mehr da ist. Wn ist immer der Buchstabe, den ich lese, bevor ich in den Endzustand komme. Das ist also die letzte Transition in einer Art Automatensicht. Zumindest Qn ist der Endzustand, oder? Genau, Qn ist der Endzustand, Wn ist das letzte Zeichen, was ich in der letzten Transition lese. Also, was ich lese, bevor ich in den Endzustand Qn komme. Okay, jetzt haben wir den Wirtel. Also, Qn ist der letzte Zustand, also hier wäre B, wo ist B, der letzte Endzustand.

Und das W, das letzte Zeichen, das ich lese, wäre hier klein. Ja, okay. Gut, sind wir jetzt fertig? Nein, immer nicht. Ich habe ja nur eine kleine Zeichen gezeigt. Das ist jetzt ja nur, dass die Automatensprache wirklich in der Grammatensprache drin ist, weil ich habe gezeigt, jedes Wort hier, das Wort ab, was akzeptiert wird im Automatum,

ist auch ableitbar in der Grammatik. Es könnte sein, dass die Grammatik aber viel, viel mehr Wörter ableitbar lässt. Dass nicht nur AB, sondern auch A, B, A, keine Ahnung, oder so drin ist. Das aber dann nicht im Automaten akzeptiert. Dann wären die Sprachen auch noch nicht klar. Also muss ich die anderen Teilnehmern natürlich auch noch durchgehen. Und das läuft so ähnlich. Ich habe mich tatsächlich gefragt, in der ersten Iteration zur Vorlesung habe ich das gar nicht hingestellt. Weil ich, ich habe nur gesagt, dass es dann genau so läuft, aber nach dem Thema...

weil es ja anfangen, jetzt machen wir es nochmal konkret. Jetzt starte ich nicht mit der Automatensicht. Jetzt starte ich hier mit LB, mit der Grammatik, die ich dort stehen habe und generiert habe. Die leitet eine Menge von Wörtern ab. Das ist die Sprache, die durch diese Grammatik generiert wird. Für jedes generierte Wort dieser Grammatik muss ich jetzt nachweisen, dass das auch akzeptiert wird in der Automatensicht. Jetzt also davon was, dass das Wort aus der Grammatik ist.

muss zeigen, dass es auch vom Automaten akzeptiert wird. Okay, dann stellt euch vor, ihr habt ein Wort, was in der Grammatik-Sicht "ableitbar" ist, abgeleitet werden kann. Das ist das richtige Wort. Dann existiert eine Mehrstellerableitung von S aus zu diesem Wort B. Ich kenne sie nicht ganz, welche Zustände dort, also welche Richttermine dort vorkommen.

Aber mein Wort W besteht aus Buchstaben. Und die, weiß ich, müssen irgendwo als Terminale erzeugt worden sein durch die Grammatik. Also steht irgendwo in der Regel, vielleicht in der ersten Einschritt-Ableitung, dieser Mehrschritt-Ableitung, steht W1 drin, dann wird W1 genannt. Ich weiß auch mit der Motivation, dass eine Grammatik von links nach rechts vorgeht, also auch, dass W1 wirklich hier der erste Buchstabe ist. Und irgendwann kommt danach W1, W2, nach der zweiten Einschritt-Ableitung, und irgendwann hat sich das ganze Wort W1 bis Wn erstellt.

Dann ist nur noch das letzte Nicht-Terminal übrig, weil ich weiß ja, in der Erzeugung besteht keine rechte Seite aus genau einem Terminal. Das ist jetzt auch. Dann sage ich noch irgendwie, das letzte Nicht-Terminal, Qn-Dort, entspricht dann dem letzten Zustand auf der Maschinensicht. Das ist ja gerade hier zu Qn hingeschrieben. Und das wird dann zu Epsilon abgeleitet. Muss ja, ansonsten würde ich das Wort nicht ableiten können. Das heißt, das impliziert allein schon, dass ich in der Grammatik dieses Wort W ableiten kann, dass das letzte Nicht-Terminal Qn nach Epsilon ableiten kann.

ist aber gleichzeitig ein Zustand in der Maschine. Und es ist nur deswegen in der Dramatik drin, weil dieser Zustand in der Maschine, hier wird der D genannt, akzeptieren war in Groß-F. Das heißt, ich ziehe daraus schon, dass hier Qn, der letzte Zustand in der Maschinensicht, akzeptieren war. Das ist gut, weil jetzt weiß ich, auf der Maschinensicht, auf der Automatensicht, akzeptiert.

Automat dieses Wort. Zumindest der letzte Zustand, den ich erreichere, ist akzeptiert. Das weiß ich. Aber ich weiß noch ein bisschen mehr, denn ich kann natürlich jede Einschnittableitung auch wieder umändern, nach Konstruktion hier, zu genau der Transition, die der Automat ausführt. Also wenn hier steht, S wird abgeleitet nach W1 Q1, dann weiß ich hier auch, dass Q0 bei dem Lesen des Wortes W1 übergeht in den Zustand Q1. Weil genau so habe ich die Regel ja gesteckt.

Insofern habe ich hier eine gültige Berechnungsfolge von Zustandsübergängen des Automat. Und ich weiß zusätzlich, dass der letzte Endzustand akzeptiert ist. Und das ist die Definition von akzeptieren. Dann muss das Modo akzeptiert werden. Ja, damit hat sich also gezeigt, dass hier diese Mehrschuldableitung beim Lesen des Wortes W wirklich Qn ergibt. Qn ist akzeptierend, also wird W als Wort akzeptiert von der Maschine. Und ich habe hier gezeigt, dass alles, was wir erleben, ist auch in M0.2. Das Wort W wird akzeptiert.

Für mich ist das nicht so ganz versichtlich, wir nehmen ein Wort, wir müssen doch für jedes Wort das überprüfen, aber hätte ich jetzt eine unendliche Menge, zwar haben wir endliche Wörter, aber eine unendliche Menge kann ich nicht für alle unendlichen Sachen überprüfen, ob es auch in einer anderen Menge ist. Doch, kann man machen, kann man das machen. Du hast recht, jedes Wort, was wir aus dem Ausbreiten ist endlich, das ist das W, was wir hier festlegen, an dem wir sagen, W ist jetzt in LW drin, also das ist ein konkretes Wort, endliches Wort.

Das was wir jetzt ausgreifen konkret benennen ist in dem Moment halt NG. Aber die ganze Menge, die dort erzeugt werden kann, das ist unendlich, eine Sprache LG kann aus unendlichem Wörtern bestehen. Aber in dem Moment, wo du ein Wort rausdenkst und sagst, wie ist Element von LG, ist dieses Wort konkret und dann NG. Das ist der Trick. An der Stelle bist du nicht mehr im Unendlichen unterwegs. Auch wenn es wirklich viele verschiedene Elemente gibt von dieser Menge, leiten wir ein einzelnes raus.

Und jedes Wort heraus ist n. Und in dem Moment, wo du sagst, das Wort W ist aus dieser Länge, greifst du dir ein Wort raus, was n ist. Und dann haben wir wirklich noch endlich viele Stellen, das ist eine Anzahl n von Stellen, deswegen können wir es auch so schreiben als W1 bis Wn. Das ist ja gerade der Trick. Die Sprache hat unendlich viele Elemente, aber jedes Element, wenn man es rauskriegt, ist n. Weitere Fragen?

Okay, dann sind wir ganz genau jetzt hier durchgegangen. Weil das kennt ihr bald Teilmengenbeziehungen und damit auch die Gleichheit dieser beiden Mengen. Wir können also wirklich jeden Automaten umändern in eine Grammatik, die regulär ist. Ihr seht, dass diese terminierte Grammatik regulär ist. Also können endliche Automaten gar nicht mehr als regulär. Wir sind ganz unten auf der Chomsky-Hirrorität. Von der Mächtigkeit sehr, sehr einfach. Es reicht nicht einmal für diese HTML-Sprache, die wir haben. Nur für die Diftels.

Die waren regulär. Die können wir erkennen. So welche Probleme können wir lösen mit endlichen Aufschwamen. HTML erkennen können wir nicht mit endlichen Aufschwamen. Okay. Genau. Und jetzt gehen wir mal ein bisschen weiter. Wir möchten jetzt eigentlich haben wir es gezeigt, die DDAs erzeugen nur und akzeptieren nur reguläre Sprachen.

möchten wir zurück. Wir möchten eigentlich zeigen, dass die DEA's akzeptieren, die Sprachen, die DEA's akzeptieren, genau die regulären Sprachen. Aber das, was wir gezeigt haben, ist eigentlich nur diese Teilnehmung, dass die DEA's nur die regulären Sprachen akzeptieren. Es könnte aber sein, dass regulären Sprachen aus noch mehr bestehen, dass dann noch andere Sprachen drin sind in den regulären Sprachen, die wir nicht durch DEA's kommen. Und das versuchen wir jetzt in der Vollmerkung zu machen, das wird auch etwas länger noch dauern.

weil es eben nicht mehr so einfach wie der Verweis gerade ist. Das können wir nicht so komplett direkt machen. Da gibt es ein paar Hindernisse. Gezeigt haben wir hier also DEAs, naja, erzeugen nur oder akzeptieren nur reguläre Sprachen, aber der Rückweg ist ein bisschen schwieriger. Und die Probleme sind folgendermaßen, die ähnlichen Automaten, wie heißen das so, deterministisch ähnlichen Automaten, sind halt eben deterministisch. Das heißt deterministisch, das bleibt zu jedem Zeitpunkt der Folge zum Plan festgelegt.

An jedem Zeitpunkt kennt ihr den aktuellen Zustand und den aktuellen Buchstaben der Reihenfolge. Wenn ihr die beiden Informationen habt, ist der Nachfolgezustand immer festgelegt. Da gibt es keine Wahlmöglichkeit. Deswegen heißen diese Automaten auch deterministisch. Bei Grammatiken ist das leider nicht so. Bei Grammatiken ist es so, dass die nicht deterministisch sind, denn diese Einschätzung, das hatten wir auch schon mal, ist eine Relation. Wenn ich jetzt ein Zeichen A lese oder ableiten möchte, dann kann ich das durch diese Regel tun.

die nach kleiner und großer ableitet oder aber vielleicht auch nach dieser Regel tun, wenn B in der Webseite auch geleitet wird. Das heißt, da ist meine nächste Regel, die ich anwende, gar nicht klar, nicht deterministisch. Und das ist so ein fundamentaler Unterschied, dem wir hier in der Vorlesung tatsächlich an mehreren Ecken begegnet werden. Gerade auch dieser Nicht-Determinismus, die das total schwierig macht, so einen einfachen Beweis zu führen, dass die Regulandsprachen eben nicht noch größer sind als die von

Automaten akzeptierte Sprachen. Das versperrt uns ein bisschen diesen Rückblick. Und deswegen gehen wir einen Ausweg. Das ist das leichteste, was noch übrig bleibt. Hier flüchten wir uns in ein nicht-deterministisches Maschinenmodell. Wir machen aus den deterministischen Automaten nicht-deterministische. Mit dem gelingen wir uns dann wirklich eine Äquivalenz zu diesen regulären Sprachen zu zeigen, weil diese Sprachen ja auch, diese Dramatiken ja auch nicht etimistisch sind.

Da kann man eine Gleichheit zeigen, ähnlich wie der Beweis von gerade. Und dann, wenn wir halt diese regulären Sprachen zu den NEAs umgewandelt haben, die sind nicht-deterministische Automaten, haben wir aber ein Problem. Wir müssen wieder von den nicht-deterministischen Automaten zurückfinden zu den deterministischen. Dann entsteht sofort die Frage, sind die nicht-deterministischen Automaten jetzt nicht wirklich mächtiger als diese deterministischen Automaten? Weil wenn sie das wehren, dann will man nicht mehr zubekommen. Dann würde nicht jede Sprache, die wir hier durch NEAs erkennen können, die wir hier durch NEAs erkennen können,

auch von DRAs akzeptiert. Aber tatsächlich werden wir das schaffen. Die nicht-die-Themillischen-Automaten, was immer die sind, die wir gleich kennenlernen, die sind tatsächlich nicht mächtiger als die D-Themillischen-Staten. Komischerweise. Man denkt erst mal, formal sind sie mächtiger. Die können erst mal mehr. Die Operationen sind genereller. Aber hinterher, wenn es auf die Sparrennung ankommt, die sie halt akzeptieren, sind es genau die gleichen Sprache.

als wir an der Nase zeigen. Wahrscheinlich nicht mehr in diese Stunde. Okay, von dem Ausweg werden wir gehen, um zu zeigen, dass hinterher alle drei Sachen tatsächlich gleich sind. Deterministische Automaten, diese regulären Sprachen und diese nicht-deterministischen Automaten. Alles können dieselben Sprachklassen erzeugen oder akzeptieren. Okay, das ist der Plan. Wie mache ich jetzt aus einem deterministischen Automaten ein, nicht-deterministischen, in dem ich meine Zustandsüberführungspunktion

Ich mache die genereller. Bisher war das so, ich habe einen Zustand genommen, ich habe ein Alphabet-Zeichen genommen und daraus wurde deterministisch als Funktion abgebildet, sofort der nachfolgende Zustand generiert. Das war eine Funktion, das war festgelegt, was hier rausgekommen ist. Was ich jetzt mache, ist, ich setze dieses Zeichen durch das.

Ich erlaube, dass das, was reinkommt als Zustand oder als Eingabe-Gestand, das war doch nur, dass das nicht nur auf einen Zustand abgebildet werden kann, wie bei der Funktion, sondern hier in der Renner-Zugicht herausgemacht habe, auf mehrere. Was hier vielleicht jetzt steht, naja, Q0, Q7, Q11. dass all diese drei Zustände zum Beispiel abgebildet werden.

macht aus einer Funktion eine Relation. Dann haben wir keinen eindeutigen Nachfolgezustand mehr, sondern wir haben eine Menge von Nachfolgezuständen. Und das ist genau der springende Punkt über einen deterministischen Automaten und einen nicht-deterministischen. Ich schreibe euch jetzt die Definition nochmal hin, von ähnlichen Automaten, die ihr kennt, nur, dass ich immer dann in Rot einblende, was sich geändert hat. Und es erinnert sich nicht allzu viel. Ich nenne das ganze Ding jetzt nicht mehr deterministisch, sondern nicht deterministisch. Er ist nicht mehr DEA, sondern NEA.

aber sonst ist dann immer das gleiche 5. Alles bleibt gleich. Q bleibt gleich, Sigma bleibt gleich, Q0 bleibt gleich, F bleibt gleich, alles bleibt gleich, bis vielleicht auch Delta. Also das kennt ihr alles schon. Das nächste Mal. Aber Delta wird ein bisschen geändert. Nur an einer Stelle. Es ist nicht nur Zustandsüberführungsfunktion, sondern eine Relation geworden. Statt dem Folgefall, hier mache ich ein kathetisches Produkt. Das erlaube ich also eine Menge von Nachfolgezuständen.

Und genau so kann ich das auch schreiben als Funktion wieder, die was Eindeutiges zuweist, aber dann halt, naja, nicht einen eindeutigen Zustand, sondern eine Menge wirklich, eine Teilmenge von Zuständen, bedeutet, dass in jedem Fall die Zustände ja keine Menge von Zuständen eingehen kann. Das heißt, hier definiere ich auch noch, dass dann wirklich die Nachfolgemenge jetzt in dem Fall von QA nicht ein einzelner Zustand ist, sondern eine ganze Menge von Zuständen.

Nämlich alle Drittel, die drin sind in diesem kathetischen Produkt hier. Sprich, hier, wenn hier Q7 drin ist, also Q, dann ist hier auch QAQ7 drin. Dann steht hier auch Q7 in meiner Nachfolge. Diese Menge, Delta QA, enthält dann alle Elemente, alle Nachfolgezustände, die ausgedeckt werden. Und interessanterweise können das gar keine Zustände sein, das ist ja auch, oder alle Zustände, die es gibt. Oder eine beliebige Zeit.

Okay, das ist ein nicht-deterministischer Automat. Und hier ist mal ein Beispiel. Links seht ihr einen deterministischen, den kennt ihr schon. Ich habe jetzt zwei Vorstiegungsstunden, doppelstundenlang gesehen. Sollte bekannt sein, was der akzeptiert. Muss ein Adel vorkommen, muss danach ein Beten vorkommen. Ansonsten akzeptiert ihr das alles, dass das diesen Dingen gelügt. Und auf der rechten Seite seht ihr einen NEA, der, soweit ich weiß, das ist das sehr normal.

Die selbe Sprache. Und ihr seht, dass da was anders ist. Ihr seht erstmal, was widerspiegelt einer DDR, was wird so nicht gehen. Ihr merkt das. Von S gehen zwei Pfeile mit A. Das ist auch ein Rutschung, das geht eben DPR. Weil ich habe ja hier einen eindeutigen Nachweis. Der wäre der Groß A. Hier ist der Groß A, aber noch hier die Möglichkeit, den Pfeiler hinzugehen. Und dann habe ich wieder ein S.

Da habe ich plötzlich zwei Nachfolgezustände, S und A. Was ist noch nicht okay? Vom Zustand A können wir nicht A abrechnen. Genau. Auch das ist festgelegt, dass ich das haben muss beim DEA. Deswegen ist es der Klinik hier dran. Ich muss es haben. Ich muss festlegen, beim Lesen von klein A, dem Zustand Groß A, komme ich hier und hier raus. Das muss man beim NEA nicht. Da kann die Wende auch leer sein. Wenn ich den Kleidungsstab A lehse, dann...

Und die Maschine macht letztendlich gar nichts mehr. Aber das ist erlaubt. Genau, also Achtung, es ist erlaubt sowohl Null-Nachfolgezustände zuzulassen, als auch genau ein, dann hätte man wieder die effektivistische Situation, als auch beliebig viele, vielleicht sogar die gesamte Teilmengelte. Ja? Ich verstehe jetzt nicht, warum man von A mit Kleiner arbeiten muss.

muss. Warum man von A und A. Wenn man das machen muss, habe ich ja eigentlich, wie meinst du das? Wann hat gesagt, dass wenn man in DEA von A auf mit Ableitungen arbeiten kann? Also, da fehlt ein bisschen Kontext. Wenn wir eine Ableitungsfolge oder wenn wir in der Zustandsüberengung haben, wir sind jetzt noch nicht bei der Semantik, wie der wirklich "Aber", nur bei der Definition.

Nach Definition muss jetzt erstmal kein Pfeil mit klein a da sein. Ja, das ist bei mir die Frage. Beim DEA, warum muss der Pfeil da sein? Achso, weil wir hier eine Zustandsüberführungsfunktion haben, die Q und Sigma reingekommt und ableitet nach D. Wir haben beim DEA mehr das. Und das ist vorgeschrieben. Kennst du eine Funktion, die im Urkwild was reinkriegt, aber dann nichts zuweist? Eine Funktion legt ja fest, dass wirklich ein Bild da sein muss.

Was ist ein Polstein? Ist unabhängig davon. Da ist ja der Definitionsbereich auch nicht Q, Q, Sigma. Der Definitionsbereich ist ja Q, Räut, Sigma. Alle Urbilder hier müssen bedient werden unter dieser Funktion. Ein Polstein oder was nicht definiert ist, müsste eine Aussage machen und sagen, okay, hier ist jetzt irgendwas Kleineres als das. Könnte ich denn damit im DEA keine Sprache machen, wo ich nicht mehr für 1A kenne?

Also wenn du jetzt keine Sprache machen, die irgendwas nicht machst, du hast gesagt, kann ich keine Sprache haben. Kann ich eine Sprache haben, wo ich hier von F zu A, mit A gehe und dann kein weiteres A anhängen muss, sondern mit dem B übergeben muss? Ja. Wie mache ich das dann, wenn ich einen Zustand brauche, der mit A bei der B für A? Naja, jetzt bist du bei der Akzeptanz von Möschern. Du würdest dann hier bei der Groß A,

zu erzwingen, dass bei jedem zweiten A, was du halt liest, ein anderer Zustand hinzufügst, sodass hier dieser Zustand nicht akzeptiert ist, werden diese Böcke halt verworfen, sobald das zweite Klein A liest. Und wenn du aber halt nur ein A liest und dann B oder irgendwie was, dann liest du das akzeptiert. So kannst du kennen. Ah ok, also was haben wir mit dem Problem jetzt nichts zu tun?

Es ist einfach nur, dass es dann nicht in einem verändenen Zustand gehen kann. So muss ich das nicht sagen. Genau. Die Pfeile sind aber alle da. Okay, du musst dich gar nicht in einem Zustand fest haben und dann auch nochmal A und B, die beiden reingehen. Ja, du brauchst für jeden Zustand, brauchst du alle Pfeile. Hier müssen wieder alle ausgehen in A und B. Wenn dein Alphabet A wählt. Für jeden Zustand. Ist ja klar, weil das eine Funktion ist und hier weg ist. Alle Elemente daraus bedient werden müssen.

Okay, gut. Ja, und das war allgemein dann natürlich ein deterministischer Automaten, so nicht deterministischer, weil wir hier als Relation auch wirklich nur einen einzigen Nachfolgezustand zulassen können. Wenn wir das tun, haben wir wieder ein BER. Wenn wir es nicht tun, haben wir einen echten NER. Ich glaube, ich habe ja nochmal ein paar Verleutlichungen aufgeschrieben. Wir müssen uns ja auch fragen, was ist denn eine Berechnung von so nicht deterministischen Automaten? Funktioniert denn da so wie bei dir?

technologisch. Ich kriege wieder eine Eingabe rein von Zeichen, das generiert mir hier eine Berechnung, wenn ich darauf eine Folge von Zuständen mache, sodass ich immer dann, wenn ich von einem Zustand zum nächsten springe, gucke, was kann durch diese Delta-Relation jetzt erreicht werden. Nur, dass Delta jetzt eine Relation ist und nicht mehr eine Funktion. Trotzdem kann ich ja checken, dass wirklich der nächste Nachfolgezustand in dieser Delta-Relation mit ist. Aber wenn er denn ist, dann ist diese Zustandsfolge eine Erlaubnis-Folge.

und damit eine Berechnung. Aber es gibt ein Problem dadurch. Jetzt kriege ich natürlich das Problem, dass wenn ich eine Zeichenplatte einlese, dass ich dann einmal hier sein kann. Vielleicht bin ich jetzt hier nachlesen vom Zeichen. Aber wenn ich eine andere Wahl getroffen habe, von Nachfällig zu stellen, es gibt jetzt ja mehrere Wahlen, könnte ich vielleicht auch hier sein. Bei derselben Eingabebuchstaben 1,0.

in verschiedene Zustände an. Ich kann also verschiedene Berechnungen aus, wie möglich, weil mehrere benachfolgende Zustände ermöglichen. Dann ist die Frage, wann akzeptiere ich das, wenn ich jetzt verschiedene Wege gehe? Ja, und das ist vielleicht noch das wichtigste, oder der wichtigste Unterschied zum Deterministischen Automaten. Ich akzeptiere dann ein Wort W, dieses hier, wenn es seine Berechnung

Wenn eine Rechnung existiert, es müssen nicht alle zum Ziel werden, eine reicht. Wenn eine davon akzeptierend ist, eine Berechnung, also mit einem Zustand aufhört, der akzeptierend ist, dann habe ich gewonnen. Aber am Ende haben wir ganz viele, viele Reguliere, auch viele, die nicht akzeptieren. Wenn eine davon akzeptierend ist, wird das ganze Wort akzeptiert. Okay, also es gibt eine Berechnung, reicht aus. Okay, gut, da haben wir jetzt noch rausgesessen.

Aber, habe ich auch gerade schon gesagt, links werden alle Wörter akzeptiert, die das Wort AB enthalten. Und zwar A direkt vorne rein. Denn wenn ich jetzt hier nach A reinkomme und hier bin und dann dieses zu dem anderen Pfeil entlang gehe, dann kriege ich ja wieder ein A. Aber insofern ist auch dort immer ein klein A gefolgt von einem B, konsekutiv, also das Wort AB enthalten.

Und all diese Wörter werden akzeptiert, alle anderen werden verbrochen. Vom deterministischen Automaten. Dieser nicht-deterministische leistet hier genau dasselbe. Sie wird also dieselbe Sprache akzeptieren, weil ich hier zu jedem Wort, was AW enthält, auf einem Rechnungsweg finden kann. Es gibt vielleicht auch einen Fall, die es nicht tun, die dann in einem Zustand dann, der hier nicht akzeptierend ist, ich könnte zum Beispiel hier a entlang gehen und dann b, und dann lande ich in einem nicht akzeptierenden Zustand s.

Das heißt aber nicht, dass das Wort AW jetzt verworfen wird, sondern ich muss alle Brennungsphase durchgehen auf der nicht-diagnostischen Maschine. Wie möglich. Und einer davon ist natürlich der, der hier A entlang geht und hier B entlang geht und dann in Groß B endet, was akzeptieren ist. Und der Einzelne reicht aus, dass das Wort akzeptiert wird. Also seht ihr hier, dass das die gleichen Sprachen akzeptiert werden, Es gibt zwei Sichten hier auf so einer nicht-theimistischen Maschine.

weil wir uns die schwer vorstellen. Und die erste Sicht ist, dass die mythemistische Maschine immer rät, nicht mythemistisch rät, ab wann dieses Teilewort AW dann, was hier die Sprache kennzeichnet, beginnt. Das heißt, diese ganzen Iterationen, die wir hier machen können, ohne dass das AW wirklich eine Rolle spielt, da sagen wir, Der nicht-hieristische Automat der Welt einfach...

die Stelle, an der es wirklich wichtig ist, dass das AB hier in diese Transition rüberkommt, zu dem Akzeptierungszustand. Und genau dann geht er den Weg im Rechnungsrat, den er gehen muss, um akzeptierend zu werden. Und die andere Vorstellung ist, dass wir alle Rechnungswege parallel durchgehen. Ja, und dann spricht man irgendwie ein bisschen hochgestochen von Paralleluniversen. Ja, wir machen irgendwie ein Universum an für jeden möglichen Rechnungsweg, für jede Verzweigung, die wir einschlagen, wenn wir mit dem Lesen vom Buchstaben A einmal nach links gehen oder einmal nach rechts.

Da spannen wir dann zwei Paralleluniversen auf und jedes dieser Paralleluniversen werden mit den anderen gleichzeitig durchgegangen. Alle Rechnungspfade, die es gibt, werden gleichzeitig mit den Paralleluniversen durchgegangen. Und am Ende wird geguckt, ist eine Welt enthalten, eine Universe enthalten, in der wir wirklich akzeptierend unterwegs sind, dann reicht dieses aus und das Wort wird dann akzeptiert. Das ist die andere Vorstellung, wie man nicht determiniert. Determinismus muss sich vorstellen. Okay, und warum ist das so schwierig, sich das vorzustellen? Weil es bis heute keiner geschafft hat, je zu bauen.

Wir wissen es nicht, ob es überhaupt werden kann. Könnte noch sein. Aber bis jetzt hat es keiner geschafft, keiner glaubt er dran. Zumindest sind es nicht ein nicht-definistischen Automaten, der fizient arbeitet. Wir können einen natürlich sinnolieren. Wir haben ihn ja auch definiert. Wir können alle Rechnungspläne hintereinander durchgehen, aber dann wirklich nur hintereinander. Nicht auf diese Parallelwelt mit vielen Paralleluniversen. Und das macht die Schwierigkeit aus, sich das Ding vorzustellen, weil es halt nicht eine handelsübliche Maschine ist, die man bauen kann und die man dann ausführt.

Trotzdem sind die in der Praxis wichtigsten Probleme, die wir kennenlernen werden, und auch in der Praxis die wichtigsten, hinterher durch nicht in den Messen was definiert, nicht nur bei Automaten, sondern auch in der Kompetenz. Das wäre jetzt aber erst in der nächsten Vorlesung. Ich glaube nicht, oder? Ja, doch erst in der nächsten Vorlesung. Also nächstes Semester. Okay, an der Stelle machen wir erstmal Pause. Manchmal mache ich Pause, damit ihr ein bisschen Ruhe habt vor mir.

ein bisschen mehr Platon bilden könnt. Lass uns mal fünf Minuten Pause machen und dann machen wir weiter mit der wie mächtig jetzt endlich der Automaten-Wegel-Sendung. ...