Pumping Lemma - Beispiele und Tricks

[@44r0n-9]

Prüfung in 1 Stunde. Daumen hoch.

[@schlukas6354]

Bestanden?

[@nilsmartel2295]

Ach Mensch, du bist schon einer der Guten. Wie viel Kraft und Arbeit selbst ein einziges Video kostet kann ich mir denken. Ich hoffe, dass dieser KZbin Kanal und deine Videos dir ich viel zurückgeben, Leuten wie mir bedeutest du und deine tolle Arbeit sehr viel

[@NLogSpace]

Vielen Dank für das Lob! :) Freut mich wirklich sehr, das zu lesen! Ja, die Videos machen tatsächlich eine Menge Arbeit, mehr als man vielleicht denkt: Strukturierung der Serien, Auswahl der Inhalte, Auswahl der Beispiele, Folien und Bilder überlegen und vorbereiten, Tafelbild überlegen, dann muss ich mir überlegen, was ich sage und welche Aspekte ich betonen will, übe die Texte ein paar mal. Die Roh-Aufnahme selbst ist meistens 2-3 mal so lang wie das endgültige Video, dann Audio nachbearbeiten, Video schneiden, Thumbnail erstellen, hochladen, Videobeschreibung schreiben, Tags eingeben. Je nach Video sind es dann meistens so 4-6 Stunden Arbeit insgesamt. Für die investierte Arbeit bekomme ich ehrlich gesagt nicht viel zurück. Gelegentlich bekomme ich solche motivierenden Kommentare und ab und zu sogar Spenden, das freut mich natürlich sehr und motiviert mich dazu, weiter zu machen! Aber auf Dauer ist dieser Kanal für mich zeitlich und finanziell gesehen ein großes Minusgeschäft, und die Aufrufzahlen bei neueren Videos stagnieren. Zugegeben, ich mache keine Werbung für den Kanal, fordere die Zuschauer quasi nie zum Abonnieren, Teilen und Unterstützen auf, denn genau diese Dinge stören mich an anderen Kanälen und ich möchte in meinen Videos einfach 100% Inhalt und nichts anderes haben. Mein Plan war eigentlich, dass ich irgendwann alle Themen abgedeckt habe, die man in einem Bachelorstudium in theoretischer Informatik lernt, und noch viele Themen darüber hinaus. Doch zur Zeit zweifel ich ein bisschen daran, ob das noch ein realistisches Ziel ist. Sorry für den langen Text, und nochmal herzlichen Dank dafür, dass Du meine Arbeit wertschätzt! :)

[@The99monti]

@@NLogSpace Hallo. Deine Antwort hat mich animiert mein erstes Kommentar auf KZbin zu verfassen! Ich finde deine mühevolle Arbeit unheimlich stark! Natürlich wäre es aus meiner Sicht durchaus berechtigt, wenn du Werbung schalten würdest - deshalb meinen größten Respekt, dass du deinem Prinzip treu geblieben bist! Danke! Du hast mir mit deinem Videos sehr geholfen! Auch dafür ein herzliches Dankeschön!

[@cheekycrex7684]

Respekt - hat mehr gebracht als 90min Vorlesung + 270min Tutorien. Richtig stark man, glaube du hast mir für die Prüfung den Arsch gerettet!

[@florian_d]

Wie läufts jetzt im Studium? :)

[@YSL069]

@@florian_d er hat abgebrochen

[@f1refly1337]

Wow, nachdem ich jetzt eine halbe Stunde vor dem Skript der Dozentin verzweifelt bin habe ichs endlich verstanden. Super Video, sachlich und verständlich!

[@josefoalmo1858]

also vor deinen videos habe ich schwarz gesehen, aber jetzt sehe ich ein helles Licht! Habe in 3 Wochen meine Klausur in Informatik und das Skirpt ist sehr zäh. Durch deine Videos muss ich sagen, dass alles doch sehr interessant ist und die Informatik mehr als nur programmieren ist! Wenn die Klausur bestanden ist, werde ich hierher zurück kehren und mach dir schonmal einen Termin für einen gemeinsamen Döner! Du hast dir absolut einen Döner auf meinen Nacken verdient

[@NLogSpace]

Viel Erfolg bei der Prüfung! :)

