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.
Kontextfreies Pumping-Lemma
Wir haben eine Frage zur Hausaufgabe 54 a) i)
Dort ging es darum zu zeigen dass die Sprache L_2 = { a^i b^j c^k | i < j < k } die k.f. Pumpeigenschaft nicht besitzt.
Unsere Argumentation in der Hausaufgabe auf die wir auch volle Punktzahl bekommen haben war wie folgt:
n_L beliebig, aber fest.
Sei z = a^(n_L) b^(n_L + 1) c^(n_L + 2)
|z| = 3 * n_L + 3
Stelle vwx an den Anfang von z. Da |vwx| <= n_L und z mit n_L a’s beginnt besteht vwx nur aus a’s.
|vx| >= 1 gilt, da n_L aus den natuerlichen Zahlen.
Setze nun i = 2. Das entstandene Wort u v^2 w x^2 y besitzt mehr a’s als c’s => u v^2 w x^2 y nicht aus L_2.
=> L_2 hat die k.f. Pumpeigenschaft nicht.
Jetzt ist unsere Frage aber folgende:
Darf man sich jetzt zum Beweis der kontextfreien Pump-Eigenschaft die Aufteilung aussuchen oder nicht?
Weil wir mittlerweile der Meinung sind, das man den obigen Beweis genauso auf a^n b^n anwenden koennte, von dem wir wissen, dass es die k.f. Pumpeigenschaft hat,
und man damit die Wahl selber ueberlassen bekommen muss, damit das ganze funktioniert.
Andererseits, wenn man die Wahl hat, dann koennte ich doch in diesem Fall fuer diese Sprache immer nur als v das letzte b, w als leer, und x als das erste c waehlen, und daran kann ich pumpen soviel ich lustig bin.
Wenn man kontextfreie Pumpeigenschaft beweist, dann darf man das.
Im vorliegenden Fall zeigt man aber, dass keine kontextfreie Pumpeigenschaft vorliegt und da darf man das nicht.
Wenn du die Definition für nicht-Pumpeigenschaft anschaust, steht da „es gibt ein z, sodass für alle Zerlegungen uvxwy=z …“
Zu zeigen ist bei der Aufgabe ja quasi:
∀n_L ∈ ℕ. ∃z ∈ L. |z| ≥ n_L. ∀u, v, w, x, y, z = uvwxy. (|vx| ≥ 1 ˄ |vwx| ≤ n_L ⇒ ∃i ≥ 0. uv^iwx^iy ∉ L))
Der Beweis in eurer Hausaufgabe ist daher meiner Meinung nach nicht vollständig.
Nur weil ihr zeigt, dass es eine mögliche Aufteilung von z gibt, bei der ihr ein i findet, sodass das auf-/abgepumpte z ∉ L, heißt das noch nicht, dass es ∀z gilt.
Ihr müsst quasi alle möglichen Fälle annehmen und jeweils zeigen, dass z ∉ L für den jeweiligen Fall gilt.
Der von euch angenommene und damit erste Fall war ja:
Fall 1: vwx am Anfang, d.h. v und x enthalten nur a’s. Pumpt man a’s dazu, ist irgendwann h > j und damit z ∉ L.
Es gilt allerdings auch noch die folgenden Fälle zu zeigen:
Fall 2: vwx in der Mitte, d.h. v und x enthalten nur b’s. Pumpt man b’s dazu, ist irgendwann j > k und damit z ∉ L.
Fall 3: vwx am Ende, d.h. v und x enthalten nur c’s. Für i = 0 wäre dann j > k und damit z ∉ L.
Fall 4: vwx im Übergangsbereich a nach b, d.h. vwx enthält nur a’s und b’s. Pumpt man b’s dazu, gilt irgendwann j > k und damit z ∉ L.
Fall 5: vwx im Übergangsbereich b nach c, d.h. vwx enthält nur b’s und c’s. Pumpt man b’s ab (also z.B. i = 0), gilt irgendwann h > j und damit z ∉ L.
EDIT: too slow :<