Klasse Videos. Wär allerdings schön gewesen nochmal ein Beispiel für die Einteilung von Nerode-Klassen durchzugehen. Wie du schon angemerkt hast ist dies evtl. schwerer.
Das geht denke ich auch anders herum, beispielsweise L = {c^(m) ° a^(n) ° b^(n) | m, n > 0}. Zwei Wörter w1 = c^(x) ° a^(i) ° b^(i-1) NICHT in L und w2 = c^(x) ° a^(i) ° b^(i-2) NICHT in L. Fügt man nun das Wort "b" hinzu, ist w1 in L, aber w2 nicht!
SherlockHomelezz Ich verstehe die Frage nicht, beziehst Du dich auf das Video? Du wirfst ein auch paar Begriffe durcheinander in deiner Frage! Eine Sprachklasse ist eine Menge von Sprachen, z.B. die regulären Sprachen, die kontextfreien Sprachen etc. Durch 0^n1^n wird genau eine Sprache beschrieben. Diese ist nicht regulär, was sich mit dem Satz von Myhill-Nerode oder dem Pumping-Lemma zeigen lässt. Weiterhin sind die Begriffe "erkennbar" und "regulär" äquivalent, die erkennbaren Sprachen sind also genau die regulären Sprachen. Ich weiß nicht, was Du mit "weil 0^n1^k nicht erkennbar ist aber 0^k1^k schon" meinst. Die Wörter der Form 0^n1^k mit beliebigen n und k bilden eine erkennbare Sprache. Unter anderen Bedingungen, etwa "n>k" oder "n=k", kann die Sprache auch nicht-erkennbar werden.
Ein interressantes Beispiel finde ich nur gerade sehr bezogen auf die Sprache. Gibt es da auch allgemeinere Ansätze oder muss man immer erst intuitiv die Sprache austricksen ?
Wenn wir den Satz von Myhill-Nerode auf eine Sprache anwenden wollen, dann müssen wir Äquivalenzklassen dieser Sprache bestimmen. Und diese hängen natürlich völlig von der Sprache ab. Also müssen wir jedes mal zunächst die Sprache untersuchen, wenn wir den Satz anwenden wollen. Wenn wir unendlich viele Klassen finden, ist die Sprache erkennbar. Wenn wir hingegen zeigen können, dass es nur endlich viele Klassen gibt, ist die Sprache erkennbar.
Hey! Man muss ja zeigen dass für jedes z aus sigma* gilt: xz ~ yz. Muss das z das ich anhängen will nicht auch aus L sein? Weil dann könnte man a^k nicht anhängen. Wie ist das genau?
Nein, dieses z muss nicht aus L sein. Die Definition gab es im vorigen Video: Zwei Wörter x und y sind äquivalent bzgl. L, wenn für jedes Wort z aus Sigma* gilt, dass xz und yz entweder beide in L oder beide nicht in L sind.
Hi, das ist das erste Deiner grossartigen Videos, mit dem ich auf Anhieb nicht ganz zurecht komme: wieso vergleichen wir unterschiedliche b^n, wenn es doch auf das Verhältnis b´s zu a´s ankommt?
Wir wollen mit dem Satz von Myhill-Nerode zeigen, dass die Sprache nicht erkennbar ist, d.h. wir müssen unendlich viele verschiedene Äquivalenzklassen der Nerode-Rechtskongruenz angeben. Für jede Klasse geben wir ein Wort an, nämlich b^n für jede natürliche Zahl n. Das heißt in einer Klasse ist z.B. das Wort bbb, in einer anderen das Wort bbbb. Wir zeigen, dass die Klassen verschieden sind, indem wir zweimal das gleich Wort an bbb und bbbb anhängen, sodass wir einmal ein Wort in der Sprache erhalten und einmal eines außerhalb der Sprache, in diesem Beispiel könnte man etwa aaa dranhängen, denn bbbaaa ist nicht in L, aber bbbbaaa schon. Wir zeigen, dass je zwei solche Wörter b^n und b^m in zwei unterschiedlichen Klassen liegen, für alle natürlichen Zahlen n ungleich m. Daraus folgt, dass die Nerode-Rechtskongruenz für L unendlich viele verschiedene Äquivalenzklassen hat, d.h. nach dem Satz von Myhill-Nerode: L ist nicht erkennbar. Intuitiv gesehen entsprechend die verschiedenen Äquivalenzklassen den verschiedenen Zuständen, die ein DEA bräuchte, um L zu erkennen. Wenn es unendlich viele verschiedene Klassen gibt, dann bräuchte ein DEA unendlich viele verschiedenen Zustände, um L zu erkennen. Aber ein DEA darf nur endlich viele Zustände haben, deshalb ist L in diesem Fall nicht erkennbar.
Vielen Dank für die ausführliche Antwort! Würde das also auch für eine unendliche Menge an Äquivalenzklassen gelten, die ALLE in der Sprache sind? Die Endlichkeit der Anzahl an Klassen ( des Index der Relation) ist das Kriterium für eine reguläre Sprache, nicht ob alle möglichen Wort-Paare in der Sprache liegen, richtig? Ich wünschte wir hätten Dich als Tutor gehabt ;) Deine Videos sind eine ganz grosse Hilfe, und dass Du auch noch Fragen beantwortest- einfach toll!
Deine Videos sind echt stark. Kein dunmes Gelaber, zack und los gehts. Und alles super erklärt.
Klasse Videos. Wär allerdings schön gewesen nochmal ein Beispiel für die Einteilung von Nerode-Klassen durchzugehen. Wie du schon angemerkt hast ist dies evtl. schwerer.
Die Äquivalenzklassen zu finden kann ein ziemlicher Brainf*ck sein... zumindest für mich ;-) Aber ein sehr gutes Video, gut erklärt.
same.
TheGI ist für mich eh Brainfck
Klausur in 1 Woche...RIP xD muss 24/7 NLogSpace ballern sonst wirds nix
@@adennis200 Ich hab 2 Tage um mich vorzubereiten :D wie liefs bei dir?
Vielen Dank ;)
du machst mir Theoretische Informatik gleich verständlicher :)
"tzjaaa reingelegt!" 😂 mega videos! Weiter so!
Dieser Satz ist super mächtig... danke für die glasklare Eklärung! Du rettest mir wahrscheinlich den Arsch morgen!
Starkes ding
der beste auf youtube, der erklären kann.
Frage: Ist epsilon immer eine eigene Äquivalenzklasse bzgl. Myhill-Nerode?
Das geht denke ich auch anders herum, beispielsweise L = {c^(m) ° a^(n) ° b^(n) | m, n > 0}. Zwei Wörter w1 = c^(x) ° a^(i) ° b^(i-1) NICHT in L und w2 = c^(x) ° a^(i) ° b^(i-2) NICHT in L. Fügt man nun das Wort "b" hinzu, ist w1 in L, aber w2 nicht!
Der Satz von Myhill - Nerode: Wann ist eine Sprache nicht regulär?
kann ich dann für die Sprachklasse 0^n1^n sagen, dass sie nicht regulär ist weil 0^n1^k nicht erkennbar ist aber 0^k1^k schon?
SherlockHomelezz Ich verstehe die Frage nicht, beziehst Du dich auf das Video?
Du wirfst ein auch paar Begriffe durcheinander in deiner Frage! Eine Sprachklasse ist eine Menge von Sprachen, z.B. die regulären Sprachen, die kontextfreien Sprachen etc. Durch 0^n1^n wird genau eine Sprache beschrieben. Diese ist nicht regulär, was sich mit dem Satz von Myhill-Nerode oder dem Pumping-Lemma zeigen lässt. Weiterhin sind die Begriffe "erkennbar" und "regulär" äquivalent, die erkennbaren Sprachen sind also genau die regulären Sprachen.
Ich weiß nicht, was Du mit "weil 0^n1^k nicht erkennbar ist aber 0^k1^k schon" meinst. Die Wörter der Form 0^n1^k mit beliebigen n und k bilden eine erkennbare Sprache. Unter anderen Bedingungen, etwa "n>k" oder "n=k", kann die Sprache auch nicht-erkennbar werden.
I love you and every video you've ever made
Könnte man genauso mit k
Toll erklärt und gutes Beispiel genommen! Danke für die Hilfe!
Ԑ ∈ {a,b}* oder nicht?
gut erklärt!
nice
STEFFEN?
Ein interressantes Beispiel finde ich nur gerade sehr bezogen auf die Sprache. Gibt es da auch allgemeinere Ansätze oder muss man immer erst intuitiv die Sprache austricksen ?
Wenn wir den Satz von Myhill-Nerode auf eine Sprache anwenden wollen, dann müssen wir Äquivalenzklassen dieser Sprache bestimmen. Und diese hängen natürlich völlig von der Sprache ab. Also müssen wir jedes mal zunächst die Sprache untersuchen, wenn wir den Satz anwenden wollen. Wenn wir unendlich viele Klassen finden, ist die Sprache erkennbar. Wenn wir hingegen zeigen können, dass es nur endlich viele Klassen gibt, ist die Sprache erkennbar.
Hey! Man muss ja zeigen dass für jedes z aus sigma* gilt: xz ~ yz.
Muss das z das ich anhängen will nicht auch aus L sein? Weil dann könnte man a^k nicht anhängen. Wie ist das genau?
Nein, dieses z muss nicht aus L sein. Die Definition gab es im vorigen Video: Zwei Wörter x und y sind äquivalent bzgl. L, wenn für jedes Wort z aus Sigma* gilt, dass xz und yz entweder beide in L oder beide nicht in L sind.
Ehrenbruder
Hi, das ist das erste Deiner grossartigen Videos, mit dem ich auf Anhieb nicht ganz zurecht komme: wieso vergleichen wir unterschiedliche b^n, wenn es doch auf das Verhältnis b´s zu a´s ankommt?
Wir wollen mit dem Satz von Myhill-Nerode zeigen, dass die Sprache nicht erkennbar ist, d.h. wir müssen unendlich viele verschiedene Äquivalenzklassen der Nerode-Rechtskongruenz angeben. Für jede Klasse geben wir ein Wort an, nämlich b^n für jede natürliche Zahl n. Das heißt in einer Klasse ist z.B. das Wort bbb, in einer anderen das Wort bbbb. Wir zeigen, dass die Klassen verschieden sind, indem wir zweimal das gleich Wort an bbb und bbbb anhängen, sodass wir einmal ein Wort in der Sprache erhalten und einmal eines außerhalb der Sprache, in diesem Beispiel könnte man etwa aaa dranhängen, denn bbbaaa ist nicht in L, aber bbbbaaa schon. Wir zeigen, dass je zwei solche Wörter b^n und b^m in zwei unterschiedlichen Klassen liegen, für alle natürlichen Zahlen n ungleich m. Daraus folgt, dass die Nerode-Rechtskongruenz für L unendlich viele verschiedene Äquivalenzklassen hat, d.h. nach dem Satz von Myhill-Nerode: L ist nicht erkennbar.
Intuitiv gesehen entsprechend die verschiedenen Äquivalenzklassen den verschiedenen Zuständen, die ein DEA bräuchte, um L zu erkennen. Wenn es unendlich viele verschiedene Klassen gibt, dann bräuchte ein DEA unendlich viele verschiedenen Zustände, um L zu erkennen. Aber ein DEA darf nur endlich viele Zustände haben, deshalb ist L in diesem Fall nicht erkennbar.
Vielen Dank für die ausführliche Antwort! Würde das also auch für eine unendliche Menge an Äquivalenzklassen gelten, die ALLE in der Sprache sind? Die Endlichkeit der Anzahl an Klassen ( des Index der Relation) ist das Kriterium für eine reguläre Sprache, nicht ob alle möglichen Wort-Paare in der Sprache liegen, richtig?
Ich wünschte wir hätten Dich als Tutor gehabt ;) Deine Videos sind eine ganz grosse Hilfe, und dass Du auch noch Fragen beantwortest- einfach toll!
Ԑ ∈ {a,b}* oder nicht?
Ja, das leere Wort ist in {a,b}* enthalten.