Diskussion:Pumping-Lemma

Sätze am Ende rausgenommen

Am Ende waren Tipps, wie man v und x wählen soll, die aber sinnlos waren.

(i) Entweder sollen v und w die gleiche Buchstabensorte (sic!) enthalten oder unterschiedliche. ( hä ? Gibt es denn noch andere Möglichkeiten ?)

(ii) gleiche Buchstabensorte und eins leer ( das macht dar keinen Sinn)

Ist hier ein Bug im Formel-Support? Bei a^nb^n werden die n's als Sub- statt Superskripts dargestellt. --80.184.117.194 21:11, 11. Mai 2005 (CEST)

Wo tritt das Problem bei mir auf? Ich sehe keine Fehlformatierung in den Formeln. --Andreas ?! 21:14, 11. Mai 2005 (CEST)

Ich auch nicht... Tritt das Problem immer noch auf? Welchen Browser verwendest du? --rdb? 21:15, 11. Mai 2005 (CEST)

Beispiel Reguläre Sprachen

zitat/

Gemäß Bedingung 1 ist v nicht leer, gemäß Bedingung 2 besteht v ausschießlich aus as.

/zitat

Ist diese Beschreibung richtig? Wieso folgt aus der 2 Bedingung, dass v nur aus a bestehen muss? Boabo 14:21, 5. Jun 2005 (CEST)

Folgt deshalb, weil $|uv|\leq n$ und $a^{n}b^{n}$ mit $a^{n}$ beginnt. Also ist v ein Teil von diesem $a^{n}$. --Langec ☎ 21:39, 5. Jun 2005 (CEST)

Sollte man das vielleicht noch im Text einfügen? Ich bin auch über diesen Punkt gestolpert, der im Nachhinein ja logisch ist, aber zum Einarbeiten wäre das "idiotensicherer"... --141.53.194.251 09:38, 13. Jul 2005 (CEST)

Sollte man. Ich würde schreiben: "Gemäß Bedingung 2 besteht $uv$ ausschießlich aus $a$s und somit auch $v$ ausschließlich aus $a$s. Trotzdem verstehe ich nicht, wieso die 'beiden' $n$s dieselben sind. Was ist, wenn ein anderes Beispiel gewählt wird, z.B. $x=\{aaaa\}$, in dem kein $n$ vorkommt? FelixKaiser 22:12, 13. Jul 2005 (CEST)

1. Danke für die Ergänzung :-)
2. x=aaaa geht nicht, weil wir die Sprache $a^{n}b^{n}$ betrachten, und da ist aaaa nicht drin. Das "hoch n" bedeutet eine n-fache Wiederholung eines Zeichens, und dieses n ist natürlich im ganzen Ausdruck dasselbe. Es kann beliebig gewählt sein, hat aber einen festen Wert. MIt n=3 ist z.B. $a^{n}b^{n}=aaabbb$.

Viele Grüße, Langec ☎ 10:01, 14. Jul 2005 (CEST)

Der Beweis ist unvollständig bzw. unsauber formuliert; er lässt nämlich außer Acht dass für $|uv|$ <n das w durchaus auch a's enthält (und nicht, wie suggeriert, $w=b^{n}$). Verbesserungsvorschlag: $k:=|uv|\leq n\Rightarrow uv=a^{k}=a^{k-|v|}a^{|v|}$ und $w=a^{n-k}b^{n}\Rightarrow uv^{2}w=a^{k-|v|}a^{2|v|}a^{n-k}b^{n}=a^{n+|v|}b^{n}$. Das folgt dann zum Widerspruch nach Eigenschaft (2) (nicht signierter Beitrag von Plg94 (Diskussion | Beiträge) 00:18, 2. Feb. 2016 (CET))

Ich sehe ein, dass die Gleichung $uv^{2}w=a^{n-\left|v\right|}a^{2\cdot \left|v\right|}b^{n}=a^{n+\left|v\right|}b^{n}$ etwas verwirrend sein kann (weil sie suggeriert, dass $u=a^{n-\left|v\right|}$), aber wenn man den mittleren Teil weglässt (was ich jetzt gemacht habe), sollte es klar sein. –Jowereit (typografie.js) 00:56, 2. Feb. 2016 (CET)

Deutsches Wort Pumplemma (erledigt)