[@lillol3245]

Ach, den shit werden 99% der Informatikabsolventen nie wieder sehen im Berufsleben. Unnötiges Siebmodul. Sollte ein Wahlpflichtmodul sein..

[@randomacc_delete4614]

Vielen Dank! Klausur lief zwar nicht wie erhofft aber zumindest musste ich dank dir nie in die Vorlesung.

[@NacToYT]

Extrem gute Erklärung (also die ganze Reihe) Ich hoffe, die Prüfung morgen wird dann auch was mit den Tricks

[@NacToYT]

Hat super geklappt. Ich finde, in der Uni wird es auch nicht wirklich gut beigebracht bzw. vorgestellt. Wenn man das Pumping Lemma nur für das Widerlegen der regulären Sprache verwendet, wieso wird es nicht so umgedreht wie in dieser Reihe?

[@rhanx8689]

Bruh was meinst du mit umgedreht?

[@Meodoc]

Beste Erklärung mann, hilft echt mal das Gewusel im Skriptum zu verstehen!

[@mr.parodie7225]

Der passiv-aggressive WM witz hat mich zum abonnieren überzeugt haha, viel dank für die guten videos ^^

[@cube2fox]

Bittere Erkenntnis: Nicht die Erklärungen der Pumping-Beweise sind schlecht, sondern ich bin zu dumm sie zu verstehen.

[@privatprivat6629]

Ist es normal sowas in der 7 klasse zu lernen

[@Themasterpeer99]

@@privatprivat6629 Ja klaro, wir hatten das schon im Kindergarten

[@tonikaiser2823]

Ich kannte das schon bevor ich geboren wurde.

[@evasion4510]

@@privatprivat6629 Ich kannte es als ich noch im samenleiter von meinem dad war

[@dazzle5350]

Ich kannte es schon, als ich es noch nicht kannte

[@oliveryt7168]

Diese Herangehensweise/ Methode hast du sehr verständlich gestaltet und erklärt. Bravo! :-D

[@uwuwaifu101]

jeder der das Pumping Lemma für Schule oder Uni je braucht kommt früher oder später hier auf deinem Kanal vorbei, um es zu verstehen :D Vielen Dank @NLogSpace :) Spitze Erklärung - mit noch ein wenig Übung dürfte das jetzt wohl bei mir klappen :D

[@NLogSpace]

Danke, das freut mich! :)

[@ziangduan9699]

sehr guuuuuuuuuuuuuuuuuuuuuuuut! Du hast mein Studium geretted mit solchen tollen Videos!!!

[@RockyToast94]

Richtig gutes Video, vielen Dank 😊 Klausur am Mittwoch ✌🏼

[@moali_yil5559]

wie war?

[@Cyber_Chriis]

Für den WM Witz bei 1:40 gibts den Like schon vor Ende des Videos :D

[@anonymouscommentator]

Echt vielen Dank, genau nach so einer Erklärung habe ich gesucht!

[@herrhupfdohle8227]

Gute Beispiele! Sehr hilfreich, Daumen hoch! Könntest du noch Beispiele für Kontextfreie Sprachen machen? Müssen keine 3 Videos sein, evtl. kurzes Intro mit den Bedingungen (die sind ja so ähnlich wie bei regulären Sprachen) und dann direkt ein paar Beispiele zeigen, das wäre top! :)

[@NLogSpace]

Zum Pumping-Lemma für kontextfreie Sprachen habe ich zwei Videos auf meinem Kanal, darin zeige ich auch einen Beispiel-Beweis. Irgendwann überarbeite ich diese Videos vielleicht auch nochmal, aber zur Zeit haben erstmal andere Themen Priorität.

[@resolut1on118]

Danke das du für solche Themen Videos machst!

[@rebeccah2415]

Super erklärt, vielen Dank! Perfekt als Begleitung zum Uni-Skript :)

[@privatprivat6629]

Ist es normal sowas in der 8 Klasse zu lernen (14J)

[@lillol3245]

@@privatprivat6629 nein.

[@secrety7623]

Dank dir hab ich es endlich richtig verstanden. Vielen vielen Dank für das tolle Video

[@FabianReschke]

