Pumping Lemma - Beispiele und Tricks

Sdílet
Vložit
  • čas přidán 20. 07. 2018
  • 0:41 Beispiel 1
    4:35 Beispiel 2
    9:44 Beispiel 3
    15:05 Tipps und Tricks
    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.
    Wir sehen uns einige Beispiele für Beweise mit dem Pumping Lemma für reguläre Sprachen an und zeigen jeweils, dass die Sprachen nicht erkennbar sind. Außerdem sehen wir uns einige Tricks und Faustregeln an, nach denen man sich richten kann, um einen Beweis mit dem Pumping Lemma erfolgreich durchzuführen.

Komentáře • 140

  • @44r0n-9
    @44r0n-9 Před 4 lety +132

    Prüfung in 1 Stunde. Daumen hoch.

  • @cheekycrex7684
    @cheekycrex7684 Před 4 lety +80

    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
      @florian_d Před rokem

      Wie läufts jetzt im Studium? :)

    • @YSL069
      @YSL069 Před rokem +8

      @@florian_d er hat abgebrochen

  • @nilsmartel2295
    @nilsmartel2295 Před 3 lety +25

    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 CZcams Kanal und deine Videos dir ich viel zurückgeben, Leuten wie mir bedeutest du und deine tolle Arbeit sehr viel

    • @NLogSpace
      @NLogSpace  Před 3 lety +48

      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
      @The99monti Před rokem +5

      @@NLogSpace Hallo. Deine Antwort hat mich animiert mein erstes Kommentar auf CZcams 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!

  • @f1refly1337
    @f1refly1337 Před 4 lety +19

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

  • @cube2fox
    @cube2fox Před 5 lety +165

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

    • @privatprivat6629
      @privatprivat6629 Před 5 lety +3

      Ist es normal sowas in der 7 klasse zu lernen

    • @Themasterpeer99
      @Themasterpeer99 Před 5 lety +68

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

    • @tonikaiser2823
      @tonikaiser2823 Před 5 lety +18

      Ich kannte das schon bevor ich geboren wurde.

    • @evasion4510
      @evasion4510 Před 5 lety +13

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

    • @dazzle5350
      @dazzle5350 Před 4 lety +17

      Ich kannte es schon, als ich es noch nicht kannte

  • @randomacc_delete4614
    @randomacc_delete4614 Před rokem +6

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

  • @josefoalmo1858
    @josefoalmo1858 Před 2 lety +7

    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
      @NLogSpace  Před 2 lety

      Viel Erfolg bei der Prüfung! :)

  • @Cyber_Chriis
    @Cyber_Chriis Před 3 lety +12

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

  • @FabianReschke
    @FabianReschke Před 4 lety +44

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

    • @abail7010
      @abail7010 Před 4 lety

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

    • @FabianReschke
      @FabianReschke Před 4 lety +7

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

    • @leonda4817
      @leonda4817 Před 3 lety +1

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

    • @Gereon_
      @Gereon_ Před 3 lety +4

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

  • @Meodoc
    @Meodoc Před 4 lety +10

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

  • @NacToYT
    @NacToYT Před 5 lety +32

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

    • @NacToYT
      @NacToYT Před 5 lety +2

      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
      @rhanx8689 Před 4 lety

      Bruh was meinst du mit umgedreht?

  • @oliveryt7168
    @oliveryt7168 Před 3 lety +2

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

  • @mr.parodie7225
    @mr.parodie7225 Před 3 lety +2

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

  • @uwuwaifu101
    @uwuwaifu101 Před 2 lety +5

    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

  • @secrety7623
    @secrety7623 Před 5 lety +5

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

  • @resolut1on118
    @resolut1on118 Před 5 lety +2

    Danke das du für solche Themen Videos machst!

  • @RockyToast94
    @RockyToast94 Před 5 lety +12

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

  • @anonymouscommentator
    @anonymouscommentator Před 3 lety +1

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

  • @chda8256
    @chda8256 Před 3 lety +4

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

  • @julianvelten1304
    @julianvelten1304 Před 4 lety +3

    Starke Reihe, danke dir!

  • @ziangduan9699
    @ziangduan9699 Před 4 lety +2

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

  • @monhern2
    @monhern2 Před 5 lety +1

    Sehr gute Beispiele und Erklärung. Danke!

  • @rebeccah2415
    @rebeccah2415 Před 5 lety +6

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

  • @herrhupfdohle8227
    @herrhupfdohle8227 Před 6 lety +4

    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
      @NLogSpace  Před 6 lety +2

      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.

  • @fiNalY4live
    @fiNalY4live Před 4 lety +27

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

  • @flumi4175
    @flumi4175 Před 5 lety +1

    So gut erklärt! DANKE

  • @DaniaMadani
    @DaniaMadani Před 5 lety +3

    vielen Dank für die Videos

  • @derGerhart
    @derGerhart Před 2 lety

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

  • @odayzahra6496
    @odayzahra6496 Před 2 lety +1

    Vielen Dank für das Video :)

  • @Crouchyy__
    @Crouchyy__ Před 2 lety +1

    Super Videos, vielen vielen Dank

  • @philh6316
    @philh6316 Před 5 lety +1

    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."

  • @L0Ls0ul
    @L0Ls0ul Před 4 lety +3

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

  • @Dacapoelcodaa
    @Dacapoelcodaa Před 8 měsíci +1

    viel viel besser als die Vorlessung

  • @dxamphetamin
    @dxamphetamin Před 4 lety +1

    Geiles Video. Vielen Dank

  • @Stibitzwegerich
    @Stibitzwegerich Před 2 měsíci

    Vielen Dank für das Video

  • @seydaakkaya3035
    @seydaakkaya3035 Před 5 lety +2

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

  • @maximscholtz5251
    @maximscholtz5251 Před 3 lety +1

    gut erklärt hilfreiches video

  • @cedescc7986
    @cedescc7986 Před 4 lety +1

    Meeeeega, vielen vielen vielen dank!

  • @luisa1551
    @luisa1551 Před 4 lety +3

    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
      @NLogSpace  Před 4 lety +5

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

  • @SunshineFromWithin
    @SunshineFromWithin Před rokem +1

    Super videos!

  • @Mosil0
    @Mosil0 Před 2 lety

    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?

  • @redma1248
    @redma1248 Před rokem

    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|

  • @huydang6059
    @huydang6059 Před 2 lety

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

  • @nhatlam96
    @nhatlam96 Před 2 lety

    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...

  • @TomasGiaoBarbosa
    @TomasGiaoBarbosa Před 2 lety

    "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

  • @sebastiangobel7142
    @sebastiangobel7142 Před 5 lety +2

    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
      @NLogSpace  Před 5 lety +2

      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.

  • @Themogawave
    @Themogawave Před 5 lety +2

    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
      @NLogSpace  Před 5 lety +2

      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
      @filmfranz Před 5 lety

      @@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
      @NLogSpace  Před 5 lety

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

  • @RoBert-og7jo
    @RoBert-og7jo Před 5 lety +1

    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
      @NLogSpace  Před 5 lety

      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
      @RoBert-og7jo Před 5 lety

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

  • @alrahiqalmakhtoum6249
    @alrahiqalmakhtoum6249 Před 3 lety

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

  • @njulian.7376
    @njulian.7376 Před 4 lety +1

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

    • @user-xu4fp4tw9h
      @user-xu4fp4tw9h Před 2 lety

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

  • @jakobjwdi
    @jakobjwdi Před 5 lety +6

    mal ganz nebenbei die nationalmannschaft zerstoert xD

  • @BooBar2521
    @BooBar2521 Před 3 lety +1

    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
      @NLogSpace  Před 3 lety

      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.

  • @chrisaes3235
    @chrisaes3235 Před 2 lety

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

    • @NLogSpace
      @NLogSpace  Před 2 lety +1

      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
      @chrisaes3235 Před 2 lety

      @@NLogSpace Danke schön :)

  • @SumbaSlice
    @SumbaSlice Před 3 lety

    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
      @NLogSpace  Před 3 lety

      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
      @SumbaSlice Před 3 lety

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

  • @alternativ1322
    @alternativ1322 Před 2 lety +1

    Warum P+2, ich checks nicht.

  • @Hubert_Schoelnast
    @Hubert_Schoelnast Před 4 lety

    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
      @NLogSpace  Před 4 lety

      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.

  • @thomasdieter9302
    @thomasdieter9302 Před 2 lety +1

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

    • @NLogSpace
      @NLogSpace  Před 2 lety +1

      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.

  • @sophiabnrm8730
    @sophiabnrm8730 Před 6 lety

    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
      @NLogSpace  Před 6 lety +1

      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
      @zeronothinghere9334 Před 4 lety

      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

  • @user-yf7nn9ut2b
    @user-yf7nn9ut2b Před 2 měsíci

    was ist eigentlich i?

  • @4538304544
    @4538304544 Před 2 lety

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

    • @NLogSpace
      @NLogSpace  Před 2 lety

      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|)

  • @jerome8660
    @jerome8660 Před 4 lety

    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
      @Hubert_Schoelnast Před 4 lety

      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
      @jerome8660 Před 4 lety

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

  • @Hubert_Schoelnast
    @Hubert_Schoelnast Před 4 lety

    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
      @NLogSpace  Před 4 lety +1

      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.

  • @lightblue254
    @lightblue254 Před 27 dny +2

    Grüße raus an die Deutsche Nationalmannschaft :D

  • @grippenbube3432
    @grippenbube3432 Před 2 měsíci

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

    • @user-qd4pd1ze7x
      @user-qd4pd1ze7x Před měsícem

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

  • @95Coaster
    @95Coaster Před 4 lety +1

    Shots fired at DFB :D

  • @dazzle5350
    @dazzle5350 Před 4 lety

    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
      @xGeicher Před 3 lety +1

      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.

  • @aji2847
    @aji2847 Před dnem

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

    • @NLogSpace
      @NLogSpace  Před dnem

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

    • @aji2847
      @aji2847 Před dnem

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

  • @_n_bl_3998
    @_n_bl_3998 Před 4 lety

    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
      @NLogSpace  Před 4 lety +1

      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
      @_n_bl_3998 Před 4 lety

      @@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. :)

  • @nanetteserzfeind9820
    @nanetteserzfeind9820 Před 22 dny

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

  • @umurfurkanonbasi5359
    @umurfurkanonbasi5359 Před rokem

    1:50 WM 2022 auch

  • @powermax6391
    @powermax6391 Před 2 lety

    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
      @NLogSpace  Před 2 lety +1

      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
      @powermax6391 Před 2 lety

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

  • @Lucas-so2hu
    @Lucas-so2hu Před 2 lety +2

    Erstmal die Nationalmannschaft fronten haha

  • @Amin-ve2xs
    @Amin-ve2xs Před rokem +1

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

  • @ML-wj5wp
    @ML-wj5wp Před 2 lety

    Gutes Fideo

  • @Littlefighter1911
    @Littlefighter1911 Před 2 lety

    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?

  • @tampelmarta9510
    @tampelmarta9510 Před 3 lety

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

  • @Seff2
    @Seff2 Před 5 lety

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

    • @NLogSpace
      @NLogSpace  Před 5 lety +2

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

  • @hanktobe
    @hanktobe Před 4 lety

    Damn this isnt english

    • @NLogSpace
      @NLogSpace  Před 4 lety +2

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

    • @hanktobe
      @hanktobe Před 4 lety +2

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

    • @zeronothinghere9334
      @zeronothinghere9334 Před 4 lety

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