Pumping Lemma
Pumping Lemma
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?
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?
Zuletzt geändert von hstr am 12. Mai 2011 13:09, insgesamt 2-mal geändert.
Re: Pumping Lemma
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)
\(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)
Re: Pumping Lemma
Ich hatte die falsche Sprache hingeschrieben, hab die ganze Frage nochmal überarbeitet.
Re: Pumping Lemma
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
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

Re: Pumping Lemma
@ 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?
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?
Re: Pumping Lemma
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.hstr hat geschrieben: Und darf man dann auch das Wort so zerlegen:
u = a^(n-k)
v = a^k
w = a^1 b^n
Ziel ist, dass das Wort nach dem "pumpen" nicht mehr in L liegt.
Re: Pumping Lemma
@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?
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?
Re: Pumping Lemma
Vielen Dank danny, jetzt hab ich es verstanden!
Re: Pumping Lemma
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
Danke
Re: Pumping Lemma
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.