Hallo, warum wird der Artikel eigentlich nicht unter der deutschen (und durchaus üblichen) Bezeichnung Pumplemma geführt? Gruß von Wasseralm 12:07, 15. Dez 2005 (CET)

Wer verwendet denn den? --ChristianErtl 13:03, 15. Dez 2005 (CET)

Na ich zum Beispiel :-) Eine Google-Suche liefert durchaus einige Einträge. Gruß von Wasseralm 13:32, 15. Dez 2005 (CET)

Google liefert 58 Treffer auf deutschen Seiten für „Pumplemma“ und etwa 12.800 Treffer auf deutschen Seiten für „Pumping-Lemma“. Ich persönlich kenne es nur als Pumping-Lemma und würde daher dieser Bezeichnung den Vorzug geben. --Thetawave 23:26, 18. Dez 2005 (CET)

Ja, diese große Diskrepanz bei den Zahlen musste ich auch schon feststellen. Da kommt mein Einwurf wohl ungefähr 50 Jahre zu spät ... Gruß von Wasseralm 12:52, 19. Dez 2005 (CET)

Problem mit dem Pumping Lemma

Hab mir mal zum Spaß einen Automaten ausgedacht der nur ein a akzeptiert. Also $L={\mathcal {f}}a^{m}|m=1{\mathcal {g}}$ Meiner Meinung nach ist das eine reguläre Sprache und laut Definition müsste das Pumping Lemma ja mit regulären Sprachen funktionieren. Allerdings bekomme ich es nicht hin, am Ende kommt immer ein Wiederspruch raus demzufolge L nicht regulär ist. Kann mir jemand das Pumping Lemma an meinem Beispiel zeigen? Also für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle L=\mathcal{f}a^m|m=1\mathcal{g}} ?

Das funktioniert nicht, weil das Pumping Lemma nur eine notwendige Bedingung liefert, aber keine hinreichende. Mit anderen Worten: Du kannst mit dem Pumping-Lemma zeigen, dass eine Sprache nicht regulär ist, aber du kannst damit nicht beweisen, dass sie regulär ist. Die Sprache L = {a} ist natürlich regulär, wie sich mit dem Satz von Myhill-Nerode zeigen lässt. --Θ~ 20:13, 20. Jan 2006 (CET)

...beziehungsweise mit dem folgenden Automaten: i ----a-----> t Wasseralm

... aber Beweis durch Beispiel ist ja wohl ganz klar zu primitiv für uns, oder? ;-) --Θ~ 10:22, 21. Jan 2006 (CET)

Wieso ist das ein Beispiel, das ist der Beweis. Gruß Wasseralm 14:24, 22. Jan 2006 (CET)

Nicht ganz, du musst erst formal beweisen, dass der Automat die Sprache auch akzeptiert ;-) --Θ~ 21:31, 22. Jan 2006 (CET)

Nein, das ist ja das Problem das Pumping lemma beweist ja die Sprache sei nicht regulär obwohl sie es ist. Ps ich wollte mit dem pungping lemma nicht beweisen das die sprache regülär ist, ich habe nur nicht verstanden wieso eine endliche Sprache pumpbar sein soll. Mit anderen Worten wenn man eine endliche Sprache mit dem Pumping lemma verwendet, enthält v mindestens einen Buchstaben weil ja gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |v| \ge 1} gilt. Beim pumpen also bei der 3. Bedinung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v^i} für große i kann man immer ja ein Wort finden das länger ist als das längste Wort der endlichen Sprache, womit man ja dann bewiesen hätte das die Sprache nicht regulär ist, was nicht sein darf weil alle endlichen Sprachen regulär sind.

Jede endliche Sprache ist pumpbar mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \max \mathcal{f} |x| 1, x \in \mathbb{L} \mathcal{g}}

Da die Megne aller Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in \mathbb{L}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |x| \ge n } leer ist und somit trivialerweise die PL Bedinungen erfüllt sind.

Kann mir das jemand erklären? Das stimmt doch garnicht, die PL Bedinungen sind dann doch nicht erfüllt: Klar kann man n so wählen das n größer ist als die Wortlänge dann bekommt man, aber für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x \in \varnothing} und das kann man ja nicht zerlegen uvw.