Das Problem ist immer: Ich verstehe die Beispiele und alles, aber selber drauf kommen würde ich nie :(

[@abail7010]

Will zwar niemand (einschließlich mir) hören aber üben hilft :D

[@FabianReschke]

@@abail7010 Hab die Klausur bestanden, ab jetzt ist mir das Pumping Lemma eh egal :P Das wird mit Sicherheit nicht mein Schwerpunkt

[@leonda4817]

Ist glaub ich normal, geht mir genau so. Man lernt die typischen Beispiele kennen, und schafft dann bei der Klausur ein Ähnliches.

[@Gereon_]

@@leonda4817 Ist halt wieder dieses typische "für die Klausur lernen". Irgendwie belastend.

[@julianvelten1304]

Starke Reihe, danke dir!

[@derGerhart]

hat mir tatsächlich was gebracht. das wollte irgendwie wochenlang kein sinn für mich machen. Danke!

[@monhern2]

Sehr gute Beispiele und Erklärung. Danke!

[@DaniaMadani]

vielen Dank für die Videos

[@odayzahra6496]

Vielen Dank für das Video :)

[@flumi4175]

So gut erklärt! DANKE

[@Dacapoelcodaa]

viel viel besser als die Vorlessung

[@L0Ls0ul]

Tolles Video! Bin ich eigentlich der einzige, der es sich anguckt, obwohl er nicht kurz vor ner Klausur ist? :'D

[@leenajamil7187]

ne ^^

[@philh6316]

Super anschauliche Beispiele! Vor allem vergesse ich immer dass bei den Informatikern die 0 in den Natürlichen Zahlen liegt^^. Nur bei 11:39 ist dir mit der Wortlänge ein kleiner "Fehler" unterlaufen. War ziemlich amüsant weil du vorher meintest: "Das Y hat auch noch'n paar. Ist uns eigentlich egal wie viele hier genau."

[@Stibitzwegerich]

Vielen Dank für das Video

[@SunshineFromWithin]

Super videos!

[@NLogSpace]

Danke! :)

[@maximscholtz5251]

gut erklärt hilfreiches video

[@chda8256]

"Falls nicht, gebt nen Daumen runter." Erfrischend :D Aber der Daumen zeigt natürlich nach oben.

[@luisa1551]

I have a question about the first example: based on the lemma, Y has to be different from epsilon, the empty word. But if I choose i=0, Y will be epsilon. Would it be that against the second condition to win the game? Thanks

[@NLogSpace]

Note that Y and Y^i are two different things! Y can not be the empty word, but Y^i can.

[@fiNalY4live]

Werd mal bitte Prof. dann habens wenigstens ein paar Studenten gut xD

[@Themogawave]

Super erklärt, danke dir. Kurze Frage: Hätte man bei Beispiel 2 auch das i=0 setzen können um zu beweisen, dass die Sprache nicht regulär ist?

[@NLogSpace]

i=0 klappt fast immer, allerdings nicht wenn p=1 war. Dann ist nämlich w=a, also die einzig mögliche Zerlegung ist w=xyz mit x=epsilon, y=a, z=epsilon und wenn wir jetzt i=0 setzen, dann ist xy^iz = epsilon, was ein Wort in der Sprache ist. i=2 klappt hingegen immer, da wir das Wort dadurch länger machen und da die "Lücke" von p^2 zu (p+1)^2 groß genug ist, die Lücke zwischen p^2 und (p-1)^2 ist ein bisschen kleiner.

[@filmfranz]

@@NLogSpace wenn i € N, dann ist die kleinste Zahl in N = 1. Daher müsste N als N0 bezeichnet werden wenn es die Null enthält. Oder ist das nur ein regionaler Unterschied?

[@NLogSpace]

In der Informatik (und auch in meinen Videos) nimmt man oft die 0 zu N dazu.

[@BooBar2521]

wirklich ein klasse video! hab keinen gefunden der das so schön und strukturiert erklärt wie du. Ich verstehe beim letzten beispiel nur leider nicht wieso nun am ende das die länge des wortes keine primzahl sein kann?

[@NLogSpace]

