Ich war mir ja nicht sicher ob ich Info studieren will weil ich mir nichts unter dem theoretischen Zeug vorstellen konnte ob das mein Ding ist, nachdem ich ein bisschen in diese Serie und die zur Berechenbarkeit rein geschnuppert habe bin ich mir ziemlich sicher dass ich an den Themen viel Freude haben werde, danke dafür :)
Huhu, mich würde mal interessieren ob du jetzt wirklich Informatik studiert hast. Und wie zur Hölle man bereits vor seinem Informatikstudium zu dieser Videoreihe gelangen kann 😂
Hi, danke für das Video :). Bei ca 7:30 - 8:00, sagst du, dass man von 1,2 durch a entweder bei 1,2 oder bei der leeren Menge landen kann. An sich könnte man denken, dann müsste noch ein Übergang von 1,2 zur leeren Menge dazu gezeichnet werden, aber wenn ich dich richtig verstehe, ist in 1,2 implizit auch die Teilmenge "leere Menge" enthalten? (Gleiches für 1,2 von 1 mit b zur leeren Menge) Wenn dem so ist, dann gilt das vermutlich für die Teilmenge 1 und 2 auch wieder, was mich fragen lässt, wieso wir für diese Teilmengen einen Übergang zur leeren Menge zeichnen müssen?
Wir konstruieren einen DEA. Dieser darf für jedes Symbol immer nur eine ausgehende Kante haben. Diese Kante führt immer zu dem Zustand, der für die Vereinigung aller erreichbaren Zustände steht. In diesem Fall haben wir die Menge {1, 2} und die leere Menge. Die Vereinigung von {1, 2} und der leeren Menge ist wieder {1, 2}, also ziehen wir die Kante zum Zustand {1, 2}. Beachte, dass ich die Zustandsnamen abgekürzt habe, also der Zustandsname 12 steht für {1, 2}, der Name 1 steht für {1} und so weiter.
@@NLogSpace "Die Vereinigung von {1, 2} und der leeren Menge ist wieder {1, 2}, also ziehen wir die Kante zum Zustand {1, 2}." Bei dem Satz hats klick gemacht. Danke :)!
Danke für das Video. An der Stelle 13:25 verstehe ich das mit den "beliebig vielen weiteren "a's" nicht. Wenn ich in "2" bin, dann kann ich kein "a" mehr lesen. Wahrscheinlich kapiere ich den Zustand "1,2" nicht. :(
Hey Leif, ich hätte eine Frage an dich. Morgen schreibe ich Theo und inzwischen beherrsche ich dank deiner Videos das Thema Formale Sprachen relativ gut. Aber da die Klausur zur Hälfte aus Berechenbarkeit/Komplexität besteht und ich diese Themen nicht kann und bis morgen nicht mehr lernen werde, habe ich mir überlegt einen Trick anzuwenden, den mir ein Freund erzählt hat: Auf die Rückseite meines Cheatsheets werde ich alle Fragen und Antworten zu den Berechenbarkeit/Komplexität-Quiz-Fragen der Altklausuren der letzten Jahre schreiben. Mein Kumpel meinte, dass es nicht so viele fundamental verschiedene Fragen zu diesen Themen in Klausuren gibt und deshalb könnten einige Fragen in meiner Klausur drankommen, wo ich einen ähnlichen Beweis dann schon auf meinem Cheatsheet haben werde. Deine Meinung zu dieser Taktik? Mir geht's bei Theo wirklich nur ums Bestehen ^^
Also meine ehrliche Meinung: Wenn Du die Hälfte der Themen nicht kannst, dann solltest Du dir keine große Hoffnung machen zu bestehen! Zum Bestehen sollte man (meiner Meinung nach) schon von allen Themen der Vorlesung ein grundsätzliches Verständnis haben. Also lieber bei nächsten Mal rechtzeitig mit der Vorbereitung anfangen. Zu Berechenbarkeit und Komplexität habe ich übrigens auch viele Videos. ;)
@@NLogSpace Du hast natürlich Recht. Ich hatte halt nur 3 Tage Zeit zum lernen, da ich Theo vorgezogen habe und somit zwischen zwei andere Klausuren gequetscht habe. Und ja, deine Videos zu Berechenbarkeit und Komplexität werde ich mir (falls nötig) für den Retake anschauen :)
Ich hab da mal eine Frage, vlt antwortest du ja noch. Also, beim Schreiben eines NEAs zu einem DEA anhand dieses Beispiels sind mir ein paar Sachen nicht ganz verständlich gewesen. Wenn ich jetzt beim NEA ein a eingebe, dann lande ich nicht zwingend beim Endzustand, das ist beim DEA aber schon so. Wenn ich jetzt beim NEA ein a lese und im Endzustand lande, dann gibt es beim NEA doch keine Möglichkeit weitere a's zu lesen? Kommt man dann nicht in den Papierkorb? Beim DEA ist das so, dass man beliebig viele a's lesen kann und im Endzustand bleibt... Kannst du mir das erklären?
Vielleicht besser spät als nie, aber ich hoffe deine Frage wurde im laufe des letzten Jahres geklärt. Aber vllt stellt sich jemand anderes die gleiche. Beim NEA hast du bei Zustand 1 die Möglichkeit beliebig viele a‘s zu lesen. Dass du über die Kante mit a zum endzustand gelangst sorgt nur dafür dass du wirklich mind. 1 a hast
Ich habe oft im Unterricht den Namen Fehlerzustand gehört und wollte fragen, ob dass in diesem Fall die leere Menge ist ? Schon mal Danke für die Antwort 👍
Ja, der Zustand mit der leeren Menge wird auch Fehlerzustand, Papierkorbzustand oder Müllzustand genannt. Wenn der Automat in diesen Zustand gelangt, dann wird das Eingabewort nicht akzeptiert, denn dieser Zustand ist kein Endzustand und er wird nie wieder verlassen, da alle ausgehenden Kanten von diesem Zustand auf sich selbst zeigen.
Wie beweist man, dass ein NEA vollständig ist? Beim DEA muss man ja nur schauen, ob bei jedem Zustand auch alle Ein- und Ausgänge vorhanden sind, allein dadurch kann man zumindest herausfinden, ob der DEA schon vollständig ist. Wie macht man das aber beim NEA, bei dem beim ein oder anderen Zustand für ein bestimmtes Symbol kein Ein- oder Ausgang vorgesehen ist?
Leifaktor Naja, wie in deinem ersten Video über einen DEA muss es einen Aus- oder Eingang für a und b geben, in jedem Zustand. Ein Zustand hat also immer ein a und ein b. Wenn man sich jetzt alle Zustände anschaut, dann darf es keinen Zustand geben, wo eine der Angaben fehlt. Fehlt eine Angabe, dann weiß man, dass der DEA noch nicht vollständig ist. Bei dem NEA ist dies ja nicht so, da hat ein Zustand z.B. nur das a, aber kein b, aber das macht es ja schwierig dies zu erkennen, für den fall, dass dieser Zustand ja doch einen b bräuchte, aber man schlichtweg vergessen hat einen einzuzeichnen. .
+Karnickel Bei einem DEA braucht jeder Zustand für jedes Symbol aus dem Alphabet genau eine ausgehende Kante. Die eingehenden Kanten sind egal! Bei einem NEA gibt es keine Beschränkungen für die ein- oder ausgehenden Kanten, es können von jedem Zustand für jedes Alphabetssymbol beliebig viele (auch 0) Kanten ausgehen. Ich bin mir nicht sicher, ob ich die Frage jetzt richtig verstehe: Möchtest Du von einem gegebenen NEA herausfinden, ob es ein DEA ist? Dafür prüft man einfach für jeden Zustand, ob er genau eine ausgehende Kante für jedes Alphabetssymbol hat. Wenn ja, dann ist es ein DEA, wenn nicht, dann nicht.
Leifaktor Das mit den ausgehenden Kanten meinte ich. Es muss in einem DEA für jedes Symbol eine ausgehende Kante geben. Damit weiß man, ob ein DEA vollständig ist. Man kann einfach schauen, ob überall die entsprechend notwendige Menge ausgehender Kanten vorhanden ist. Bei einem NEA kann die Zahl für jedes Symbol 0 bis beliebig viele sein. Man sieht also an dieser Anzahl nicht, ob bei einem Zustand noch etwas fehlt. Darum geht es mir. Wenn ich wissen will, ob ein DEA vollständig ist, dann zähle ich einfach die ausgehenden Kanten an jedem Zustand. Damit weiß ich, dass er vollständig ist, ich weiß damit natürlich noch nicht, ob er auch richtig ist. Beim NEA bringt diese Zählerrei nichts. Wie erkennt man also, dass der NEA alle Kanten hat die er braucht?
"Wie erkennt man also, dass der NEA alle Kanten hat die er braucht?" Brauchen wofür? Ein NEA "braucht" überhaupt keine Kanten: Jedes Objekt mit Zuständen, einem Startzustand, einem Alphabet, einer Menge von Endzuständen und irgendwelchen (oder gar keinen) Kanten ist ein NEA. Oder meinst Du geht es Dir darum herauszufinden, ob der NEA eine bestimmte Sprache erkennt? Hierfür kann man nicht allgemein argumentieren: Es hängt immer von der Sprache ab, die man erkennen möchte, welche und wieviele Kanten man benötigt.
Wie konstruiert man genau die Zustände für Q'? Angenommen mein NEA hätte {1,2,3,4,5,6,7} Zustände, müsste ich es dann wie folgt aufdröseln?: Q' { 0, 1, 2, 3,4,5,6,7, 12,13,14,15,16,17, 23,24,25,26,27, 34,35,36,37, 45,46,47, 56,57, 67 123,134,156,167, 234,245,256,257, usw. ? } Danke für eine Antwort, auch wenn das Video schon etwas älter ist :)
+americanaccounts Ja, man muss systematisch alle Kombinationen durchgehen, so wie Du das schon angefangen hast. Wenn Q insgesamt n Zustände hat, dann hat Q' 2^n Zustände, in deinem Fall wären es also 2^7=128.
Reicht es nicht die Kombinationen zu wählen, die auch im NEA möglich sind? Also bei denen auch mehr als eine abgehende Kante für ein Symbol vorhanden ist? Andere Kombinationen würden im entstehenden DEA keine Verwendung finden oder? D: Ich bin verwirrt!
Komisch. Bei uns in der Vorlesung hatten wir Potenzmengenkonstruktion anders. Bei uns sah das dann so aus: imgur.com/il6ep5y Kann es sich hier um was anderes als eine Potenzmengenkonstruktion handeln?
In dem Bild hießen die Zustände des ursprünglichen Automaten q0, q1 und q2. Die Zustände des Potenzautomaten sind dann Mengen von Zuständen, also z.B. {q0}, {q0, q1}, {q0, q2}. In meinem Video habe ich die Zustände des ursprünglichen Automaten 1 und 2 genannt. Die Zustände des Potenzautomaten, welche eigentlich Mengen sind, also dann z.B. {1}, {1,2} usw. habe ich abkürzend einfach nur 1 und 12 genannt. Bei 3:00 sage ich dazu, dass ich die Schreibweise vereinfacht habe. Der Grund, weshalb nicht alle möglichen Mengen in dem Automaten dargestellt werden, ist, dass die anderen Zustände gar nicht erreichbar sind. Man könnte sie dazu schreiben, aber es gäbe keine Möglichkeit vom Startzustand dorthin zu kommen, deshalb kann man sie weglassen und die erkannte Sprache ist immer noch die gleiche.
Ah okay. Desweiteren: Kann es sein dass wenn man einen Epsilon-NEA direkt in einen DEA verwandelt man ein anderes Ergebnis bekommt als wenn man einen Epsilon-NEA in einen NEA und dann den NEA mittels Potenzmengenkonstruktion in einen DEA verwandelt? (2 verschiedene DEAs)
Kommt darauf an. Was für eine Konstruktion benutzt Du denn, um einen Epsilon-NEA "direkt" in einen DEA zu verwandeln? Ich habe in dieser Videoreihe glaube ich keine solche Konstruktion vorgestellt, sondern nur Epsilon-NEA zum NEA und NEA zum DEA gezeigt.
Erst mal Top, dass Du die Videos hier machst und anderen hilfst TheoInf besser zu begreifen. Danke. Nun zu meiner Frage: Warum steht die leere Menge in Mengenklammern beim DEA? Die leere Menge ist ja schon ne Menge und darf für mein Verständnis nicht mehr in die Mengenklammern geschrieben werden.
Der DEA hat eine MENGE von Zuständen. Bei der Potenzmengenkonstruktion ist jeder dieser Zustände selbst wieder eine MENGE, also haben wir Mengen in Mengen. Die leere Menge ist einer dieser Zustände, die anderen wären {1}, {2} und {1,2}. Ich habe diese aber abgekürzt geschrieben als 1, 2 und 12, aber eigentlich sind das auch alles Mengen!
![Pumping Lemma für erkennbare Sprachen [IMPROVED]](http://i.ytimg.com/vi/NFJtwpZs7BE/mqdefault.jpg)
![Pumping Lemma für erkennbare Sprachen [IMPROVED]](/img/tr.png)
du bist der beste auf x1,5 video-abspieleschwindigkeit
omg ich dachte schon ich wäre der einzige der das so macht
Sehr verstaendlich erklaert. Danke! :-)
Ich war mir ja nicht sicher ob ich Info studieren will weil ich mir nichts unter dem theoretischen Zeug vorstellen konnte ob das mein Ding ist, nachdem ich ein bisschen in diese Serie und die zur Berechenbarkeit rein geschnuppert habe bin ich mir ziemlich sicher dass ich an den Themen viel Freude haben werde, danke dafür :)
Das freut mich! :)
Huhu, mich würde mal interessieren ob du jetzt wirklich Informatik studiert hast. Und wie zur Hölle man bereits vor seinem Informatikstudium zu dieser Videoreihe gelangen kann 😂
Starkes Video!
Hi, danke für das Video :).
Bei ca 7:30 - 8:00, sagst du, dass man von 1,2 durch a entweder bei 1,2 oder bei der leeren Menge landen kann.
An sich könnte man denken, dann müsste noch ein Übergang von 1,2 zur leeren Menge dazu gezeichnet werden, aber wenn ich dich richtig verstehe, ist in 1,2 implizit auch die Teilmenge "leere Menge" enthalten? (Gleiches für 1,2 von 1 mit b zur leeren Menge)
Wenn dem so ist, dann gilt das vermutlich für die Teilmenge 1 und 2 auch wieder, was mich fragen lässt, wieso wir für diese Teilmengen einen Übergang zur leeren Menge zeichnen müssen?
Wir konstruieren einen DEA. Dieser darf für jedes Symbol immer nur eine ausgehende Kante haben. Diese Kante führt immer zu dem Zustand, der für die Vereinigung aller erreichbaren Zustände steht. In diesem Fall haben wir die Menge {1, 2} und die leere Menge. Die Vereinigung von {1, 2} und der leeren Menge ist wieder {1, 2}, also ziehen wir die Kante zum Zustand {1, 2}. Beachte, dass ich die Zustandsnamen abgekürzt habe, also der Zustandsname 12 steht für {1, 2}, der Name 1 steht für {1} und so weiter.
@@NLogSpace
"Die Vereinigung von {1, 2} und der leeren Menge ist wieder {1, 2}, also ziehen wir die Kante zum Zustand {1, 2}."
Bei dem Satz hats klick gemacht. Danke :)!
Das stimmt zwar alles, allerdings hast du leider nicht die δ' transition angesprochen, die oft in Uni Klausuren verwendet werden sollen.
Danke für das Feedback. Wenn ich die Serie neu aufnehme, werde ich das beachten!
Danke für das Video. An der Stelle 13:25 verstehe ich das mit den "beliebig vielen weiteren "a's" nicht. Wenn ich in "2" bin, dann kann ich kein "a" mehr lesen. Wahrscheinlich kapiere ich den Zustand "1,2" nicht. :(
Was muss man machen, wenn der NEA ε-Transitionen enthält?
stark
Hey Leif, ich hätte eine Frage an dich. Morgen schreibe ich Theo und inzwischen beherrsche ich dank deiner Videos das Thema Formale Sprachen relativ gut. Aber da die Klausur zur Hälfte aus Berechenbarkeit/Komplexität besteht und ich diese Themen nicht kann und bis morgen nicht mehr lernen werde, habe ich mir überlegt einen Trick anzuwenden, den mir ein Freund erzählt hat: Auf die Rückseite meines Cheatsheets werde ich alle Fragen und Antworten zu den Berechenbarkeit/Komplexität-Quiz-Fragen der Altklausuren der letzten Jahre schreiben. Mein Kumpel meinte, dass es nicht so viele fundamental verschiedene Fragen zu diesen Themen in Klausuren gibt und deshalb könnten einige Fragen in meiner Klausur drankommen, wo ich einen ähnlichen Beweis dann schon auf meinem Cheatsheet haben werde.
Deine Meinung zu dieser Taktik? Mir geht's bei Theo wirklich nur ums Bestehen ^^
Also meine ehrliche Meinung: Wenn Du die Hälfte der Themen nicht kannst, dann solltest Du dir keine große Hoffnung machen zu bestehen! Zum Bestehen sollte man (meiner Meinung nach) schon von allen Themen der Vorlesung ein grundsätzliches Verständnis haben.
Also lieber bei nächsten Mal rechtzeitig mit der Vorbereitung anfangen. Zu Berechenbarkeit und Komplexität habe ich übrigens auch viele Videos. ;)
@@NLogSpace Du hast natürlich Recht. Ich hatte halt nur 3 Tage Zeit zum lernen, da ich Theo vorgezogen habe und somit zwischen zwei andere Klausuren gequetscht habe. Und ja, deine Videos zu Berechenbarkeit und Komplexität werde ich mir (falls nötig) für den Retake anschauen :)
Ich hab da mal eine Frage, vlt antwortest du ja noch. Also, beim Schreiben eines NEAs zu einem DEA anhand dieses Beispiels sind mir ein paar Sachen nicht ganz verständlich gewesen.
Wenn ich jetzt beim NEA ein a eingebe, dann lande ich nicht zwingend beim Endzustand, das ist beim DEA aber schon so.
Wenn ich jetzt beim NEA ein a lese und im Endzustand lande, dann gibt es beim NEA doch keine Möglichkeit weitere a's zu lesen? Kommt man dann nicht in den Papierkorb? Beim DEA ist das so, dass man beliebig viele a's lesen kann und im Endzustand bleibt...
Kannst du mir das erklären?
Vielleicht besser spät als nie, aber ich hoffe deine Frage wurde im laufe des letzten Jahres geklärt. Aber vllt stellt sich jemand anderes die gleiche. Beim NEA hast du bei Zustand 1 die Möglichkeit beliebig viele a‘s zu lesen. Dass du über die Kante mit a zum endzustand gelangst sorgt nur dafür dass du wirklich mind. 1 a hast
Ich habe oft im Unterricht den Namen Fehlerzustand gehört und wollte fragen, ob dass in diesem Fall die leere Menge ist ? Schon mal Danke für die Antwort 👍
Ja, der Zustand mit der leeren Menge wird auch Fehlerzustand,
Papierkorbzustand oder Müllzustand genannt. Wenn der Automat in diesen
Zustand gelangt, dann wird das Eingabewort nicht akzeptiert, denn dieser
Zustand ist kein Endzustand und er wird nie wieder verlassen, da alle
ausgehenden Kanten von diesem Zustand auf sich selbst zeigen.
Ist der zustand von der leeren Menge ( papierkorbzustand ) das gleiche wie der "Error" Zustand ?
Ich kenne den Begriff Error-Zustand nicht, aber ich nehme mal stark an, dass damit das gleiche wie hier der Papierkorbzustand gemeint ist!
@@NLogSpace Es ist das gleiche gemeint. Danke für die schnelle Antwort ^^ Deine Videos sind der Hammer. Mach weiter so :D
Wie beweist man, dass ein NEA vollständig ist?
Beim DEA muss man ja nur schauen, ob bei jedem Zustand auch alle Ein- und Ausgänge vorhanden sind, allein dadurch kann man zumindest herausfinden, ob der DEA schon vollständig ist. Wie macht man das aber beim NEA, bei dem beim ein oder anderen Zustand für ein bestimmtes Symbol kein Ein- oder Ausgang vorgesehen ist?
+Karnickel Was meinst Du mit "vollständig"? Der Begriff sagt mir im Bezug auf NEAs nichts.
Leifaktor
Naja, wie in deinem ersten Video über einen DEA muss es einen Aus- oder Eingang für a und b geben, in jedem Zustand.
Ein Zustand hat also immer ein a und ein b.
Wenn man sich jetzt alle Zustände anschaut, dann darf es keinen Zustand geben, wo eine der Angaben fehlt.
Fehlt eine Angabe, dann weiß man, dass der DEA noch nicht vollständig ist.
Bei dem NEA ist dies ja nicht so, da hat ein Zustand z.B. nur das a, aber kein b, aber das macht es ja schwierig dies zu erkennen, für den fall, dass dieser Zustand ja doch einen b bräuchte, aber man schlichtweg vergessen hat einen einzuzeichnen.
.
+Karnickel Bei einem DEA braucht jeder Zustand für jedes Symbol aus dem Alphabet genau eine ausgehende Kante. Die eingehenden Kanten sind egal! Bei einem NEA gibt es keine Beschränkungen für die ein- oder ausgehenden Kanten, es können von jedem Zustand für jedes Alphabetssymbol beliebig viele (auch 0) Kanten ausgehen. Ich bin mir nicht sicher, ob ich die Frage jetzt richtig verstehe: Möchtest Du von einem gegebenen NEA herausfinden, ob es ein DEA ist? Dafür prüft man einfach für jeden Zustand, ob er genau eine ausgehende Kante für jedes Alphabetssymbol hat. Wenn ja, dann ist es ein DEA, wenn nicht, dann nicht.
Leifaktor
Das mit den ausgehenden Kanten meinte ich. Es muss in einem DEA für jedes Symbol eine ausgehende Kante geben. Damit weiß man, ob ein DEA vollständig ist. Man kann einfach schauen, ob überall die entsprechend notwendige Menge ausgehender Kanten vorhanden ist.
Bei einem NEA kann die Zahl für jedes Symbol 0 bis beliebig viele sein.
Man sieht also an dieser Anzahl nicht, ob bei einem Zustand noch etwas fehlt.
Darum geht es mir.
Wenn ich wissen will, ob ein DEA vollständig ist, dann zähle ich einfach die ausgehenden Kanten an jedem Zustand. Damit weiß ich, dass er vollständig ist, ich weiß damit natürlich noch nicht, ob er auch richtig ist.
Beim NEA bringt diese Zählerrei nichts. Wie erkennt man also, dass der NEA alle Kanten hat die er braucht?
"Wie erkennt man also, dass der NEA alle Kanten hat die er braucht?"
Brauchen wofür? Ein NEA "braucht" überhaupt keine Kanten: Jedes Objekt mit Zuständen, einem Startzustand, einem Alphabet, einer Menge von Endzuständen und irgendwelchen (oder gar keinen) Kanten ist ein NEA.
Oder meinst Du geht es Dir darum herauszufinden, ob der NEA eine bestimmte Sprache erkennt? Hierfür kann man nicht allgemein argumentieren: Es hängt immer von der Sprache ab, die man erkennen möchte, welche und wieviele Kanten man benötigt.
Wie konstruiert man genau die Zustände für Q'? Angenommen mein NEA hätte {1,2,3,4,5,6,7} Zustände, müsste ich es dann wie folgt aufdröseln?:
Q' {
0, 1, 2, 3,4,5,6,7,
12,13,14,15,16,17,
23,24,25,26,27,
34,35,36,37,
45,46,47,
56,57,
67
123,134,156,167,
234,245,256,257,
usw. ?
}
Danke für eine Antwort, auch wenn das Video schon etwas älter ist :)
+americanaccounts Ja, man muss systematisch alle Kombinationen durchgehen, so wie Du das schon angefangen hast. Wenn Q insgesamt n Zustände hat, dann hat Q' 2^n Zustände, in deinem Fall wären es also 2^7=128.
Reicht es nicht die Kombinationen zu wählen, die auch im NEA möglich sind? Also bei denen auch mehr als eine abgehende Kante für ein Symbol vorhanden ist? Andere Kombinationen würden im entstehenden DEA keine Verwendung finden oder? D: Ich bin verwirrt!
Habe ich das richtig verstanden? Bei 12 könnte ich auch das logische "oder"(v) verwenden, oder?
Welche Stelle genau meinst Du?
Ungefährt 07:30
Thomas Khlebovitch Richtig, wir können im Zustand 1 'oder' im Zustand 2 landen.
Und was, wenn der NEA mehrere startzustände hat?
Dann startet man für die Potenzmengenkonstruktion mit der Menge, die genau diese Startzustände enthält.
Komisch. Bei uns in der Vorlesung hatten wir Potenzmengenkonstruktion anders.
Bei uns sah das dann so aus: imgur.com/il6ep5y
Kann es sich hier um was anderes als eine Potenzmengenkonstruktion handeln?
Diese Tabelle ist nur eine andere Art, die Zustandsübergänge aufzuschreiben. Aber das Ergebnis ist genau das selbe!
Aber wieso wird da nicht auch q1 und q2 dargestellt und wo hat man da die q0,q1,q2 her?
In dem Bild hießen die Zustände des ursprünglichen Automaten q0, q1 und q2. Die Zustände des Potenzautomaten sind dann Mengen von Zuständen, also z.B. {q0}, {q0, q1}, {q0, q2}.
In meinem Video habe ich die Zustände des ursprünglichen Automaten 1 und 2 genannt. Die Zustände des Potenzautomaten, welche eigentlich Mengen sind, also dann z.B. {1}, {1,2} usw. habe ich abkürzend einfach nur 1 und 12 genannt. Bei 3:00 sage ich dazu, dass ich die Schreibweise vereinfacht habe.
Der Grund, weshalb nicht alle möglichen Mengen in dem Automaten dargestellt werden, ist, dass die anderen Zustände gar nicht erreichbar sind. Man könnte sie dazu schreiben, aber es gäbe keine Möglichkeit vom Startzustand dorthin zu kommen, deshalb kann man sie weglassen und die erkannte Sprache ist immer noch die gleiche.
Ah okay.
Desweiteren: Kann es sein dass wenn man einen Epsilon-NEA direkt in einen DEA verwandelt man ein anderes Ergebnis bekommt als wenn man einen Epsilon-NEA in einen NEA und dann den NEA mittels Potenzmengenkonstruktion in einen DEA verwandelt? (2 verschiedene DEAs)
Kommt darauf an. Was für eine Konstruktion benutzt Du denn, um einen Epsilon-NEA "direkt" in einen DEA zu verwandeln? Ich habe in dieser Videoreihe glaube ich keine solche Konstruktion vorgestellt, sondern nur Epsilon-NEA zum NEA und NEA zum DEA gezeigt.
a^+ b* oder? :D
Ja, so kann man die Sprache bezeichnen, die unser Beispielautomat hier erkennt.
Erst mal Top, dass Du die Videos hier machst und anderen hilfst TheoInf besser zu begreifen. Danke.
Nun zu meiner Frage: Warum steht die leere Menge in Mengenklammern beim DEA?
Die leere Menge ist ja schon ne Menge und darf für mein Verständnis nicht mehr in die Mengenklammern geschrieben werden.
Der DEA hat eine MENGE von Zuständen. Bei der Potenzmengenkonstruktion ist jeder dieser Zustände selbst wieder eine MENGE, also haben wir Mengen in Mengen. Die leere Menge ist einer dieser Zustände, die anderen wären {1}, {2} und {1,2}. Ich habe diese aber abgekürzt geschrieben als 1, 2 und 12, aber eigentlich sind das auch alles Mengen!
du brauchst zu lange
Im Video unter den Einstellungen bei Geschwindigkeit auf 1,25 Stellen. ;)
passt schon!
bin mittlerweile auf 1,5 haha