Pumping Lemma

[hstr]

Hallo, ich hab eine Frage zum erstellen bzw. zerlegen eines Wortes mit dem Pumping Lemma.
Ist es erlaubt das Wort x=a^(n+1) b^n aus der Sprache L = {a^n b^m € {a,b}* | n > m} zu wählen?
Und darf man dann auch das Wort so zerlegen:
u = a^(n-k)
v = a^k
w = a^1 b^n
Ich frage deshalb, weil mein Tutor erklärt hat man darf keine konkrete Zahl als Hochzahl in u,v,w nehmen.
(z.B. u=a^3 oder v=a^5)
Oder ist das trotzdem erlaubt, wenn schon in dem gewählten Wort eine Zahl als Hochzahl vorkommt?
(in diesem Fall a^(n+1)

Und nochwas, ist es möglich das n (Anzahl der Zustände) beim Pumping Lemma 1 ist?

[kbraden]

Ich verstehe deine Frage zwar nicht (wir scheinen das Pumping Lemma unterschiedlich zu verstehen), aber:

\(x=a^{n+1} b^n \notin L = \{a^n b^n | n \in N\}\)
(Sprich: dein Wort x ist nicht in der Sprache L, die Annahme ist falsch)

[hstr]

Ich hatte die falsche Sprache hingeschrieben, hab die ganze Frage nochmal überarbeitet.

[danny]

Du weißt, dass |uv| <= n sein muss, daher hast du ja schon richtig erkannt, dass u und v nur as enthalten können.
Allerdings müssen u und v zusammen ja nicht die Länge n haben (sie können ja auch kürzer sein).
Deshalb darfst du nicht annehmen, dass w genau ein a enthält.

Angenommen u enthält k as und v enthält l as (wobei k+l <= n gelten muss und l >= 1). Dann weißt du, dass noch (n+1)-(k+l) as übrig sind für das w.
Dann sähe deine Zerlegung so aus:

u = a^k
v = a^l
w = a^(n+1-k-l)b^n

So, ich hoffe ich kam bei den ganzen Buchstaben jetzt nicht durcheinander und konnte dir helfen

[kain]

@ danny

zu untersuchen => a^nb^n

für = 3:

u = aa
v = a
w = bbb

nach PL:
u^k = 2
v^l = 1
w^(n+1-k-l) = 4 - 2 - 1 = 1
also w enthält 1 a mehr wie uv => nicht regulär?

[hymGo]

Und darf man dann auch das Wort so zerlegen:
u = a^(n-k)
v = a^k
w = a^1 b^n

Die Zerlegung des Wortes darfst du nicht selbst festlegen. Diese wird immer von "deinem Gegner" , der versucht zu zeigen, dass die Sprache doch regulär ist gewählt. Du nimmst einfach an, dass n das n aus dem Pumping Lemma ist. Dann darfst du dir ein Wort x wählen was natürlich in L liegen muss. Also wäre hier dein x = a^n+1 b^n eine korrekte Wahl. Als nächstes ziehst du an Hand der Bedingungen (|uv| <= n und |v| >0) Rückschlüssel auf die Zerlegung u,v,w ziehen. Man kann z.B. erkennen, dass v nur a's enthält. Aber, dass w= a^1 b^n ist kannst du in dem Fall nicht schließen, da ja auch mehr oder weniger als ein a in w sein kann.
Ziel ist, dass das Wort nach dem "pumpen" nicht mehr in L liegt.

[danny]

@kain:

ich verstehe deine Antwort nicht ganz.
a^nb^n kommt ja als Wort garnicht in Frage, da die Sprache L = {a^n b^m € {a,b}* | n > m} ist, oder wolltest du auf etwas anderes hinaus?

[hstr]

Vielen Dank danny, jetzt hab ich es verstanden!

[kain]

Man wendet ja das PL an, indem man v^m ändert. Wann nimmt man (z.B.) m = 2 oder m = 0 für v^m (x = uv²w, x = uw)?


Danke

[dschneid]

Das ist ja gerade der Witz dabei: Es kommt auf die Sprache an, und lässt sich nicht allgemein sagen. In den allermeisten Fällen (wenn du dein zerlegtes Wort x passend gewählt hat) funktioniert m = 2, aber es gibt auch Sprachen, in denen man nur durch Weglassen des Mittelteils zum Ziel gelangt.