Wenn man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = \varepsilon} und $|\varepsilon |=0$ macht geht es auch nicht. Damit können nicht alle Bedinungen erfüllt werden. Die 1. Bedinung $|v|\geq 1$ wäre nicht gegeben?! Die 3. $\forall i\in \mathbb {N} :uv^{i}w\in \mathbb {L}$ würde ja immer das leere Wort ergeben und das muss ja nicht zwingend in L enthalten sein.

Also gut, nochmal ganz formal:

Sei L := {a} eine endliche Sprache. Nach dem Satz von Myhill-Nerode ist L regulär. Es muss also eine natürliche Zahl n geben, für die das Pumping-Lemma erfüllt ist. Wir wählen n := 2. Sei L' := { x aus L | |x| >= n}. Offenbar gilt L' = {}. Da es keine Wörter gibt, deren Länge größer oder gleich n ist, muss also nichts weiter gezeigt werden. Das Pumping-Lemma gilt trivialerweise.

Siehe Artikel leere Menge#Eigenschaften, eine der Grundeigenschaften der leeren Menge ist:

„Da die leere Menge keine Elemente hat, sind Aussagen der Art: „für alle Elemente der Menge gilt…“ für die leere Menge stets erfüllt, da es keine Elemente gibt, für die die fragliche Eigenschaft nachgeprüft werden müsste.“

Das ist eine Eigenart der Mathematik, die mit dem umgangssprachlichen Verständnis nicht ganz vereinbar ist, ähnlich etwa wie das umgangssprachliche „oder“ dem logischen „exklusiven oder“ und nicht dem gewöhnlichen logischen „oder“ entspricht. --Θ~ 21:31, 22. Jan 2006 (CET)

Ich habe mal einen (wie ich hoffe) recht einfachen Beweis zu dem Artikel zum Thema Pumping-Lemma beigefügt. Die Kernaussage ist einfach: Wenn wir eine reguläre Sprache L haben deren Elemente durch einen Automaten mit n Zuständen erkannt werden und wir ein Wort mit mehr als n Buchstaben haben, welches auch von M erkannt wird so muss der Automat irgendwo "im Kreis laufen". Da man diesen Kreis beliebig oft durchlaufen könnte sind auch alle Worte mit beliebig vielen Wiederholungen in der Sprache. Also: Präfix Kreis Suffix. <== uvw. Bei Endlichen Sprachen wählen wir n einfach größer als das größte Wort und sind fertig ;) Gruß --Horratio 21:00, 8. Feb 2006 (CET)

Ich würde ja, um das obige Problem ein bisschen zu entschärfen, das Pumping Lemma nur für unendliche reguläre Sprachen formulieren. (Endliche Sprachen sind ja sowieso regulär und von daher uninteressant.) -- Zampel, 2008-05-27_16:42

Wikipedia formuliert keine Sätze, wikipedia berichtet über sie.

Beweise

Ich habe für die beiden Formen des Pumping-Lemma jeweils mal einen Beweis hinzugefügt. Würde mich freuen, wenn Jemand mal korrekturlesen könnte. Ich habe mir Mühe gegeben den Text so verständlich wie möglich zu formulieren glaube jedoch, daß ich gerade beim Beweis für kontextfreie Sprachen jämmerlich gescheitert bin. Werde versuchen sobald ich Zeit habe noch eine Grafik hinzuzufügen um das ganze etwas anschaulicher zu machen. Gruß --Horratio 19:09, 9. Feb 2006 (CET)

"Wir betrachten das Wort $z=a^{n}b^{n}c^{n}$". Ich denke, man kann hier n durch m ersetzen oder? Gruß -- 13 Mai 2006 (CET)

Zum ersten Beweis (den zweiten habe ich noch nicht gelesen):

Abgesehen davon dass mir persönlich eine formalere Schreibweise lieber wäre (aber das ist mein Problem), habe ich noch folgende Probleme mit dem Beweis:

