In der am Donnerstag, der letzten Woche, stattgefundenen Einsicht, die du offenbar verschlafen zu haben scheinst. 
Edit: oder aber auch nicht mitbekommen hast, da du womöglich noch gar nicht geschrieben hattest. 
Und wie genau lautet der Beweis?
Die Idee dahinter ist, dass du aufgrund der begrenzten Zustandsanzahl und da es sich um einen DFA handelte, mindestens einen Zustand mehrfach besuchen musst, um sämtliche in L enthaltenen Wörter zu akzeptieren. Dh du kannst verschiedene Abfolgen erzeugen um einen Zustand zu erreichen. Und dadurch auch zwingend Abfolgen, die eigentlich gar nicht akzeptiert werden dürften, da sie nicht in der Sprache enthalten sind.
Ich gebe mal den Anfang an: Man soll ein z angeben mit z ∈ L. Ich setze z = 0[sup]n[/sup] 1[sup]n+1[/sup] ∈ L. Und wie gesagt, n ist die Anzahl der Zustände des angeblichen DFA A. Da A z akzeptieren muß, muß es bei der z akzeptierenden Rechnung durch A einen Zustand q geben mit:
δ(q[sub]0[/sub], u) = q
δ(q, v) = q
δ(q, w) = q[sub]F[/sub]
wobei u ∈ 0*, v ∈ 0[sup]+[/sup] und w ∈ 01.
Der Zustand q kommt also in einer z akzeptierenden Rechnung doppelt vor. Dieses doppelte Vorkommen passiert bereits bei der Verarbeitung des 0-Teils. Und das Teilwort v besteht aus mindestens einer 0 (weil A ein DFA ist).
Und nun bauen Sie mit diesem Wissen ein z[sub] :nuts:[/sub] ∉ L, mit δ(q[sub]0[/sub], z[sub] :nuts:[/sub]) = q[sub]F[/sub].
Also kann es A gar nicht geben!
4 „Gefällt mir“
Ginge auch das?
Setze nL = 4; nL = 7
z = uvwxy mit:
u = 0000
v = 0
w = € (Epsilon für Arme)
x = 1
y = 111
(i) |vx| = 2 >= 1 *check*
(ii) |vwx| = 2 <= nL *check*
(iii) f. i = 0 kommt dann 0000111 raus, was in der Sprache liegt und für alle i > 0 werden 0en und 1en gepumpt,
wobei immer mehr 0en als 1en vorhanden sind. *check*
Sei L={0[sup]k[/sup] 1[sup]l[/sup] | k>l>2}.
Nein, n[sub]L[/sub]=7 ginge nicht, da das kürzeste Wort der Sprache z=0[sup]4[/sup]1[sup]3[/sup] mit |z|=7 ist und in der Pumpeigenschaft |z| ≥ n[sub]L[/sub] steht. D.h., auch dieses Wort z müßte abpumpbar sein, also ein noch kürzeres Wort der Sprache erzeugen, das es aber nicht gibt.
Die Wahl n[sub]L[/sub]=8 schließt eben dieses Wort aus. Nun ist das kürzeste Wort der Sprache das Wort 0[sup]5[/sup]1[sup]3[/sup]. Da kann man eine einzelne 0 beliebig auf- und einmal(!) abpumpen. Gefährlich sind nun allgemein die Wörter der Form 0[sup]n+1[/sup]1[sup]n[/sup] (also z.B. 0[sup]5[/sup]1[sup]4[/sup]), weil man da eine 0 nicht ohne gleichzeitige 1 abpumpen darf.
Also muß der Beweis so ablaufen:
Setze n[sub]L[/sub]=8. Sei z=0[sup]n+m[/sup] 1[sup]n[/sup]∈L mit n≥3, m≥ 1 und m+2n≥8 beliebig, aber fest.
Fallunterscheidung:
m=1: In diesem Fall ist (ganz wichtig!) n≥4. Hier werden eine 0 und eine 1 auf- und abgepumpt (das mache ich jetzt nicht formal)
m≥2: (In diesem Fall kann n=3 sein!) Hier wird nur eine 0 auf- und abgepumpt.
Bei weiteren Fragen einfach melden.
MfG
Rolf Wanka
Danke für die Antwort. Dass meine Lösug falsch ist, verstehe ich, aber mir sind noch einige Details unklar.
Mit abpumpen ist gemeint 0 oder 1 „hoch 0 nehmen“, richtig?
Warum muss ich hier nur den Fall beachten, dass ich eine 0 auf- und abpumpen kann? Ich kann ja bei 0^5 1^3 keine 1 abpumpen, weil sonst die Bedingung l > 2 verletzt würde.
Passt meine uvwxy-Aufteilung von z?
z = uvwxy mit:
u = 0000
v = 0
w = € (Epsilon für Arme)
x = 1
y = 111
Hier könnte ich ja die 1 (=x) abpumpen und hätte nach wie vor ein Wort der Sprache.
Genau, „abpumpen“ ist der Fall i=0 aus Eigenschaft (iii). Es muß also uwx∈L (Tippfehler korrigiert:) uwy∈L sein.
Haben Sie übersehen, nach was die Fallunterscheidung durchgeführt wurde?
Meine Fallunterscheidung läuft nach der Differenz m der Längen der beiden Zeichen-Teile. Ist die Differenz m=1, müssen immer eine 0 und eine 1 auf- und abgepumpt werden. In diesem Fall (d.h. m=1) ist das kürzeste mögliche Start-Wort das Wort z=0[sup]5[/sup]1[sup]4[/sup].
Ist m mindestens 2 (in Ihrem Bsp. 0[sup]5[/sup]1[sup]3[/sup] ist es das ja), läßt man die Finger von den 1-en und pumpt nur genau eine 0. Das haben Sie ja dann auch geschrieben.
Genaugenommen haben Sie da ja nur das eine Wort 0[sup]5[/sup]1[sup]4[/sup] zerlegt.
Der Fall m=1 ist konkret so abzuhandeln:
Sei z=0[sup]n+1[/sup]1[sup]n[/sup]∈L mit n≥4 beliebig, aber fest (der ∀-Quantor für alle Wörter in L mit m=1).
Setze u=0[sup]n[/sup], v=0, w=ε (epsilon für Reiche ), x=1, y=1[sup]n-1[/sup]. (der ∃-Quantor: nun müssen die Eigenschaften (i) bis (iii) nachgewiesen werden)
Dann ist |vwx| ≤ n[sub]L[/sub]=7 und vx≠ε, sowie
∀i ≥0: uv[sup]i[/sup]wx[sup]i[/sup]y = 0[sup]n+i[/sup]1[sup]n-1+i[/sup]∈L, da der 1-Teil immer mindestens drei 1-en und immer eine 0 mehr als 1-en enthält.
Für den Fall m≥2 müssen Sie sich nun wieder zuerst eine Anfangsdarstellung für z überlegen. Die Zerlegung ist dann die gleiche wie bei m=1, nur daß x≠ε (Tippfehler korrigiert:) x=ε gesetzt wird.
Wurde es etwas klarer?
MfG
Rolf Wanka
Es wurde jetzt um Einiges klarer. Nur verstehe ich nicht, warum beim Fall m≥ 2 x≠ε sein muss.
Ich hätte die Aufteilung so gemacht:
u=0[sup]n[/sup]
v=0
w=1
x=ε
y=1[sup]n-1[/sup]
Insgesamt ergibt sich damit z=0[sup]n+2+i[/sup]1[sup]n[/sup]
Wenn, wie Sie selbst geschrieben haben, in diesem Fall n≥3 ist,
bekomme ich für i=0 0⁴1³. Für alle i>0 sind immer mehr 0en als 1en im Wort enthalten.
Soll’s auch nicht. Klassischer Copy-and-Paste-Fehler von mir :nuts: 
. Das ≠ muß natürlich ein = sein.
Das w darf ja auch ε sein, also kann man ruhig y=1[sup]n[/sup] setzen. Das läuft aber natürlich auf’s Gleiche hinaus.
Ihre Konstruktion deckt jetzt aber nur die Wörter der Form 0[sup]n+2[/sup] 1[sup]n[/sup] ab. Vollständig wäre es also mit z=0[sup]n+m[/sup] 1[sup]n[/sup] für n≥3, m≥2 und: u=0[sup]n+m-1[/sup], v=0, w=ε, x=ε, y=1[sup]n[/sup].
MfG
Rolf Wanka
OK. Jetzt habe ich’s verstanden.
Vielen Dank für die ausführliche Hilfe!
Ich bin jetzt etwas verwirrt.
Funktioniert denn die ursprünglich vorgeschlagene Variante?
Wähle p = 8; z beliebig aber fest mit |z| ≥ p; Wähle x = ε, v = 0, w = 0000111, u = restliche 0, y = restliche 1 → für alle i werden 0en gepumpt, auch für i = 0 ist das Wort noch in L.
damit würde man sich ja dann auch die Fallunterscheidungen sparen:
Setze nL=8. Sei z=0^(n+m) 1^n ∈L mit n≥3, m≥ 1 und m+2n≥8 beliebig, aber fest.
Fallunterscheidung:
m=1: In diesem Fall ist (ganz wichtig!) n≥4. Hier werden eine 0 und eine 1 auf- und abgepumpt (das mache ich jetzt nicht formal)
m≥2: (In diesem Fall kann n=3 sein!) Hier wird nur eine 0 auf- und abgepumpt.
[quote=[hedgehogs dilemma = 42]]
Ich bin jetzt etwas verwirrt.
Funktioniert denn die ursprünglich vorgeschlagene Variante?
Wähle p = 8; z beliebig aber fest mit |z| ≥ p; Wähle x = ε, v = 0, w = 0000111, u = restliche 0, y = restliche 1 → für alle i werden 0en gepumpt, auch für i = 0 ist das Wort noch in L.
damit würde man sich ja dann auch die Fallunterscheidungen sparen:
[…]
[/quote]
Betrachten Sie z.B. das Wort z=0[sup]10[/sup] 1[sup]9[/sup].
Ihre Zerlegung wäre:
u = 0[sup]5[/sup]
v = 0
w = 0[sup]4[/sup]1[sup]3[/sup]
x = ε
y = 1[sup]6[/sup]
Für i=0 ergibt sich dann: uv[sup]0[/sup]wx[sup]0[/sup]y = uwy = 0[sup]9[/sup] 1[sup]9[/sup] ∉ L.
MfG
Rolf Wanka
Hallo,
ich habe mir jetzt ca eine Stunde lang die Aufgabe 3b) angeschaut, und komme einfach nicht dahinter, was mein Fehler sein könnte:
Mein Ansatz sieht dem von Lemur gleich aus.
Um die Regeln noch einmal im Beitrag zu haben:
ein beliebiges p Element N. Mein p sei 7.
|z| >= p
|vx| >= 1
|vwx| <= p
für jedes i >= 0 muss uv^iwx^i< Element der Sprache L sein.
Die Zerlegung war dementsprechend:
z = uvwxy mit:
u = 0000
v = 0
w = € (Epsilon für Arme)
x = 1
y = 111
um Herrn Wanka zu zitieren:
Aber die Zerlegung von z ist doch |z| >=p. Wo ist hier mein Denkfehler?
Der Denkfehler liegt darin, dass du nicht an das Abpumpen gedacht hast (i = 0 setzen).
Wenn du 7 wählst und du das Wort 0⁴1³ erhältst (das kürzeste Wort der Sprache → alles, was weniger 0en oder 1en besitzt, ist nicht Teil der Sprache),
kannst du dementsprechend nicht mehr abpumpen. Denn wenn du eine 0 abpumpst, hast du gleich viele 0en und 1en und wenn du eine 1 abpumpst,
verletzt du die bedingung, dass l > 2 sein muss. Und im Pumping-Lemma steht ja, dass für alle z mit |z| > p diese aufteilung uv[sup]i[/sup]wx[sup]i[/sup]y mit jedem i
noch ein wort der sprache ergeben muss. das funktioniert also mit p=7 nicht.
das funktioniert allerdings mit p=8. Da kannst du durch abpumpen das kürzeste wort der sprache 0⁴1³ erzeugen.
Aber v^0 und x^0 (was ja, so wie ich das verstanden habe, das abpumpen ist) immer noch das Wort: z = 0000111, welches weiterhin Element der Sprache ist.
Und im Pumping Lemma steht doch, dass die Länge des Wortes z größer/GLEICH p sein muss?
du musst das so sehen
wenn du sagst das dein p, bzw. nL = 7 ist, dann sind alle wörter der Länge 7 erlaubt:
also ist
0000111 Erlaubt
=> deine Aufteilung kann es garnicht geben, da du für deine Aufteilung 9 Zeichen brauchst.
Stimmt 
Das hat mich am Anfang auch verwirrt, aber ich glaube, dass du beim Betrachten des Betrags
nicht einfach das v und x außer Acht lassen kannst, weil du die abpumpst.
Wenn du dein z so aufteilst (willkürliches Beispiel, hat nix mit der Aufgabe zu tun)
u=0
v=0
w=ε
x=1
y=1
hat das z demnach den Betrag 4. Und das ist der Betrag, der zählt. Wenn du jetzt v und x abpumpst,
erhälst du zwar ein Wort, das nur noch den Betrag 2 hat. Aber das hat dich dann nicht mehr zu interessieren.
Umgekehrt kannst du dir ja auch vorstellen, dass, wenn du i=1000 setzt, die Bedingung |vwx| <= p auch verletzt wäre.
Ich bin mir da nicht 100%-ig sicher. Ich habe mich auch an den Aussagen und Beispielen von Prof. Wanka entlanggehangelt und versucht,
mir einen Reim drauf zu machen
Das liegt an der Reihenfolge, in der die P.E. die Aussagen aufzählt, was man als Mensch auch ruhig zeitlich interpretieren kann:
∃ n[sub]L[/sub] ∈ IN ∀ z ∈ L mit |z| ≥ n[sub]L[/sub] ∃ u,v,w,x,y mit z = uvwxy …
Sobald n[sub]L[/sub]=7 festgesetzt ist, besagt der ∀-Quantor, daß ab diesem Moment alle Wörter aus L betrachtet werden müssen, die aus mindestens 7 Zeichen bestehen, also auch das Wort 0[sup]4[/sup]1[sup]3[/sup]. Erst jetzt muß man für jedes dieser Wörter eine Zerlegung finden.
MfG
Rolf Wanka
1 „Gefällt mir“