Pumping Lemma

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Pumping Lemma

Beitrag von hstr » 12. Mai 2011 08:57

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?
Zuletzt geändert von hstr am 12. Mai 2011 13:09, insgesamt 2-mal geändert.

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Pumping Lemma

Beitrag von kbraden » 12. Mai 2011 12:32

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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Re: Pumping Lemma

Beitrag von hstr » 12. Mai 2011 12:51

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

danny
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 17. Okt 2010 22:32

Re: Pumping Lemma

Beitrag von danny » 12. Mai 2011 15:54

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
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Pumping Lemma

Beitrag von kain » 12. Mai 2011 16:49

@ 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?

Benutzeravatar
hymGo
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 209
Registriert: 4. Okt 2009 23:17

Re: Pumping Lemma

Beitrag von hymGo » 12. Mai 2011 17:36

hstr hat geschrieben: 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
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 17. Okt 2010 22:32

Re: Pumping Lemma

Beitrag von danny » 12. Mai 2011 17:57

@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
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Re: Pumping Lemma

Beitrag von hstr » 12. Mai 2011 19:35

Vielen Dank danny, jetzt hab ich es verstanden!

kain
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 30. Sep 2009 13:49

Re: Pumping Lemma

Beitrag von kain » 12. Aug 2011 13:11

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
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 271
Registriert: 14. Dez 2009 00:56

Re: Pumping Lemma

Beitrag von dschneid » 12. Aug 2011 13:47

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.

Antworten

Zurück zu „Archiv“