Pumping-Zahl?

Hallo, evtl. kennt sich jemand mit der Pumping-Zahl aus.

Diese ist nämlich jene minimale Zahl p, sodass gilt:

Jedes Wort w aus der Sprache L mit einer Länge von mind. p (also |w| = p) kann in w = xyz aufgespalten werden, derart, dass

1. |xy| <= p
2. y =/= e (leeres Wort)
3. x(y^i)z ist in L

------------------------

Ich hätte mich jetzt gefragt, was die Pumping-Zahl von 0001*, 1011 und ((011) u (1*0*) ist.

-----------------------

Beim Ersten hätte ich p = 4 vermutet. Begründung: x = 000, y = 1, z = e

Dann |xy| <= p, y =/= e, und xy^iz ist in L (weil 000111...11 in L) für jedes i aus IN.

----------------------

Beim Zweiten bin ich mir nicht sicher, ob es da überhaupt eine Pumping-Zahl gibt, weil ich 1011 eigentlich nicht aufpumpen kann. Vielleicht weiß da jemand mehr.

----------------------

Beim Dritten hätte ich eine Pumping-Zahl von 1 vermutet. Begründung: Setze x = e, y = 1 und z = e

Dann |xy| <= p, y =/= e und xy^iz ist in L (weil 111...11 in L) für jedes i aus IN.

---------------------

Stimmen meine Vermutungen? Was mache ich mit dem endlichen Ausdruck 1011?

Answer 1

[Willibergi]

Das Pumping-Lemma bezieht sich ja auf ganze Sprachen, nicht auf einzelne Wörter: Für jede reguläre Sprache gibt es eine einzig Pumping-Zahl, die für alle Wörter der Sprache die Pumping-Eigenschaft erfüllt. Das heißt, die Pumping-Zahl hängt zwar von der Sprache ab, aber nicht vom Wort der Sprache selbst.

Tatsächlich muss man auch nur irgendeine Zahl finden, die das Pumping-Lemma erfüllt, denn das impliziert wegen der Beschränktheit von IN direkt die Existenz eines Minimums.

Deine Beweise sind in Ordnung, bis auf den dritten. Wörter der Form 0*1* der Mindestlänge 1 müssen nicht zwangsläufig eine 1 enthalten.

Für endliche Sprachen ist das Pumping-Lemma trivial, da die Pumping-Zahl einfach größer als die Maximallänge gewählt werden kann. Für

$L = \{ 1011 \}$

tut es also p = 5, damit ist die Implikation trivial (und tatsächlich ist das auch die Pumping-Zahl, denn das Pumpen erzeugt ja unendlich viele verschiedene Wörter).

Bei

$L = \{ 011 \} \cup L(1^* 0^*)$

tut es auch p = 4, dann kann man sich auf den hinteren Teil der Vereinigung beschränken und braucht sich über das einzeln hinzugefügte Wort keine Gedanken zu machen. Auch hier muss man das y nur mit Länge 1 wählen (also entweder y = 0 oder y = 1, je nachdem wie das Wort in L(0*1*) aussieht) und kann pumpen wie man lustig ist. (Die Pumping-Zahl wäre hier tatsächlich 1, aber für die Pumping-Eigenschaft genügt wie gesagt irgendeine Zahl, die sie erfüllt.)

Comments

[Quotenbanane]

Erstmal danke!

Verstehe ich bei L = {1011} richtig, dass man p = 5 wählt, weil man dann per Definition jedes Wort w mit |w| >= 5 aufpumpen kann, was trivial wahr ist, weil es in L kein Wort mit einer Länge größer-gleich 5 existiert?

[Willibergi]

@Quotenbanane

Genau so ist es. Die Prämisse ist falsch, damit die Implikation trivialerweise wahr. Man hat auch wie gesagt keine Wahl, denn das durch das Pumpen kann man unendlich viele verschiedene Wörter erzeugen und damit sicher eines, das nicht in der endlichen Sprache liegt. Damit muss die Pumping-Zahl in diesem Fall größer als die Länge des längsten Wortes sein.