Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Pumping-Lemma Klausurvorbereitung
Hey, folgende 2 Aufgaben mal zum Start versucht. Bin mir aber nicht sehr sicher… :
Kann man da einfach “Rest” schreiben?
Vielen Dank 
Hey,
zur b): Du schreibst, dass „x beliebig, aber fest“ sein soll, aber man darf sich hier kein Wort raussuchen, sondern muss zeigen, dass für ALLE Wörter mit gewisser Mindestlänge die Pumpeigenschaft gilt. Bei dir ist das wohl p und da die feste Wahl auch richtig.
Nun wird deine Schreibweise ein wenig unübersichtlich und falsch ;), denn v = {0,1}^3 bedeutet, dass v eine MENGE ist mit v = {000,001,010,…,111}. Nach längerem Anschauen vermute ich 
, dass du damit meinst, dass u das erste Zeichen von x ist und v die Zeichen zwei bis vier, w damit die verbliebenen Zeichen. Das würde ich entweder so in Worten hinschreiben oder Formal: sei x € L und x = x1,x2,…,xn mit n = |x|; damit: u = x1; v = x2,x3,x4; w = x5,…,xn;
Den Test „1.“ verstehe ich nicht. Warum die 4? Außerdem hier mit u,v und w arbeiten, so wie du sie ja auch vorher definiert hast. Bei 2. eine Formalität: mit den Betragsstrichen |…| ist die Länge des Wortes gemeint und damit aus den natürlichen Zahlen. Also entweder Betragsstriche weglassen oder epsilon durch 0 ersetzen, wobei Letzteres eher der Definition entspricht :).
Der 3. Punkt ist in Ordnung.
Du solltest mehr darauf achten, das was du sagen willst, formal korrekt aufzuschreiben. Ich bin zwar kein Hellseher ;), aber in der Klausur verlierst du so nur unnötig Punkte, obwohl der Gedankengang wohl korrekt ist.
zur 3c):
Hier hast du gezeigt, dass für eine spezielle Zerlegung das Pumping-Lemma nicht gilt. Man soll aber zeigen, dass es für jede beliebige natürliche Zahl n ein Wort x gibt mit |x| >= n, welches sich egal in welcher Weise nicht derart Zerlegen lässt, dass die Bedingungen des Lemmas erfüllt sind. Ebenso sind die drei Zeilen ab „|uvw| >= p“ ein wenig zusammenhanglos. Es wird nirgendwo gesagt, was denn u,v und w konkret ist. Du meintest auch wohl |vwx| statt |uvw| und kleiner statt größer ;).
Gern geschehen :), ich habe von der Erstellung meiner Antwort ebenfalls profitiert hinsichtlich der Klausur ;).
Also, danke erst mal für die schnelle Antwort.
Hab die erste Aufgabe jetzt korrigiert und denke die passt so weit. Hab eigentlich nur weggemacht was du gesagt hast. Danke für das x1,x2…xn , mir hat da die richtige Schreibweise gefehlt. Also schick ich die nicht nochmal her. Die 4 bei Test 1 sollte ne 7 sein und is irgendwo mal verändert und nicht wieder zurückgeändert worden und das zweite warn minigedankenfehler.
Die 3C hab ich jetzt praktisch noch mal von vorne probiert, hoffe das ist jetzt besser:
Ja, das ist viel besser ;). Ich denke, es müsste in den letzten 3 Zeilen noch m >= l und l >= k statt mit Gleichheitszeichen stehen, weil die Aufteilung ja auch so gewählt werden könnte, dass in v oder x mehr als ein Zeichen steht.
Ansonsten habe ich nichts zu bemängeln ;).
Ich hab das aehnlich gemacht, bin mir aber nicht sicher ob ich die Pumpeigenschaft einwandfrei beweisen hab,
weil ich manche woerter aus L nicht erstellen („aufpumpen“) kann:
Fuer alle z gilt: |z| >= p
waehle p = 4
u ∈ {a,b}^1
v ∈ {a,b}^3
w = epsilon
x = epsilon
y ∈ {a,b}^3
i) |v w x| <= p
= |v epsilon epsilon| <= 4
= 3 <= 4
ii) |v x| >= 1
= |v epsilon| >= 1
= 3 >= 1
iii) Fuer alle i >= 0 muss gelten:
u v^i w x^i y
= u v^i y ∈ L
i=0:
u y => |u y| = 1 + 3 = 4
=> uy ∈ L
i=1:
u v^1 y => |u v y| = 1 + 3 + 3 = 7
=> uvy ∈ L
i=2:
u v^2 y => |u v^2 y| = 1 + 6 + 3 = 10
=> uv^2y ∈ L
→ Fuer alle i >= 0 ist |u v^i y| >= 4 und nicht durch 3 teilbar
Hi Feni,
dein p ist falsch gewählt, das muss für deine Belegung 7 sein. Als groben Richtwert für p kannst du dir merken, die Minimallänge des durch L gebildeten Wortes (4) + 1x die Länge des pumpbaren Teils (|v| = 3). Ansonsten kannst du deine Zerlegung nicht abpumpen.
Und ich meine, es gäbe 2 Fälle in dieser Pumping Aufgabe… Es gilt ja, dass |z| nicht durch 3 teilbar ist, du hast jetzt ein z generiert, was zwar nicht durch 3 teilbar ist, jedoch den anderen Fall, der auch erlaubt ist ausblendet.
Ich kann das schwer beschreiben, aber:
1 2 3 4 5…
X X X X
Es sind ja als Wortlänge 4 UND 5 erlaubt, aber 6 nicht, deine Worte sind immer nur 4,7,10… lang.
Mir fällt aber gerade auch nicht die passende Formulierung für einen Wert, der nicht durch 3 teilbar ist, ein.
//Edit:
Fallunterscheidung?
Fall 1: |z| = 7 (=> p = 7):
u = {0,1}^4
v = {0,1}^3
x = epsilon
Fall 2: |z| = 8 (=> p = 8):
u = {0,1}^5
v = {0,1}^3
x = epsilon
Damit hättest du beide Fälle abgedeckt…(? ^^)
Aber dann ist ja
|z| >= p
verletzt. (fuer die weggepumpten Faelle)
z.B.
Fall 1: |z| = 7 (=> p = 7):
u = {0,1}^4
v = {0,1}^3
x = epsilon
iii) Fuer alle i >=0:
uv^i >= p
Wenn jetzt aber i = 0: |uv^0| = 4
Und damit ist ja |z| >= p verletzt, oder?
Das mit den Faellen gefaellt mir! 
Für alle Worte z in L, für die gilt |z| >= p muss das Wort nach dem Abpumpen noch in L liegen. Die Bedingung |z| >= p muss nur davor gelten.
Und zu eurem Fall noch: Den “Rest” des Wortes in w und nicht in u, sonst gibts n Problem mit der ersten Bedingung: |uv| <= p