1. aus der Existenz von $i,j$ mit $q_{i}=q_{j}$ folgt noch nicht, das |uv| ≤ n. Es stimmt zwar, dass es solche i,j gibt (was noch zu beweisen wäre), aber es i.A. gilt nicht für alle i,j mit der genannten Eigenschaft; Beispiel: Sprache sei a*, das betrachtete Wort aaaaaaaaa, i=4,j=5 erfüllen die Bedingung, ein passender Automat existiert aber mit einem Zustand, n=1, |uv| = 5 > 1
2. warum sollte der Zyklus auch ausgelassen werden können? Ist mir nicht einsichtig. Nebenbei behauptest Du, dass alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle uv^iw} mit i ≥ 0 Element der Sprache sind, da musst Du den Spezialfall i=0 nicht noch einmal besonders herausheben.

-- 84.63.54.217 16:42, 23. Okt. 2006 (CEST)

Aussage für reguläre Sprachen, 2. Punkt

Die Aussage 2 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left| uv \right| \le n} gehört meines Wissens nicht unmittelbar zum Pumping-Lemma. In der GTI-Vorlesung Uni Siegen wird das Pumping-Lemma durch Aussage 2 zum "starken Pumping-Lemma" erweitert. Gibt es dazu Kenntnisse von anderen?

Wäre mir neu. Im Schöning (Theoretische Informatik - kurzgefasst) gehört diese Zeile auf jeden Fall zur Definition dazu und ohne diese Eigenschaft ließe sich z.B. der Beweis für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^n b^n} gar nicht führen. Bzw. welchen Sinn hat dann das "schwache Pumping-Lemma" (ohne Aussage 2)? --Samx 18:36, 29. Jul 2006 (CEST)

Also bei uns (TU Dresden) ist auch die Aussage 2 weg gelassen worden. Der Beweis für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a^n b^n} lässt sich trotzdem führen : http://wwwtcs.inf.tu-dresden.de/GThI/script_25012005.ps (Seite 22/23)

Fehlerhaftes Bild zum Beweis?

Das Bild, das den Beweis des Pumping-Lemma illustrieren soll, erscheint mir fehlerhaft. Ich habe den Eindruck, dass die Möglichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} abzupumpen (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v^0} ) nicht berücksichtigt wird. Ich denke Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle u} ist die Zeichenfolge, die von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_1} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_t} durchlaufen wird; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} ist die Zeichenfolge, die von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_t} über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_s} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_t} durchlaufen wird; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle w} ist die Zeichenfolge, die von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_t} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_m} durchlaufen wird. Das impliziert, dass es im allgemeinen Fall auf dem Rückweg von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_t} nach Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_s} noch Zustände geben kann.

Brosenne 13:54, 12. Jul. 2007 (CEST)

Beispiel für kontextfreie Sprachen

Ich halte das Beispiel für etwas knapp formuliert und daher für recht schwer zu verstehen. Ich denke, es wäre intuitiver, wenn man statt des letzten Satzes:

"Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|vwx\right| \le n} , enthält das Wort Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle vwx} höchstens zwei verschiedene Buchstaben. Da Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|vx\right| \ge 1} , kann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle uv^2wx^2y} nicht von allen drei Buchstaben gleich viele enthalten. Also ist L nicht kontextfrei."

vielleicht folgende Beweisvariante nutzen sollte:

"Aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|vwx\right| \le n} folgt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle vx} entweder kein a oder kein c enthält. Enthält Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle vx} kein a, so folgt aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left|vx\right| \ge 1} , dass mindestens ein b oder ein c enthalten ist. Pumpt man nun mit i = 0 auf, so ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle uv^0wx^0y = uwy} und enthält aus vorheriger Bedingung n a's aber weniger b's bzw. weniger c's und ist damit nicht Element von L. Der Fall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle vx} enthält kein c ist analog. L ist also nicht kontextfrei."

Wenn kein Einspruch kommt, werde ich es in den nächsten Tagen ändern.

-- Aethian 17:49, 21. Jan. 2008 (CET)

Leider komplett unverständlich

Es wird aus dem Artikel nicht intuitiv klar, was das Pumping Lemma eigentlich ist, der Kern der Aussage versteckt sich hinter jeder Menge Formalismen. Eine kurze informelle Zusammenfassung wie in http://users.comlab.ox.ac.uk/luke.ong/teaching/moc/pump2up.pdf würde das Verständnis stark erleichtern.

--Andreas Bogk 00:58, 13. Feb. 2008 (CET)

Beweis: Punkt 2 nicht trivial

Als Mathematiker oder Informatiker sollte man sehr, sehr sparsam mit dem Wort "trivial" umgehen. Oft sind die Dinge, die man auf den ersten Blick für trivial hält, gar nicht so trivial.