Danke! Die Länge kann keine Primzahl sein, denn eine Primzahl kann man nicht darstellen als das Produkt von zwei ganzen Zahlen größer 1. Doch genau das haben wir dort gezeigt. Die Länge lässt sich darstellen als das Produkt von |x|+|z| und |y|+1. Beide Zahlen sind mindestens 2. Die erste, weil |xy| höchstens p ist, aber |xyz|=p+2, also |z|>1, und die zweite weil y nicht leer ist.

[@dxamphetamin]

Geiles Video. Vielen Dank

[@seydaakkaya3035]

Könntest du vll das 3. Beispiel mit dem Prinzip vom 2. Beispiel aufschreiben?

[@Hubert_Schoelnast]

Zum 1. Beispiel: Der grüne Spieler könnte auch die folgende Zerlegung wählen: x=a^(p+1), y=b, z=b^(p-1). y muss also nicht zwingend (mindestens) ein a enthalten. In diesem Fall ist aber xy^(p)z = a^(p+1)b^(p)b^(p-1) = a^(p+1)b^(2p-1) eine aufgepumpte Version, die erkannt wird, aber nicht zur Sprache gehört. Als dritte Möglichkeit könnte der grüne Spieler auch das wählen: x=a^p, y=ab, z=b^(p-2). Das ist aber leicht, denn dann ist xyyz = ....aaababbb... ein ungültiges Wort, das erkannt wird.

[@NLogSpace]

Beachte, dass bei beiden Zerlegungen, die Du nennst, die Bedingung |xy| ≤ p verletzt ist. Diese Zerlegungen sind also keine erlaubten Züge für den grünen Spieler. Ich verstehe aber, wie Du darauf kommst: Es gibt verschiedene Formulierungen des Pumping-Lemmas, und manchmal wird die Bedingung |xy| ≤ p weggelassen. Ich arbeite hier aber mit der Version, die im Video links eingeblendet ist, also wo der grüne Spieler die Bedingung |xy| ≤ p erfüllen muss.

[@huydang6059]

Wie würde man jetzt die Primzahl Aufgabe mir der vorherigen Methode lösen?

[@Hubert_Schoelnast]

Zum 3. Beispiel: Im Video wird mehrfach gesagt, dass (|x|+|z|) größer als 0 ist. Aber der grüne Spieler kann auch wählen x=ε, y=w, z=ε. Das ist ja eine durchaus erlaubte Wahl. Dann ist aber (|x|+|z|) genau gleich 0. Der Beweis funktioniert dann noch genau so, denn i=0, und xy^(i)z=ε, also das leere Wort mit der Länge 0, und 0 ist ebenfalls keine Primzahl (0 ist durch jede Zahl teilbar).

[@NLogSpace]

Nein, das ist keine erlaubte Wahl, aus dem gleichen Grund wie bei deinem anderen Kommentar: Der grüne Spieler muss die Bedingung |xy| ≤ p erfüllen und wir haben extra ein Wort der Länge mindestens p+2 gewählt. Er kann also nicht das ganze Wort in y unterbringen.

[@sebastiangobel7142]

Tolle Erklärung aber warum darf man y = 0 setzen, obwohl wir zuvor festgelegt haben das y ungleich dem leeren Wort sein muss oder unterscheidet sich das nochmal? Fände ein paar Beispiele noch sehr hilfreich, welche zeigen das mittels Pumping Lemma keine Aussage über eine Sprache getroffen werden kann.

[@NLogSpace]

y ist ein Wort, d.h. wir können gar nicht "y=0 setzen". Wir setzen auch nirgends y=epsilon (leeres Wort), denn das ist nicht erlaubt. Aber man darf i=0 setzen, das ist der Multiplikator für das y, also wie oft das y im gepumpten Wort auftaucht.

[@redma1248]

Wäre i=0 im zweiten Beispiel nicht auch eine valide Lösung? Wenn y^i verschwindet dann ist es ja auch nicht möglich die letze potenz zu treffen, da |xy|

[@chrisaes3235]

Hey! Darf ich eigentlich im Notfall für p einen Mindestwert annehmen? Oder pfusche ich damit dem Gegner ins Handwerk? Danke! :)

[@NLogSpace]

