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.
Pump-Eigenschaft
Hallo alle zusammen ,
habe mal eine Frage , ob mit den Beweis für Kontextfrei Sprache so geht ! …
ich habe die Sprache L = {a^k b^n c^m d^n+m | k>=1 , m,n>=0 }
gefragt ist den Beweis dass die Sprache die Pump Eigenschaft besitzt …
meine Lösung :
ich wähle nL = k+2m+2n
Fall 1 :
u=a^k
v=b^n
w=c^m
x=d^n
y=d^m
Fall 2 : (n=0)
u=a^k
v=c^m
w=epsilon
x=d^m
y=epsilon
Fall 3 : (m=0)
u=a^k
v=b^n
w=epsilon
x=d^n
y=epsilon
Fall 4 : (n=0 und m = 0 )
u=epsilon
v=a^k
w=epsilon
x= epsilon
y=epsilon
für alle mögliche Zerlegung , wird die folgende Eigenschaften erfüllt ( da nL von k und m und n abhängig ist )
-
|vx|>=1 immer in alle 4 Fälle
-
|vwx| < = nL
fall 1 : |vwx|= 2n+m <= nL
fall 2 :|vwx|= 2m <= nL
fall 3 : |vwx|= 2b <= nL
fall 4 : |vwx|= k <= nL -
für all i , in alle Zerlegungen , wird das gepumpte Wort in L bleiben .
[color=crimson]ist das so gemeint in diese Aufgabe … kann man so machen und wird das richtig sein ? …
[/color]
Fall 4 geht für i = 0 kaputt, da jedes Wort in L mindestens ein a enthalten muss.
dann muss man Fall 4 so machen , dass man in u oder w noch einen a macht und in v = a^k lassen , dann garantiert mann , dann in z ein a vorkommt …
Ja, das funktioniert bei deiner Lösung aber grade nicht. Das Wort a ist zwar in L, aber nicht pumpbar. Du musst also garantieren, dass deine nL immer >1 ist. Bei dir ist das bei m=0, n=0 und k=1 allerdings nicht der Fall.