Danke für Deine hilfreichen Videos, ich lerne gerade für meine Theo. Inf. Prüfung und habe keine Vorlesungen oder Präsenzveranstaltungen, da es sich um ein Fernstudium handelt. Da sind zusätzlich zu den Skripten Videos bei denen die für mich recht schwere Thematik so toll erklärt wird wirklich hilfreich!
Im Vergleich zu Deinen neueren Videos finde ich dieses hier (und das vorherige zum PL für kontextfreie Sprachen) deutlich wirrer. Vielleicht wäre das Pumping Lemma für kontextfreie Sprachen ein Kandidat für ein aktualisiertes Video.
Vielen Dank für das Feedback! Ja, ich plane bereits den Großteil der Serie zu formalen Sprachen (Videos 1-29) neu zu strukturieren und neu aufzunehmen.
Sehr gut erklärt, vielen Dank!! ich hatte zuvor nicht wirklich die Pfadlänge ect verstanden, aber Deine Videos sind eine enorme Hilfe (für die baldige FSK-Klausur) :DD
Tausend Dank nochmal - die Klausur ist inzwischen bestanden!! :DD Eine besondere Hilfe waren dabei Deine Videos über die Anwendung des Pumping Lemmas für kontextfreie Sprachen und den CYK-Algorithmus, ohne die ich das bestimmt nicht geschafft hätte! :D
Ich habe noch nicht ganz verstanden was p jetzt genau darstellen soll bzw. wenn ich einen Beweis machen soll, woher ich weiß wie groß p ist. Könntest du das nochmal sagen bitte, wie man auf p kommt bzw woher man weiß wie groß p ist? Danke. Also ich verstehe nicht, was du meinst mit dem 3 * 3 bzw. wie man darauf kommt.
@NLogSpace 11:34 Kann man für den ersten Fall und i = 2 sagen, dass die Länge des Wortes nach dem "Aufpumpen" wie folgt ausschaut: a^(p+2) b^p c^p oder a^(p+1)b^(p+1)c^p oder a^pb^(p+2)c^p. Danke
Hi, warum muss man die drei Fälle vxy enthält nur a's | b's | c's nicht betrachten? ... habs nun glaube ich verstanden. deine fallunterscheidung schließt diese fälle mit ein, denn fall 1 enthält bereits die aussage (vxy enthält nur a's | b's | a's & b's) und fall 2 enthält die aussage (vxy enthält nur b's | c's | b's & c's)
verdammt, leider schon was spät mit der frage und morgen prüfung, aber vielleicht würde das ja noch anderen helfen: aber bei a^pb^pc^p ist doch schon beispielsweise c^p alleine von der länge p. wenn ich jetzt |vxy| p bzw. zwischen p+1 und 2p um genau zu sein?
Der Fall "vxy hat kein a" behandelt alle Fälle, in denen vxy kein a hat. Das heißt aber nicht, dass vxy =b^p c^p ist (das hat ja wie Du richtig gesagt hast Länge größer als p). Stattdessen ist vxy einfach irgendein Teilwort von b^p c^p mit Länge höchstens p. Hoffe, das war noch rechtzeitig. Viel Erfolg bei der Prüfung!
In der Definition aus meiner Vorlesung steht, |w| ≥ 2^p und nicht |w| ≥ p. Des Weiteren steht bei mir |vy| ≥ 1 und nicht v ≠ λ oder y ≠ λ. Und bei mir steht auch |vxy| ≤ 2^p und nicht wie bei dir |vxy| ≤ p. Hat das irgendwas zu bedeuten? Mich verwirrt in meiner Definition dieses 2^p.
Ich habe mir jetzt die videos mehrmals angeschaut. Mir fehlt ein Pullzestück: Was bedeutet/woraus besteht denn nun die variable p genau? ich checks einfach nicht.
Das erkläre ich in den ersten paar Minuten dieses Videos. Wir brauchen im Beweis des Pumping Lemmas die Tatsache, dass jeder Ableitungsbaum für unser Wort sehr tief ist (tiefer als wir Nichtterminale in der Grammatik haben). Wenn wir Wörter der Länge mindestens p betrachen, dann ist das der Fall, d.h. das p ist genau so gewählt, dass Wörter der Länge mindestens p in ihrem Ableitungsbaum einen solchen langen Pfad haben.
@@andre9897 Nein, wie gesagt, die Berechnung erkläre ich in den ersten paar Minuten dieses Videos. Es ist sowas wie (längste rechte Regelseite)^(Anzahl Nichtterminale) + 1
Die Variablen u, v, x, etc. können also aus Teilworten bestehen und müssen nicht unbedingt aus nur einem Buchtaben oder einer Folge von einem Buchstaben bestehen, richtig?
![Pumping Lemma für erkennbare Sprachen [IMPROVED]](/img/n.gif)
Danke für Deine hilfreichen Videos, ich lerne gerade für meine Theo. Inf. Prüfung und habe keine Vorlesungen oder Präsenzveranstaltungen, da es sich um ein Fernstudium handelt. Da sind zusätzlich zu den Skripten Videos bei denen die für mich recht schwere Thematik so toll erklärt wird wirklich hilfreich!
Kann ich nur bestätigen! Geht mir (an der FernUni Hagen) genauso! Hilfreiche Videos!!
Im Vergleich zu Deinen neueren Videos finde ich dieses hier (und das vorherige zum PL für kontextfreie Sprachen) deutlich wirrer. Vielleicht wäre das Pumping Lemma für kontextfreie Sprachen ein Kandidat für ein aktualisiertes Video.
Vielen Dank für das Feedback! Ja, ich plane bereits den Großteil der Serie zu formalen Sprachen (Videos 1-29) neu zu strukturieren und neu aufzunehmen.
Sehr gut erklärt, vielen Dank!! ich hatte zuvor nicht wirklich die Pfadlänge ect verstanden, aber Deine Videos sind eine enorme Hilfe (für die baldige FSK-Klausur) :DD
Danke!
Tausend Dank nochmal - die Klausur ist inzwischen bestanden!! :DD
Eine besondere Hilfe waren dabei Deine Videos über die Anwendung des Pumping Lemmas für kontextfreie Sprachen und den CYK-Algorithmus, ohne die ich das bestimmt nicht geschafft hätte! :D
Sehr hilfreich. Vielen Dank!
Ich habe noch nicht ganz verstanden was p jetzt genau darstellen soll bzw. wenn ich einen Beweis machen soll, woher ich weiß wie groß p ist. Könntest du das nochmal sagen bitte, wie man auf p kommt bzw woher man weiß wie groß p ist? Danke. Also ich verstehe nicht, was du meinst mit dem 3 * 3 bzw. wie man darauf kommt.
Die gleichen Fragen beschäftigen mich jetzt. Verstehst du jetzt, wofür p verwendet wird?
Super Videos, helfen sehr beim Lernen. Vielen Dank :)
Ich glaube jetz hab ichs endlich verstanden....vielen dank!
@NLogSpace 11:34 Kann man für den ersten Fall und i = 2 sagen, dass die Länge des Wortes nach dem "Aufpumpen" wie folgt ausschaut: a^(p+2) b^p c^p oder a^(p+1)b^(p+1)c^p oder a^pb^(p+2)c^p. Danke
Hi,
warum muss man die drei Fälle
vxy enthält nur a's | b's | c's
nicht betrachten?
... habs nun glaube ich verstanden. deine fallunterscheidung schließt diese fälle mit ein, denn fall 1 enthält bereits die aussage (vxy enthält nur a's | b's | a's & b's) und fall 2 enthält die aussage (vxy enthält nur b's | c's | b's & c's)
14:47 Gibts da nicht noch einen Fall drei, dass vxy genau nur die b's enthält. Das könnte man aus der Vereinigung Fall1 und Fall2 auch schließen.
Wenn vxy nur die b's enthält, dann enthält es kein c, was der erste Fall ist.
Das Wort uvxyz hat doch Raum für alle Buchstaben (eine wird selbsverständlich stark steigen) warum kann u = a und z = c sein?
verdammt, leider schon was spät mit der frage und morgen prüfung, aber vielleicht würde das ja noch anderen helfen: aber bei a^pb^pc^p ist doch schon beispielsweise c^p alleine von der länge p. wenn ich jetzt |vxy| p bzw. zwischen p+1 und 2p um genau zu sein?
Der Fall "vxy hat kein a" behandelt alle Fälle, in denen vxy kein a hat. Das heißt aber nicht, dass vxy =b^p c^p ist (das hat ja wie Du richtig gesagt hast Länge größer als p). Stattdessen ist vxy einfach irgendein Teilwort von b^p c^p mit Länge höchstens p.
Hoffe, das war noch rechtzeitig. Viel Erfolg bei der Prüfung!
@@NLogSpace war zwar nicht rechtzeitig aber kam glücklicherweise nicht dran. aber okay, verstehe jetzt wie's gemeint war, danke :D
Da hat es bei mir auch gerade gehakt und ich suchte in den Kommis nach Hilfe. Das half, super :D
In der Definition aus meiner Vorlesung steht, |w| ≥ 2^p und nicht |w| ≥ p. Des Weiteren steht bei mir |vy| ≥ 1 und nicht v ≠ λ oder y ≠ λ. Und bei mir steht auch |vxy| ≤ 2^p und nicht wie bei dir |vxy| ≤ p. Hat das irgendwas zu bedeuten? Mich verwirrt in meiner Definition dieses 2^p.
Aber wenn 'vxy' sowohl 'a's als auch 'c's hat, was ist dann? Wieso muss dieser Fall nicht berücksichtigt werden?
Vxy darf ja nicht länger als p sein
Ich habe mir jetzt die videos mehrmals angeschaut. Mir fehlt ein Pullzestück: Was bedeutet/woraus besteht denn nun die variable p genau? ich checks einfach nicht.
Das erkläre ich in den ersten paar Minuten dieses Videos. Wir brauchen im Beweis des Pumping Lemmas die Tatsache, dass jeder Ableitungsbaum für unser Wort sehr tief ist (tiefer als wir Nichtterminale in der Grammatik haben). Wenn wir Wörter der Länge mindestens p betrachen, dann ist das der Fall, d.h. das p ist genau so gewählt, dass Wörter der Länge mindestens p in ihrem Ableitungsbaum einen solchen langen Pfad haben.
@@NLogSpace danke für die schnelle Antwort :)
D.h. p ist keine genau definierte Zahl, man kann p auch als (mindestens) Nichtterminale+1 definieren?
@@andre9897 Nein, wie gesagt, die Berechnung erkläre ich in den ersten paar Minuten dieses Videos. Es ist sowas wie (längste rechte Regelseite)^(Anzahl Nichtterminale) + 1
Die Variablen u, v, x, etc. können also aus Teilworten bestehen und müssen nicht unbedingt aus nur einem Buchtaben oder einer Folge von einem Buchstaben bestehen, richtig?
Richtig!
Danke! :)
Was ist denn mit den Fällen in denen vwx nur in a oder b, c liegt ?
Diese Fälle sind schon abgedeckt, z.B. wenn es komplett im a-Block liegt, dann hat es kein c, also Fall 1.
@@NLogSpace verstehe, vielen dank für die schnelle Antwort!
Stark!