Der Gegenspieler wählt eigentlich das p, Du hast also keinen Einfluss darauf. Man kann sich jedoch überlegen, dass die Aussage, die Du für dieses p zeigen musst, monoton in p ist, d.h. wenn Du die Aussage für irgendeine Zahl p zeigen kannst, dann gilt sie auch für alle kleineren Zahlen p. Also zusammengefasst: Ja, es reicht, wenn man die Aussage nur für alle p ab irgendeinem Mindestwert zeigt.

[@chrisaes3235]

@@NLogSpace Danke schön :)

[@TomasGiaoBarbosa]

"ANMERKUNG ZU BEISPIEL 3: Ich gebe als Beispiel x=a^3, y=a^2 und z=a^5 an, dann wäre aber xyz=a^10 und 10 ist keine Primzahl, ist also ein schlechtes Beispiel. Stellt Euch einfach vor y=a^3, dann wäre xyz=a^11. Wenn man dann i=|x|+|z|=8 wählt, bekommt man |xy^iz| = 32, was keine Primzahl ist." Aber wenn wir uns vorstellen, dass y=a^3 konnten waere es noch leichter einfach zu beweisen, dass es keine regulare Sprache ist oder? Weil wenn y=a^3, und |w|= eine Primzahl ist, wissen wir, dass |w| eine ungerade Zahl oder 2 ist, da wir das Wort ja wahlen, konnen wir einfach sagen, wir nehmen nicht 2 "aa" und dann konnen wir einfach i^2 nehmen, da |w| + |y| immer eine gerade Zahl sein wird und alle gerade Zahlen ausser 2 sind keine Primzahlen

[@lightblue254]

Grüße raus an die Deutsche Nationalmannschaft :D

[@Mosil0]

Tolles Video! Beim dritten Beispiel, könnte man es auch irgendwie so argumentieren? Es muss immer ein i |x y^(i+1) z| ≡ (r-1) mod (y+1), und daher muss r irgendwann den Wert 0 annehmen. Also ohne ein konkretes i zu wählen?

[@nhatlam96]

8:59: "y ist höchstens so lang wie p". sei |y| = p, folgt dann |x| = 0 und ist |x| = 0 erlaubt? Gehört das dritte Beispiel zu den schwierigen Aufgaben? Ich wäre nicht darauf gekommen...

[@cedescc7986]

Meeeeega, vielen vielen vielen dank!

[@njulian.7376]

wie kann man wissen dass die länge von x und y jeweils 3 und 5 bei Beispiel 3 ist.?

[@ЛилияКолесник-к9ь]

Kennst du schon vielleicht die Antwort auf deine Frage?👀 ich kann es immer noch nicht verstehen 🙈

[@RoBert-og7jo]

Könnte man nicht bei Beispiel 2 auch argumentieren, dass eine reguläre Grammatik nur Produktionen der Form V->uA bzw V->u mit {V,A} Variablen und u Terminal der Länge 1 enthalten darf und man so unmöglich die "Distanz" zwischen den Worten "überbrücken" kann? Vorausgesetzt natürlich, es wird nicht explizit ein Pumping-Lemma-Beweis gefordert? Anyway, vielen vielen Dank für dieses Videos!

[@NLogSpace]

Man kann mit regulären Grammatiken "Distanzen" zwischen Wörtern überbrücken, z.B. alle Worte, deren Länge durch 3 teilbar ist: S -> aT | epsilon, T -> aR, R -> aS. In dieser Sprache gibt es keine Wörter der Länge 1, keine Wörter der Länge 2, aber ein Wort der Länge 3. Das Problem sind die immer länger werdenden Distanzen. Man könnte sicherlich auch versuchen, direkt zu argumentieren, dass es keine reguläre Grammatik gibt, die die Sprache aus dem Video erkennt. Allerdings müsste man dann auch größere Mengen von Variablen betrachten, nicht nur 2 Stück. Die Anzahl der Variablen entspricht nämlich in etwa der Anzahl der Zustände, die nötig ist, um eine Sprache zu erkennen.

[@RoBert-og7jo]

@@NLogSpace Ich erkenne meinen Denkfehler, danke für die prompte Antwort!

[@pyuc]

3:07 ich verstehe einfach nicht warum sich x und y innerhalb der a's befinden. Woran sieht/erkennt man das? Oder ich das einfach eine festgeschriebene Regel, sobald das Pumping Lemma anwendbar ist, sind bei Aufteilung des Wortes in uvw uv immer in den ersten Part des Wortes oder wie ist das zu verstehen?

