Verständnisproblem zum Pumping-Lemma

[BlackCobra]

Hallo,

Ich habe wie der Titel schon sagt ein Problem mit dem Pumping-Lemma, für alle die es nicht kennen hier mal die Definition;


für jede reguläre Sprache L gibt es eine natürliche Zahl n, sodass gilt: Jedes Wort z in L mit Mindestlänge n hat eine Zerlegung z = uvw mit den folgenden drei Eigenschaften:



Die beiden Wörter u und v haben zusammen höchstens die Länge n.
Das Wort v ist nicht leer.
Für jede natürliche Zahl (mit 0) i ist das Wort u(v^i)n in der Sprache L, d. h. die Wörter uw, uvw, uvvw, uvvvw, usw. sind alle in der Sprache L.



Ich nehme jetzt mal die Reguläre Sprache L(r) die von dem regulären Audruck r = aabba über dem Alphabet Σ = {a,b} beschrieben wird als Beispiel.

Für diese Reguläre Sprache (Sie kann durch einen regulären Ausdruck dargestellt werden) gibt es jedoch kein Wort z in L mit Mindestlänge n sodass ich es in drei Teile zerlegen könnte, und den Mittelteil wiederholen/weglassen könnte sodass das entstehende Wort immer noch in L liegt, da L nur aus einem einzigen Wort besteht.

Was habe ich am Pumping-Lemma falsch verstanden?

grüße BlackCobra (diesen Namen sollte ich unbedingt mal ändern)

[blackberry]

Du meinst die Sprache, die nur das Wort aabba enthält? Die genügt der Aussage des Pumping-Lemmas; wähle etwa n=6 in deiner Formulierung von oben.

Der Punkt ist, dass All-Quantifizierungen über die leere Menge immer wahr sind. Beispielsweise die Aussage "Alle blauen Giraffen sind grün" ist wahr (vorausgesetzt, dass es keine blauen Giraffen gibt) -- denn die Negation dieser Aussage ("Es gibt eine blaue Giraffe, die nicht grün ist") ist ersichtlich falsch.

[BlackCobra]

Danke für die Antwort, man sollte sich solche Lemmas doch etwas genauer durchlesen als ich es getan habe, ich hatte die Stelle "Jedes Wort z in L mit Mindestlänge n" komplett übersehen