Pumping Lemma?
Die Sprache ist nicht regulär, dies kann man über das Pumping Lema zeigen.
Soweit konnte ich dies nachvollziehen, allerdings:
Generell setzt man ja n = k.
wenn i = 0 ist gilt uw = a^(k - |v|)b^k
Warum ist dies jetzt nicht Teil meiner Sprache? Wenn ich nichts Pumpe und n = k z. B. n = 1 dann steht doch hier ab, was Teil meiner Sprache ist?
Wie kommt man auf den generellen Ansatz uw = a^(k - |v|) b^k ???
1 Antwort
Also, die Sprache ist ja a^k b^k. Wählt man n=k, so gilt wegen |uv| <= n, dass uv ein Teilwort von a^k ist, und somit auch v. Zudem ist v nicht das leere Wort.
Wählt man i=0, so gilt u v^i w = uw, das v fällt also weg. Daher gilt uw=a^(k-|v|) b^k.
Und da |v| > 0, entspricht das Wort nicht mehr der Form a^k b^k, ist also nicht mehr in L
Des ist echt verwirrend, wenn man des, dass das erstem mal sieht:
uw=a^(k-|v|) b^k. für i = 0 gilt dies. Macht Sinn da sonst |v| = 0 wäre und somit die 1 Bedingung verletzt wäre.
Die a^(k - |v|) sind die a(s) die in u drinnen stecken von x = uw
Damit Bedingung 1 erfüllt ist muss |v| >= 1 sein, d. h. z. B. aaabbb
Ich wähle aa als u a als v und bbb als w
somit gilt: a^(k - |v|) für uv^(i)w (1) und (2) Bedingung sind erfüllt. Fange ich nun das pumpen an
i = 0 darf ja nicht sein. Also
i = 1 aaabbb passt aa als u a ls v bbb als w
i = 2 aaaabbb Bedingung (3) verletzt. aa als u aa als v bbb als w
i = 3 ...
Ja, muss man halt wissen, dass a^(k - |v|) auf die Anzahl der äußeren a bzw. u bezieht.
Bsp. k = 4 aaaabbbb aaa = u a = v^i bbbb = w
Fängt man das Pumpen an, ist nur bei i = 1 das Wort noch teil meiner Sprache, dann nicht mehr.
Das gesamte ursprüngliche Wort ist laut Pumping Lemma uvw = a^k b^k. Bei uw fehlt also das v. Und da v nur aus a's besteht, fallen diese weg. Daher musst du sie von der ursprünglichen Zahl k abziehen.
Noch ein paar Rückfragen:
Generell. Wenn man beim Pumping Lemma pumpt und die Bedingung (1) und (2) erfüllt sind: d. h. mein Wort x = uvw
(1) |v| >= 1
(2) |uv| <= n
dann hat das Pumpen uv^i w keinerlei Auswirkung auf die 2 Bedingung. Richtig?
Ja. Wenn die Bedingungen erfüllt sind, ändert das Pumpen selbst nichts mehr daran.
"so gilt wegen |uv| <= n, dass uv ein Teilwort von a^k ist, und somit auch v."
Warum ist uv ein Teilwort von a^k?
"Wählt man i=0, so gilt u v^i w = uw, das v fällt also weg."
Dies ist klar!
Warum gilt dann uw=a^(k-|v|) b^k?
Sorry, aber mir ist dies nicht klar!