So ist die Tatsache, dass |uv| ≤ n ist, nur dann mit Sicherheit erfüllt, wenn s_j der erste doppelt vorkommende Zustand auf dem Weg zum Endzustand ist. Es können danach noch viele weitere Schleifen auf dem Weg zum Endzustand kommen.

Parser Fehler

Warum wird die Zeile bei Aussage des Pumping-Lemmas für reguläre Sprachen 1. Punkt

"Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left| v \right| \ge 1} "

nicht richtig dargestellt, so sollte sie dargestellt werden wird sie aber nicht (nicht signierter Beitrag von Xrjpk (Diskussion | Beiträge) 13:14, 25. Mai 2009 (CEST))

Eine nicht-reguläre Sprache, die das Pumping-Lemma erfüllt

Ich versteh das mit den führenden a's ja noch, aber nicht mit den b'b und c's. Kann das jemand besser erklären? (nicht signierter Beitrag von 85.179.236.184 (Diskussion | Beiträge) 01:50, 19. Nov. 2009 (CET))

Jaffes Pumping-Lemma

Ich weiß zwar nicht, wie es aussehen soll, aber in der Form, wie es im Artikel steht, kann es nicht stimmen. Beispielsweise ist die Sprache Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{a^ib^b|i > 0\}} nicht regulär, aber mit k=1 sind die Bedingungen des Satzes erfüllt (es gibt halt kein w mit |w|=1, darum gilt egal was dahinter steht natürlich für alle w mit |w|=1). Ist vielleicht |w| >= k anstatt |w|=k gemeint? --93.104.83.249 12:16, 27. Jun. 2010 (CEST)

Es scheint hier richtig zitiert zu sein, siehe [1]. Das ist interessant und merkwürdig. Vor allem, da das Lemma auch in diversen Vorlesungsskripten zu finden ist.--Zahnradzacken 15:50, 27. Jun. 2010 (CEST)

Ich habe die Aussage nach https://www.cs.colorado.edu/department/publications/reports/docs/CU-CS-155-79.pdf korrigiert. --KommX 19:37, 2. Jul. 2010 (CEST)

Aussagen der Pumping-Lemmata, Beweis PL reg. Sprachen

Die math. Formulierungen der Aussagen der Pumping-Lemmata (PL) verursachen bei mir Bauchschmerzen. Wenigstens ein "daraus folgt" (=>) sollte jeweils auftauchen.

Und beim Beweis des PL für reguläre Sprachen sollte man n := |M| + 1 setzen, denn es sollen ja alle Wörter einer Länge größer/GLEICH n gepumpt werden können.

Wenn niemand meckert, ändere ich beides in den nächsten Tagen. -- UKoch 16:15, 27. Jan. 2011 (CET)

Aus "in den nächsten Tagen" wurden 10 Monate, aber besser spät als nie... Der Beweis des PL für reguläre Sprachen stimmt inzwischen. (Oder stimmt er vorher auch, und ich hatte mich versehen?!) -- UKoch 19:40, 21. Nov. 2011 (CET)

Formulierung des Pumping-Lemmas

Die formalen Formulierungen der Aussagen der Pumping-Lemmas sind in ihrer jetzigen Form fachlich nicht richtig. Es fehlt schon allein die richtige Quantifizierung.

Die Aussage des Pumping-Lemmas für reguläre Sprachen kann man formal so ausdrücken: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{align} L \in \mathcal{L}_3 &\implies \\ & \exist n \in \mathbb{N}_0.\, \forall z \in L.\, |z|\ge n \implies &&\exist u, w, v.\,\\ &&&\quad z=u\cdot v\cdot w\ \land\\ &&&\quad |v| >0\ \land \\ &&&\quad |uv| \leq n\ \land\\ &&&\quad \forall i\ge 0.\, u\cdot v^i\cdot w \in L \end{align} }

Es ist allerdings fraglich, ob eine solche formale Formulierung überhaupt zum Artikel beiträgt. Das Pumping-Lemma kann doch auch ohne solchen Formalismus präzise ausgedrückt werden. Beispiel:

