Pumping Lemma - Beweisschema
Вставка
- Опубліковано 12 лип 2018
- Wir sehen uns an, wie man aus der Aussage des Pumping Lemmas ein Beweis-Schema bekommt, mit dem man die Nicht-Erkennbarkeit von Sprachen nachweisen kann. Dieses Schema kann auch als ein Spiel zwischen zwei Spielern aufgefasst werden. Wir wenden dieses Schema dann auch für die Sprache {a^nb^n} an.
![[1 von 3] Aus der Sicht eines Studenten | Laufzeitanalyse](http://i.ytimg.com/vi/jPaYI00kIIQ/mqdefault.jpg)
![Pumping Lemma für erkennbare Sprachen [IMPROVED]](/img/n.gif)
Perfekt :D Morgen Klausur in Theoretischer Informatik.
Ich auch und das hilft mir gerade ungemein ^^
Auch Uni Augsburg?
Jup ^^
Liebe Grüße aus Duisburg, same here.
@@smiletolerantly und hast du die AFS bestanden ?
Wie geil du aus Theoretischer Informatik ein spannendes Spiel machst 🤣
In Übung nie gecheckt, ein Video von dir -> direkt gecheckt xD
Kannst du nicht einfach unsere Vorlesungen machen? 😂
Super verständlich, danke.
Viele Grüße aus Karlsruhe(KIT). Das Video hat mir mega geholfen. Danke!
Tolle Erklärungen, sehr hilfreich und verständlich. Bitte weiter so und vielen Dank!
Vielen Dank, das hat mir sehr geholfen :)
Danke, sehr gute Erklärung!
sehr gut erklärt. danke dir
einfach heftig man!!! richtig gut
Grüße von der TU Darmstadt ✌️
Das wirdn spaß morgen
Hochschule Heilbronn Campus Sontheim grüßt auch (Studiengang SEB). Danke dass du diese tollen Videos machst.
Super gut erklärt! :)
Geil, ich liebe diesen Spielvergleich :D
Danke :)
Wenn ich die Klausur dank dir bestehe gebe ich dir einen Döner aus! Ehrenmann :D
Na dann viel Erfolg! :)
Und hast du die Klausur jetzt bestanden? wo bleibt der Döner?
@@songokkel7667 Nein hab es leider verkackt mit 4 punkten drunter... Schreibe die Klausur im September nach aber diesmal wird es klappen und verstehe diesmal alles schon deutlich besser. Sagen wir mal so: Konnte damals nichtmal Logik und Mathe Kenntnisse fehlten auch so einige, daher normal dass ich es verhauen habe.
Aber jetzt Schuldest du mir einen Döner weil ich verkackt habe xD
@@Noone62575 Und hast du die Klausur jetzt bestanden? wo bleibt der Döner?
@@Noone62575 und haste die Klausur bestanden ? :)
die idee das mit nem gegenspieler zu erklären is richtig gut!
sag mal wenn du i = 0 setzt, dann hast du ein wort der form x*(y^0)*z. y^0 = epsilon , ich dachte genau das darf y nicht sein?
y und y^0 sind zwei verschiedene Sachen. y darf nicht epsilon sein, aber y^0 darf epsilon sein (und y^0 ist immer gleich epsilon).
Ehrenmann
bei 8:19 wird das w a^p b^p in xyz eingeteilt. woher weiß er das x und y nur a beinhalten und z nur b? ist das so das da da |xy|
Super video! Ich hab nur eine (eventuell blöde) Frage: warum kann meine Zerlegung nicht so gewählt werden, dass ich mitten in den as anfange und mitten in den bs aufhöre und mein y so aus as und bs besteht. Oder ist das generell nicht der Fall, weil y sozusagen nur aus einem der Buchstaben bestehen darf?
Nevermind, mit einer Skizze wird es schnell klar. Ich hab da eher an die Zerlegungen bei den kontextfreien gedacht und das durcheinander gebracht. Dachte eben, dass ich ja vor dem x noch Buchstaben haben kann, aber mein ganzes Wort ist ja w=xyz
Hey ich hab mit Hilfe von deinem Video ein paar Aufgaben im Internet gelöst....in den Lösungen dieser Aufgaben gab es ziemlich oft auch eine Fallunterscheidung und meine Frage an dich ist, muss ich beim Pumping Lemma für reguläre Sprachen eine Fallunterscheidung machen ? Ich weiß dass dies der Fall ist bei dem Pumping Lemma für kontextfreie Sprachen.Vielen Dank schon mal im voraus :)
Ist zwar etwas spät aber egal: es gibt auch Fallunterscheidungen beim PL für reguläre Sprachen. Das kommt aber auf die Sprache und das gewählte Wort an.
haben Sie itte ein Link zu Aufgabe online?
Ist eine erkennbare Sprache das gleiche wie eine reguläre Sprache ?
Edit: Ist die Idee mit dem Spiel irgendwie gängig? Wir haben das auch so gelernt in der Vorlesung ^^
Achja und richtig gutes Video
Ja, ich verwende hier den Begriff "erkennbar" als Synonym für "regulär".
Ja, das mit dem Spiel ist eine beliebte Art die Bedeutung von Formeln zu erklären, in denen viele geschachtelte Quantoren ("für alle" und "es existiert") vorkommen.
@@NLogSpace Cool danke. Ist sehr gut verständlich mit dem Spiel 👍
Du rettest mir den Arsch mit deine Videos!! Vielen Dank *_*
Warum hat man dann zwangsweise weniger as als bs? wenn y genau in der mitte ist so dass es wieder passt?
Wegen der Bedingung |xy|
i hoch 1 wäre dann aber in der Sprache oder? weil es ja die ursprüngliche Zusammensetzung von a^n b^n nicht verändert
Richtig. Daher macht es bei einem Pumping-Lemma-Beweis niemals Sinn, die 1 zu wählen, oft funktioniert aber schon 0 oder 2.
hast du mal überlegt Vorlesungen zu halten? Habe es hier besser verstanden als in der Vorlesung! TOP!
Kann man auch mit der Variable p pumpen? Also xy^pz ? Ist bei dieser Sprache natürlich nicht nötig, aber bei anderen Sprachen wäre das glaube ich hilfreich.
Ja, jede natürliche Zahl ist erlaubt. Ziel ist aber immer, dass das gepumpte Wort nicht in der Sprache liegt.
@@NLogSpace danke für die super schnelle Antwort!
Eigentlich weiß ich gar nicht, warum ich das Video gucke, denn das PL habe ich verstanden, aber ich wollte mal anmerken, dass ich es etwas irritierend finde, dass von "erkennbar" statt regulär gesprochen wird, vllt bin ich aber auch zu sehr im Turingmaschinenpart drin :D
Ja, die Benennung ist ein bisschen gewöhnungsbedürftig. Aber es ist durchaus so üblich: "erkennbar" steht für DEA-erkennbar und ist das äquivalent zu "regulär". Im Gegensatz zu "Turing-erkennbar", was bedeutet, dass es eine Turingmaschine gibt, die die Sprache akzeptiert.
Frage: 10:55 wenn bei der Zerlegung von w = xyz, y nicht epsilon sein darf (das leere Wort), wie kann man dann i = 0, setzen. Was ergibt y^0 = 0 oder y^0 = epsilon, was ja eingentlich nicht sein darf und ein Widerspruch wäre?
y und y^0 sind nicht das gleiche. y darf nicht leer sein, y^0 hingegen ist immer das leere Wort.
Ja, wenn y nicht leer sein darf |y| > 0 allerdings i = 0 mit y^i sein darf, womit y^0 möglich ist, dann ist dies doch ein Widerspruch.
da y^0 = epsilon ist (leeres Wort) damit ist y doch leer? |espilon| = 0 bzw. leer
@@NLogSpace
@@NLogSpace D. h. wenn y^0 = epsilon ist, dann wäre doch |y| = 0 ???
Widerspruch zur Bedingung |y| >= 1 sein?
Frage: Woher weiß man, dass bei 9:10 wenn man y aufpumpt mit i = 2 zum Beispiel, dass dann |xy| > |z| gilt? Man weiß ja nicht davor, wie genau die Zerlegung von xy ist. Also in dem Beweisfall von i = 0, ergibt es natürlich Sinn, jedoch bei allen anderen (wie im Video behauptet) verstehe ich es nicht.
Ich glaube hier geht einiges durcheinander. Die Aussage "Wenn man y aufpumpt mit i = 2, dann ist |xy| > |z|." ergibt keinen Sinn, denn die Längen von x, y und z hängen nicht von i ab. Meinst Du vielleicht die Aussage "Wenn man y aufpumpt mit i = 2, dann ist |xy^i| > |z|."? Auch dieses Aussage gilt nicht unbedingt, das Argument ist ein anderes. Die Aussage |xy| > |z| gilt im Allgemeinen nicht, und das wird auch im Video nirgends behauptet. Wir haben das Wort a^p b^p gewählt. Dann bekommen wir eine Zerlegung xyz dieses Wortes mit der Bedingung |xy|
Ah stimmt, du hast recht! Danke für die schnelle Antwort!@@NLogSpace
Was issn wenn y=ab oder y = aabb oder so is. Dann wenn y^0 ist hat man immer noch gleich viele a's und b's. Muss man das dann separat beweisen?
Diesen Fall müssen wir nicht betrachten, da wir die Bedingung |xy| ≤ p ausnutzen und wir das Wort a^p b^p gewählt haben, denn dann besteht y nur aus as. 7:30
ne ne, Freundchen 😁😂
10:08 wenn i = 2, 3 ,4 ,5... ist dann hat x y^i z mehr a als b. so das geht?
ja
Mich irritiert 8:47 .
"wir können i = 0 setzen..."
aber es gilt doch auch *|y| ≥ 1* ...?
wenn *|y| ≥ 1* gilt, dann darf man doch nicht i = 0 setzen, weil dadurch y komplett wegfällt und nicht mehr |y| ≥ 1 sein kann.
Was versteh ich hier falsch?
Dein Denkfehler ist, dass y^i nicht das gleiche ist wie y. Das Wort y ist nicht leer. Aber deswegen können wir trotzdem i=0 setzen, sodass y^i das leere Wort ist.
"Aber deswegen können wir trotzdem i=0 setzen, sodass y^i das leere Wort ist."
Und genau das verstehe ich als Verstoß gegen die eine der drei Regeln des Pumping Lemma, nämlich jene die besagt dass
|y| ≥ 1.
Ich weiß dass "|y|" die "Länge von y" heißt, aber wenn y^i durch i = 0 auf y^0 = 1 .... 🧐 achso... durch die 0 im Exponenten verschwindet das y ja nicht komplett, sondern reduziert sich damit auf die Länge 1?
Nein, das y ist die ganze Zeit ein nicht-leeres Wort. Es geht am Ende aber nicht um y, sondern um y^i. Dieses y^i ist ein anderes Wort. Es entsteht, indem man das y einfach i mal hintereinander hinschreibt. Wenn man i=0 wählt, dann schreibt man das y eben 0 mal hin. (Das ist auch kein Wort der Länge 1, sondern das leere Wort, Länge 0). Aber es widerspricht nicht der Bedingung |y| > 0, denn y ist ja weiterhin nicht leer. y darf nicht leer sein, y^i hingegen schon, das hat uns niemand verboten.
Ah... okay ich verstehe. Ich war noch nicht ganz auf Deinem Abstraktionslevel angekommen. Habe wieder zu kompliziert gedacht. Danke für Deine Hinweise. Die sind ungemein hilfreich! 👍🏻
@@NLogSpace same problem. ich komme immer noch nicht durch @@.
was für ein nicht-leeres Wort hat ein exponent 0 und dessen länge >=1 ist?
wenn man 0 mal y hinschreibt, d.h gibt es kein y mehr oder?
nachdem ich weitere Videos geschaut hatte, hatte ich ne Bemerkung dass y bestimmt immer kein leeres Wort ist, aber y^i ein leeres Wort ist. Daher widersprucht es bedingung |y| >=1. ---> L ist nicht regulär/nicht erkennbar... Ist das noch denkfehler ?
Was ich nicht so ganz verstehe ist: Wenn ich die Aussage "Wenn L erkennbar, dann gilt..:" negieren möchte, wieso muss ich denn alle Quantoren negieren? Reicht es nicht, den obersten Quantor zu negieren? Dann habe ich doch schon das Gegenteil. Stehe da auf dem Schlauch.
Ah, ich habe meinen Fehler gefunden. Ich habe die Negation falsch in Erinnerung gehabt. Dadurch, dass die Negation des Allquantors bedeutet, dass es ein Element gibt, für das die Folgeaussage nicht gilt, zieht das Ganze selbstverständlich durch die ganze Kette. Ups. :D
Aber wenn i=0 dann ist y doch das leere Wort und das darf ja nicht sein?
Nein, so darfst du das nicht verstehen. Die intuitive Idee hinter dem Pumping Lemma ist ja, dass man bei einem Wort, welches mindestens so lang ist, wie der Automat Zustände hat, in mindestens einen Zustand doppelt gehen muss, dass es also einen Loop irgendeiner Form gibt. Das Wählen von i = 0 musst du dann so verstehen, dass du diesen Loop genau 0 Mal gehst. Wir nennen das auch "abpumpen", weil, wie du richtig erkannt hast, das Wort dadurch kürzer wird und deswegen nicht mehr in der Sprache sein könnte. Wenn y = Epsilon gilt, bedeutet dann intuitiv, dass es nichts bringt, einen Epsilon-Übergang in einer Schleife mehrmals zu durchlaufen, deswegen schließen wir diesen Fall der Zerlegung aus.
Warum muss ein a in Z liegen?
Ist nicht i hoch 0 = 1 , dann hätte man doch wieder gleich viele a und bs. Ist das selbe wie i = 1 und i = 0 aufpumpen
Die Schreibweise y^i ist wiederholte Konkatenation und hat nichts mit Potenzieren zu tun! Das y^i bedeutet, dass wir das Wort y insgesamt i mal hintereinander schreiben. Und 0 mal hintereinander ist das leere Wort.
wir haben aber vorher angenommen ,dass das y nicht glich das leere Wort sein darf oder nicht?
@@NLogSpace
@@abdulssatarkhateb2482 Ja, haben wir!
Bin durchgefallen danke für nichts
Was kann der Bre dafür, das du durchgefallen bist?!