[@NLogSpace]

Ja, wir zerlegen das Wort w in drei Teile xyz. Zerlegen bedeutet, dass der erste Teil x ist, dann kommt y und dann kommt z, und wenn man alle drei Teile hintereinanderkonkateniert bekommt man genau das Wort w. Die Begründung habe ich dann genau an der Stelle im Video genannt, und zwar gibt uns das Pumping Lemma die Aussage |xy| < p. Da die ersten p Symbole von unserem Wort nur aus a's bestehen und xy der Anfang des Wortes ist, bestehen x und y nur aus a's.

[@pyuc]

@@NLogSpace Okay danke für die Antwort. Mir ist das ganze jetzt schon mal etwas klarer geworden. Aber was ist, wenn unsere Sprache zum Beispiel aus {a^n b^n c^n d^n e^n} besteht. Wie würde dann die Aufteilung hier aussehen bzw. was wäre hier dann xy?

[@SumbaSlice]

Bei 8:23 sagst du, dass aus y ungleich leeres Wort folgt, dass xy^2z strikt größer als xyz ist. Kann es aber nicht auch sein, dass die gleich groß sind, wenn y nämlich genau ein Buchstabe ist? Dann wäre xy^2z nicht strikt größer, sondern nur größergleich xyz. Was habe ich übersehen?

[@NLogSpace]

Auch dann ist xy^2z strikt länger als xyz, nämlich einen Buchstaben länger, da das Wort y verdoppelt wurden. Beachte, dass die Schreibweise y^2 nichts mit Exponentialrechnung zu tun hat, sondern y^2 steht einfach für das Wort yy.

[@SumbaSlice]

@@NLogSpace Du hast absolut recht. Genau das war mein Denkfehler. Vielen Dank.

[@jakobjwdi]

mal ganz nebenbei die nationalmannschaft zerstoert xD

[@thomasdieter9302]

Wieso kann er i=0 setzen? y soll doch ungleich dem leeren Wort sein.

[@NLogSpace]

Das ist kein Widerspruch. y und y^i sind zwei verschiedene Dinge. y ist nicht das leere Wort, aber y^i darf das leere Wort sein, und ist es auch, wenn i=0 ist.

[@dazzle5350]

Hey, kleine Frage: L = {w1#w2#w3 | w1 != w2 != w3} wi element von {1,0}, ist die Sprache kf? Ein Freund und ich verzweifeln gerade ein wenig daran, weil das in einer Altklausur gewesen sein soll (angeblich), kommen nämlich auf kein passendes i. Ansonsten top Video wie auch der Rest! :) Vielen Dank im voraus, Gruß

[@xGeicher]

Hi, wenn L eine reguläre Sprache ist, dann (und nur dann) ist auch das Komplement von L regulär. Mit dem Komplement von L kannst Du einfach zeigen, dass es nicht regulär ist. ( |w1| = p, |w2| = p, |w3| = p) Anschließend setzt du i = 2, so dass |w1| != |w2|. Damit is das Komplement von L nicht regulär. Daraus folgt, dass L ebenfalls nicht regulär sein kann.

[@alrahiqalmakhtoum6249]

Hallo, ich brauche Hilfe. Könnte jemand mir helfen? Meine Prüfung nächste Woche. Danke

[@alternativ1322]

Warum P+2, ich checks nicht.

[@jerome8660]

Bezüglich des ersten Beispiels: Du wählst das Wort a^(p+1)b^p und du beweist, dass dieses Wort nicht in der Sprache ist. Dieses Wort kann aber nur die Form aaabb, aab, aaaabbb, usw. haben. Was ist mit Wörtern wie abaaabab? Oder reicht es ein Gegenbeispiel zu finden, um die Regularität zu beweisen? MfG

[@Hubert_Schoelnast]

Die gegebene Sprache enthält _ALLE_ Wörter, die mehr a's als b's enthalten. Du sollst beweisen, dass es keinen endlichen Automaten geben kann, der diese Sprache beherrscht. DIe Sprache zu beherrschen heißt: Der Automat kann dir bei jedem beliebigen sagen, ob es zur Sprache gehört, oder ob es nicht zur Sprache gehört. Die Aufgabe lautet daher: "Beweise, dass es keinen endlichen Automaten geben kann, der ALLE Wörter erkennt, die mehr a's als b's enthalten". Der Beweis läuft so ab, dass man dir jeden beliebigen Automaten vorlegen kann. Du muss dann zu diesen Automaten nur ein einziges Wort finden, dass zwar zur Sprache gehört, aber vom Automaten nicht erkannt wird. Dieses eine Wort beweist, dass der Automat, den man dir vorgelegt hat, nicht in der Lage ist, wirklich _ALLE_ Wörter zu erkennen, die zur Sprache gehören. Und weil du ein Schema hat, mit dem es dir gelingt, zu jedem beliebigen Automaten, den man dir gibt, ein Wort zu finden, das beweist, dass der Automat daran scheitern wird, ist damit bewiesen, dass es keinen endlichen Automaten geben kann, der diese Sprache erkennen kann. Dass es Automaten gibt, die ein paar Wörter aus der Sprache erkennen können, macht nichts. Ein Automat erkennt eine Sprach nur dann, wenn er _JEDES_ Wort, das zur Sprache gehört, erkennt, und wenn er zugleich jedes Wort, das nicht zur Sprache gehört, nicht erkennt.

[@jerome8660]

@@Hubert_Schoelnast Danke für die ausführliche Antwort, bin aber durch mit dem Modul :D Wird hoffentlich noch anderen helfen:)