Für eine reguläre Sprache L gibt es eine natürliche Zahl n so, dass sich alle Wörter z der Sprache mit Mindestlänge n zerlegen lassen als uvw, wobei das mittlere Wort v nicht leer ist und die beiden vorderen Wörter uv zusammen nicht länger als n. Diese Zerlegung hat weiterhin die Eigenschaft, dass uv^iw \in L für alle i>=0 gilt. Dies bedeutet, dass das mittlere Wort v in der Zerlegung weggelassen oder beliebig oft dupliziert werden kann, ohne dass dabei ein Wort ensteht, das nicht in L liegt. (nicht signierter Beitrag von 92.194.138.80 (Diskussion) 23:41, 30. Mai 2011 (CEST))

Ich bevorzuge persönlich die Koexistenz von Formel und Sprache, auch bei Redundanz (aber nur bei Korrektheit, deine Formel kann also gerne in den Artikel und damit vielleicht auch Benutzer:UKochs Problem lösen). Deine Formulierung finde ich nicht präzise: Wenn die Zerlegung "weiterhin" die Eigenschaft XY "hat" (und nicht "haben soll"), verstehe ich das so, als gelte das automatisch für die zuvor charakterisierte Zerlegung uvw. Auf der anderen Seite sind deine Formulierungen zum Teil präziser als die bisherige Beschreibung im Artikel. Also probier's einfach :) --Zahnradzacken 01:48, 31. Mai 2011 (CEST)

Genau. Die Eigenschaft gilt ja auch für die Zerlegung uvw ;). Da kommt wahrscheinlich die existentielle Quantifizierung von u,v und w nicht deutlich genug heraus. (nicht signierter Beitrag von 92.194.224.47 (Diskussion) 08:26, 31. Mai 2011 (CEST))

Die Existenzquantor lässt sich schon erkennen, aber nicht sein Wirkungsbereich über zwei Sätze hinweg. Du schließt einen Satz mit einem Punkt ab und was folgt, könnte auch als "daraus folgt" gelesen werden. --Zahnradzacken 11:31, 31. Mai 2011 (CEST)

Bild mit Ableitungsbaum für kontextfreies PPL fehlerhaft

Ist das Bild mit dem Ableitungsbaum nicht fehlerhaft? Erstens steht dort sowas: w = uvwxy, was keinen Sinn ergibt. Und zweitens steht da: Gegeben sei ein Wort x - das Wort sollte doch wohl w in der obigen Notation sein?

--Ccoenig (Diskussion) 20:48, 9. Feb. 2013 (CET)

Einleitung: "in vielen Fällen

lässt sich mit dem PL nachweisen ..." ist meiner Meinung nach unglücklich formuliert. Wenn eine Sprache nicht T2/T3 ist, laesst sich doch immer mit dem PL feststellen, dass das so ist. Oder liege ich da falsch?

Ich wäre für eine Formulierung wie "das PL kann in seiner jeweiligen Fassung verwendet werden, um zu zeigen, dass eine bestimmte Sprache nicht zu einer Sprachklasse gehört." --88.68.121.127 15:11, 6. Apr. 2013 (CEST)

Beweis: kleiner statt ungleich

In dem Beweis steht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \ne j \in \{1, \dots, n+1\}} Erreichen wir den Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i = q_j} , also Beginn und Ende des Zyklus, ist es egal ob i ≠ j ist oder nicht, da die Zustände äquivalent, also in der Minimierung der gleiche sind. Wenn wir allerdings die Sequenz Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i \to \dots \to q_j} betrachten, haben wir da ein kleines Problem mit der Definitionsmenge. Denn wenn wir zuerst Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_j} erreichen (j < i), dann können wir die Sequenz schwerlich bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle q_i} starten. Deswegen sollte dort stehen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i < j \in \{1, \dots, n+1\}} .

Bitte helfen Sie mir ich muss diese Aufgabe lösen!

Sei L die folgende kontextfreie Sprache über dem Alphabet ∑ = {a, b, c}:

- L = {aⁿbbcⁿ | n ∈ N}

Beantworten Sie die folgende Frage und begründen Sie Ihre Antwort.

(i) Ist die Zahl 2 eine Pumping-Lemma-Zahl der Sprache L? (ii) Ist die Zahl 3 eine Pumping-Lemma-Zahl der Sprache L? (iii) Ist die Zahl 4 eine Pumping-Lemma-Zahl der Sprache L?