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.
Pumpeigenschaft
Hallo allesamt,
kann mir jemand sagen, ob meine Idee für Blatt 14, Aufgabe 73 (kontextfreie Pumpeigenschaft) stimmt?
L={a^p b^n c^m d^(n+m)|n,m >=0, p >=1} hat die k.f. Pumpeigenschaft:
Wähle n=3
Sei z \in L beliebig aber fest
Wähle für die Zerlegung z=uvwxy:
u=a a^j b^k c^l
v=c
w=\epsilon
x=d
y=d^(k+l)
Nacheis der Eigenschaften:
(1) |vx|=|cd|=2>=1
(2) |vwx|=|cd|=2<=3
(3) Sei i>=0 beliebig aber fest: uv^iwx^iy = a a^j b^k c^l c^i d^i d^(k+l) = a^(1+j) b^k c^(l+i) d^(i+k+l) \in L
“Sei z ∈ L, |z| ≥ 3 (nicht vergessen!), beliebig aber fest” bedeutet auch für z=aaa ∈ L … Das deckt Ihre Zerlegung nicht ab. Eine Fallunterscheidung ist da nötig.
MfG
Rolf Wanka
hey,
nach meiner Lösung sollte die Sprache die Pumpeigenschaft nicht haben.
Sei p beliebig aber fest
setze x = a b^p c d^(p+1) => |x| >= p
Fall 1 u != epsilon
da |uv|<= p und v != epsilon , v = b^z mit 1<=z<=p
u = ab^(p-z)
=> für i=0 ist x = ab^(p-z)cd^(p+1) => x notin L
Fall u=epsilon
mit i=0 is x = bcd^(p+1) damit ist x notin L
somit hat L nicht die kontextfreie Pumpeigenschaft.
Oder seh ich das falsch ?
Meine Lösung :
Setze nl = –
sei z in L mit |z| >= n beliebiug aber fest
d.h : z = a(a^r)(b^n)(c^m)(d^n+m)
**falls m=0 und n>0
setze : u = epsilon , v = a , w= a^r , x = b und y = b^l d^n
|vx| >= 1 , |vwx|<= n und u(v^i)w(x^i)y = (a^i) (a^r) (b^i) b^l d^n in L
setze : u = a(a^r)(b^j)b
v = b
w = epsilon
x = d
y = d(d^j)
|vx| >= 1 , |vwx|<= n und u(v^i)w(x^i)y = a(a^r)(b^j)b(b^i) (d^i)d (b^j) = a(a^r)(b^i+j+1)(d^i+j+1)
**(fast gleicher Beweis fuer m>0 und n=0)
**falls m=0 und n=0 : (k>=3)
setze : u = epsilon , v = a , w= epsilon , x = a und y = a^(k-2)
|vx| >= 1 , |vwx|<= n und u(v^i)w(x^i)y = (a^i)(a^i) a^(k-2) in L
usw … Alle möglichen Fälle für das Wort z müssen abgedeckt werden 
(Rest ist fast ähnlich :D)
was ist denn bei dir l und was n ? du musst doch n anfangs konkret setzen.
ich versteh den teil nicht ganz, weil wenn l = n wäre würde dein z nur in L sein für i = 0. also müsste dein n = l+i sein. Da du aber n konkret setzen musst wiederspricht sich das doch, weil die regel ja für alle i gelten muss, wenn du beweisen willst das die Sprache die Pumpeigenschaft hat?
Gruß
Falscher Film :huh: : Sie schauen auf die reguläre P.E.
MfG
Rolf Wanka
PS: Noch ein wenig Klugsch…rei 
: Für jede beliebige Sprache L gilt:
(i) L hat die reguläre P.E. ⇒ L hat die kontextfreie P.E. (Kleine Aufgabe: warum?)
(ii) L hat die reguläre P.E. nicht ⇒ Man weiß nichts über die kontextfreie P.E. (Kleine Aufgabe: warum?)
Hier müssen Sie sich entscheiden! Z.B. reicht nl = 3 aus.
Sie müssen natürlich nun auch hier an den richtigen Stellen nl benutzen:
Von mir zur Erklärung (und vielleicht milden Vereinfachung durch drüber Reden) eingefügt:
Fängt das z mit mindestens zwei a’s an, dann wird ein genau a gepumpt (d.h. v=a, x=ε): Man kann es wegnehmen (i=0) und beliebig oft einfügen.
Fängt das z mit genau einem a an, wird geschaut, ob es mindestens ein c gibt. Falls ja, wird am Grenzbereich c auf d (d.h. v=c, w=ε, x=d) gepumpt. Gibt es kein c, ist der Grenzbereich b auf d, und dann wird der gepumpt (d.h. v=b, w=ε, x=d).
Wenn ich zeigen soll, dass eine Sprache nicht die Pumpeigenschaft hat, und ich die Pumpkonstante p hab, darf ich dann in x=uv^i w mein i auch abhängig von p settzen, also sagen für i=p oder so ist das Wort nicht in der Sprache, oder geht das nicht?
Klar dürfen Sie das. Auf der letzten Seite von Blatt 13 (Hardware-Software-Co-Design › Lehrstuhl für Informatik 12) ist in der Zeile (*) an der Stelle, an der es um die Wahl von i geht, das p ja „bekannt“, da es „beliebig, aber fest“ ist.
MfG
Rolf Wanka
Eine Frage zu Aufgabe 58:
L_1 = {w| w ∈ {0,1}, w enthält doppelt so viele 0en wie 1en}
L_2 = {c^iw | i >= 1, w ∈ L_1} u {0,1}
Zu zeigen: L_2 hat die reguläre Pumpeigenschaft.
Meine Lösungsmitschrift:
Setze p = 1.
Sei x ∈ L_2 beliebig aber fest mit |x| >= p.
Aus |uv|<= p folgt:
(1) u = epsilon
(2) v = c
(3) w = Rest
Für i > 0 ist klar, dass uvw ∈ L_2 ist, aber der Fall i = 0 irritiert mich, weil laut Sprache das dortige i >= 1 sein muss. Ich habe hier stehen:
Fall i = 0: c’w ∈ L_2 oder w ∈ L_2,
aber w ∈ L_2 stimmt doch nicht, weil dann die Bedingung i>= 1 nicht erfüllt ist, oder?
L_2 ist ja die Vereinigung zweier Mengen, also L_2 = A ∪ B mit A = {c[1]j[/b]w | j ≥ 1, w ∈ L_1} und B = {0,1}*. (Zur Sicherheit habe ich die Variable i durch die Variable j ersetzt, damit es kein Durcheinander mit der in der Pumpeigenschaft vorkommenden Variablen i gibt; kann es sein, daß Ihre Irritation hier begründet ist?)
Betrachten Sie ein konkretes Beispiel: x = c010001 ∈ A.
Mit v=c ist das Aufpumpen des c’s (i ≥ 1) offensichtlich im grünen Bereich und das Wort bleibt in A. Und das Abpumpen (i = 0)? Das führt zum Wort 010001, und das „verläßt“ A und ist nun in B: 010001 ∈ {0,1}* = B. Aber es ist noch immer in L_2, und nur das zählt.
MfG
Rolf Wanka
b ↩︎
Denkfehler gefunden - vielen Dank! 
Geht das nicht viel einfacher wie folgt:
nach Definition L1⊆{0,1}, also L2={0,1}
L2 entspricht genau der Sprache des regulären Ausdrucks {0,1}*, also L2 regulär.
⇒L2 hat die reguläre Pumpeigenschaft.
L2 ist nicht regulär. Sie übersehen den Buchstaben c.
MfG
Rolf Wanka
Ich hab die Sprache L= {1^p |p Primzahl } und will zeigen, dass sie nicht kontextfrei ist. Kann ich dann so vorgehen:
Sei n Element IN beliebig aber fest. Setze z=1^m wobei m die nächstgrößere Primzahl nach n ist. |z| ist somit auch größer als n.
Sei z=uvwxy beliebig aber feste Zerlegung mit |vwx|<=n, |vx|>=1. => vx=a^k, 1<=k<=n
Somit ist zi=a^(m+k*(i-1))
Setze i=m+1
=> a^(m+k*(m+1-1))=a^(m*(k+1)) aber m*(k+1) ist keine Primzahl, da durch m teilbar. Also ist zi für i=m+1 nicht in L, und L hat somit die kf. Pumpeigenschaft nicht und kann deshalb auch nciht kontextfrei sein.
Darf man das so machen, weil eigentlich ist mein m doch auch bekannt, und ich darf es für i verwenden.
Eine generelle Frage:
Wenn ich zeige, dass eine Sprache die (kontextfreie) Pumpeigenschaft nicht hat, darf ich, um das i zu wählen, beliebige Fallunterschiedungen machen?
Also z.B.:
Fall u = epsilon:
i = 0 …
Fall |u| < n_L:
i = 2 …
Fall |u| >= n_L:
i = 3 …
Ja natürlich. Aufgabe ist ja zu zeigen, daß jede Zerlegung z = uvwxy kaputtgepumpt werden kann. Aber für jede einzelne Zerlegung kann das benötigte i ein anderes sein. Sie müssen halt aufpassen, daß Sie keine Zerlegung übersehen. Das ganze ergibt sich direkt aus der Reihenfolge der Quantoren, die, wie ich ja nicht müde werde zu betonen, ganz wichtig ist.
MfG
Rolf Wanka
Wie ich in der Antwort eins drüber schon geschrieben habe: Ja, die Reihenfolge der Quantoren erlaubt Ihnen das.
MfG
Rolf Wanka
Hätte es somit gereicht zu sagen, dass die regulären Sprachen Teilmenge der kontextfreien Sprachen sind und diese daher deren Eigenschaften besitzen, ohne weiter mit dem Pumping-Lemma zu „rechnen“?