[@MariaSteinbrecher]

was ist eigentlich i?

[@4538304544]

Das Ausklammern bei 12:48 min habe ich leider nicht ganz verstanden .. 😓

[@NLogSpace]

Das ist ganz normales Ausklammern, wie man es aus der Schule kennt. Dort steht |x| + |y|*(|x|+|z|) + |z|. Also in der Mitte steht |y| mal die Länge von x und z, und die beiden Summanden vorne und hinten zusammen sind noch ein weiteres mal die Länge von x und z. |y| * (|x| + |z|) + 1 * (|x| + |z|) = (|y| + 1) * (|x| + |z|)

[@sophiabnrm8730]

Sehr gut und verständlich erklärt! Habe aber eine sicherlich laienhafte Frage zum Beispiel 2: Sprachen sind doch regulär, wenn ich einen Automaten für sie finden kann. Nun kann ich doch für a^n^2 einen erstellen, der erst ein 'a' einliest und dann in einen möglichen Endzustand kommt, dann muss er weitere 3 'a' einlesen bis er zu einem Endzustand kommt, dann weitere 5 'a' bis ein Endzustand erreicht ist, etc. Wieso ist die Sprache nun nicht regulär, obwohl sie durch einen Automaten akzeptiert wird? Danke im Voraus

[@NLogSpace]

Mrs. Man Der Automat, den du beschreibst, hätte unendlich viele Zustände. Ein endlicher Automat muss aber immer endlich viele Zustände haben.

[@zeronothinghere9334]

Ich weiß, ist ein bissl late so ein Jahr danach, aber schau mal die anderen Videos auf der Playlist vom Uploader zum Pumping Lemma an, da erklärt er es

[@95Coaster]

Shots fired at DFB :D

[@grippenbube3432]

ich verstehe nicht wie bei den primzahlen aus y^i da y*i wird, weil 3 hoch 3 ist ja nicht = 3 * 3

[@h8965-d4q]

Weil du hier mit keinen Zahlen rechnest. y^15 würde bedeuten das da 15 mal a steht ^^.

[@aji2847]

Ich verstehe die erste Aufgabe nicht ganz. Wenn i=0 ist, dann ist doch unser y = Epsilon. Hat das jemand verstanden?

[@NLogSpace]

@@aji2847 Die Frage wurde schon mehrfach in den Kommentaren beantwortet!

[@aji2847]

@@NLogSpace alles klar. Ich hatte vorher durchgescrollt und die Frage nicht auf Anhieb unter den Kommentaren gefunden

[@powermax6391]

4:50 etwas irreführend ohne Klammersetzung. (a^n)^2 oder a^(n^2). Erst nachdem Du sagtest, dass 9 a´s ebenfalls in der Sprache, war es klar,

[@NLogSpace]

