Ich hab ne Frage: Kann man bei einem NEA mit unterschiedlichen Buchstaben in einen anderen Zustand wechseln? Also z.B. von q0 mit a und b in q1? Geht das?
+marckotobelo Wie ich bei 8:05 sage, kann man tatsächlich beweisen, dass ein DEA, der diese Sprache erkennt, mindestens 4 Zustände benötigt. Dir muss wohl ein Fehler unterlaufen sein. Probiere mal ein paar Worte aus, dann solltest Du den Fehler finden können!
Vielen Dank für die übersichtliche Erklärung, aber eines ist mir noch unklar, hoffe du kannst mir das kurz beantworten. Darf man einen NFA getrennt erstellen? Also 2 Startzustände, die beide in unterschiedliche Endzustände führen, aber kein Folgezustand von Startzustand 1 mit einem Folgezustand von Startzustand 2 verbunden ist und so gesehen eigl. 2 Automaten dastehen, aber es Ein Automat sein soll.
Es gibt unterschiedliche Definitionen für NFAs. Manchmal erlaubt man mehrere Startzustände, manchmal nicht. Aber die unterschiedlichen Versionen sind gleichmächtig, d.h. sie können die gleichen Sprachen erkennen.
Ein NEA akzeptiert ein Wort, wenn es mindestens einen akzeptierenden Pfad gibt und er verwirft das Wort, wenn alle Pfade verwerfend sind. Der Automat kann zwar auch im ersten Zustand bleiben, aber das ist nur ein möglicher Pfad. Da es aber noch einen anderen und zwar akzeptierenden Pfad gibt, wird ein Wort mit vorletztem Symbol a akzeptiert. Bei einem Wort mit vorletztem Symbol b hingegen wäre jeder Pfad verwerfend, deswegen werden solche Wörter nicht akzeptiert.
Verstehen den NEA nicht ganz, welcher L5 erkennen soll. Angenommen ich habe a,a,b. Den Pfad mit der Schleife auf sich selbst ergibt kein Erfolg. Der andere hat nur zwei mögliche Operationen. Er geht zu a dann wieder a, landet im Automaten der akeptiert aber nun geht es ja nicht mehr weiter mit b. D.h. der Pfad ist auch ungültig? Ich hab das jetzt so verstanden, dass ein NEA die Pfade kombiniert aber davon hast du ja nichts gesagt oder? Also woher weiß er, dass er alle Symbole, bis auf die letzten Beide mit der Schleife macht und den Rest mit dem rechten Pfad?
Ein NEA akzeptiert ein Wort w, falls es einen möglichen Pfad *gibt*, den er mit dem Eingabewort w nehmen kann und am Ende in einem Endzustand landet. Das Wort aab wird also akzeptiert, denn der NEA kann vom Startzustand aus einmal die a-Schleife benutzen, dann den a-Übergang zum nächsten Zustand und dann den b-Übergang in den Endzustand. Deine Frage bezieht sich auf den interessanten Punkt, dass ein NEA ja nicht wissen kann, welchen Pfad er nehmen muss. Aber man kann sich zum Beispiel vorstellen, dass der NEA den Pfad rät, und er immer richtig rät, falls es einen Pfad gibt. Die NEAs sind also kein Automatenmodell, das man aus der Praxis kennt, sondern eher für theoretische Zwecke wichtig!
Sehr gutes Erklärvideo. Du machst das echt sehr gut.
Super gute Arbeit !
Habe bald eine wichtige Klausur und diese Video-Serie hilft mir wirklich sehr! Vielen Dank!!
Danke für die Hilfe
Sehr gut!!!:)))
Wie kann es sein, dass die Professoren in der Uni alles so "Scheisse" (Sorry) erklären und du es viel besser ausführlicher erklären kannst? :-D
auch noch in einem Bruchteil der Zeit
Du machst das was olaf nicht konnte
Ich hab ne Frage: Kann man bei einem NEA mit unterschiedlichen Buchstaben in einen anderen Zustand wechseln? Also z.B. von q0 mit a und b in q1? Geht das?
Ja, das geht.
@@NLogSpace Sehr gut vielen Dank für deine Antwort. Und würde das auch beim DFA gehen?
warum braucht dein DEA mit vorletzte Zeichen A soviel zustände ? ich kann den auch mit 3 zuständen bauen... oder lieg ich da falsch ?
+marckotobelo Wie ich bei 8:05 sage, kann man tatsächlich beweisen, dass ein DEA, der diese Sprache erkennt, mindestens 4 Zustände benötigt. Dir muss wohl ein Fehler unterlaufen sein. Probiere mal ein paar Worte aus, dann solltest Du den Fehler finden können!
+Leifaktor vielen Dank bin drauf gekommen ! :)
Vielen Dank für die übersichtliche Erklärung, aber eines ist mir noch unklar, hoffe du kannst mir das kurz beantworten. Darf man einen NFA getrennt erstellen? Also 2 Startzustände, die beide in unterschiedliche Endzustände führen, aber kein Folgezustand von Startzustand 1 mit einem Folgezustand von Startzustand 2 verbunden ist und so gesehen eigl. 2 Automaten dastehen, aber es Ein Automat sein soll.
Es gibt unterschiedliche Definitionen für NFAs. Manchmal erlaubt man mehrere Startzustände, manchmal nicht. Aber die unterschiedlichen Versionen sind gleichmächtig, d.h. sie können die gleichen Sprachen erkennen.
Dankeschön für die schnelle Antwort!
tipp: 1.5x Geschwindigkeit.
Bitteschön.
Ich mag die 1x Geschwindigkeit gerne ;D
Warum erkennt der eine Sprache bei der das vorletzte Zeichen ein a ist ? Er kann doch auch dann im Startzustand stecken bleiben und erkennt das nicht.
Ein NEA akzeptiert ein Wort, wenn es mindestens einen akzeptierenden Pfad gibt und er verwirft das Wort, wenn alle Pfade verwerfend sind. Der Automat kann zwar auch im ersten Zustand bleiben, aber das ist nur ein möglicher Pfad. Da es aber noch einen anderen und zwar akzeptierenden Pfad gibt, wird ein Wort mit vorletztem Symbol a akzeptiert. Bei einem Wort mit vorletztem Symbol b hingegen wäre jeder Pfad verwerfend, deswegen werden solche Wörter nicht akzeptiert.
@@NLogSpace Ah, OK. Wenn es geht, dann macht es das auch. Danke
Verstehen den NEA nicht ganz, welcher L5 erkennen soll. Angenommen ich habe a,a,b. Den Pfad mit der Schleife auf sich selbst ergibt kein Erfolg. Der andere hat nur zwei mögliche Operationen. Er geht zu a dann wieder a, landet im Automaten der akeptiert aber nun geht es ja nicht mehr weiter mit b. D.h. der Pfad ist auch ungültig?
Ich hab das jetzt so verstanden, dass ein NEA die Pfade kombiniert aber davon hast du ja nichts gesagt oder? Also woher weiß er, dass er alle Symbole, bis auf die letzten Beide mit der Schleife macht und den Rest mit dem rechten Pfad?
Ein NEA akzeptiert ein Wort w, falls es einen möglichen Pfad *gibt*, den er mit dem Eingabewort w nehmen kann und am Ende in einem Endzustand landet. Das Wort aab wird also akzeptiert, denn der NEA kann vom Startzustand aus einmal die a-Schleife benutzen, dann den a-Übergang zum nächsten Zustand und dann den b-Übergang in den Endzustand.
Deine Frage bezieht sich auf den interessanten Punkt, dass ein NEA ja nicht wissen kann, welchen Pfad er nehmen muss. Aber man kann sich zum Beispiel vorstellen, dass der NEA den Pfad rät, und er immer richtig rät, falls es einen Pfad gibt. Die NEAs sind also kein Automatenmodell, das man aus der Praxis kennt, sondern eher für theoretische Zwecke wichtig!
Ok danke :)