Hi powermax. Potenzen sind in der mathematischen Notation grundsätzlich rechtsassoziativ zu lesen, also wenn man a^b^c schreibt, dann ist immer a^(b^c) gemeint. Es wäre also unüblich diese Klammern zu setzen.

[@powermax6391]

@@NLogSpace hätte lieber Mathe als Zweitfach wählen sollen. ;)

[@Lucas-so2hu]

Erstmal die Nationalmannschaft fronten haha

[@Amin-ve2xs]

Wenn man so was in der Klausur schreibt, dann erhält man nicht die volle Punkte oder gar Kein Punkt, weil die Argumente fehlen!

[@nanetteserzfeind9820]

In einer Stunde Prüfung. Hoffentlich wird das was.

[@Littlefighter1911]

3:42 Ich verstehe das noch immer nicht so ganz. Wenn der "Gegner" uns die Zerlegung vorgibt. Dann kann er uns doch die Zerlegung: x= a^p y= a z = b^p vorgeben? Aber er gibt sie uns nur mit |xy| kleiner gleich P Warum sollte er das machen?

[@_n_bl_3998]

Hallo :) Könntest du vielleicht folgendes Beispiel nochmal machen bitte: L := L((a ∪ b) ^∗ · (aa ∪ bb) · (a ∪ b)^* ) ∪ {w ∈ {a, b}^∗ | |w| ist Primzahl} Danke

[@NLogSpace]

Habe das Gefühl, dass die einfache Variante des Pumping-Lemmas hier nicht ausreicht. Der Gegner wählt n. Wir haben zwei Optionen: 1. Wir können ein Wort mit Infix aa oder Infix bb wählen. Aber da die erste Teilsprache regulär ist, wird der Gegner in diesem Fall gewinnen können: Er wählt die Zerlegung so, dass dieses Infix aa oder bb nicht in y liegt, sodass wir es nicht entfernen können und am Ende (nach pumpen) wieder ein Wort aus L erhalten. 2. Wir wählen ein Wort von Primzahllänge, das nicht das Infix aa und auch nicht das Infix bb hat. Dann muss das Wort also abwechselnd abababab.... sein, die Länge insgesamt eine Primzahl. Nun kann die Gegner jedoch y so wählen, dass es mit dem gleichen Symbol beginnt wie es endet. Damit sorgt er dafür, dass wir egal wie oft wir y wiederholen, oder y weglassen, auf jeden Fall ein Wort mit Infix aa oder Infix bb erzeugen, also wieer ein Wort in L erhalten. Also wenn Du zeigen willst, dass diese Sprache nicht erkennbar ist, versuche es mal mit einer stärkeren Version des Pumping-Lemmas (habe ich nicht in meinen Videos vorgestellt) oder mit dem Satz von Myhill-Nerode.

[@_n_bl_3998]

@@NLogSpace Genau. Wir sollten zeigen, dass die Sprache die Pumpingeigenschaft hat und anschließend aber noch, dass sie nicht regulär ist. Mit Myhill - Nerode kommt man wahrscheinlich darauf, dass es unendlich viele Äquivalenzklassen gibt, und die Sprache darauf hin nicht regulär ist. Oder? Vielen Dank auf jeden Fall für deine Antwort. :)

[@umurfurkanonbasi5359]

1:50 WM 2022 auch

[@ML-wj5wp]

Gutes Fideo

[@tampelmarta9510]

das video pumping pumpimg lemma lemma lemma lemma lemmm lem lem lem lem lem lem lem lem l

[@Seff2]

von was für einem Gegner gegen den man gewinnen muss redest du? wtf...

[@NLogSpace]

Im vorigen Video "Pumping Lemma - Beweisschema" habe ich erklärt, wie man das Pumping Lemma als ein 2-Personen-Spiel verstehen kann.

[@hanktobe]

Damn this isnt english

[@NLogSpace]

I have an english channel as well, but there are very few videos so far. No pumping lemma yet, sorry!

[@hanktobe]

@@NLogSpace Youre all good I watched this video anyways with auto translate and it helped. Thank you for making the vid

[@zeronothinghere9334]

@@NLogSpace What do you think about adding dedicated english subtitles?

[@zCrouchy]

Super Videos, vielen vielen Dank