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.
Kontextfreie Pumpeigenschaft
Hallo Zusammen,
mal eine Frage zur k.f. P.E., konkret an der Aufgabe 57 von Blatt 11 verdeutlicht:
Es soll gezeigt werden dass die Sprache L = {w | w \in {a,b,c}*, #a(w) = #b(w) = #c(w)}
die k.f. P.E. nicht besitzt.
Also Standartmäßiges Vorgehen:
(1) Sei nL beliebig aber fest
(2) Wähle z = a^nL b^nL c^nL
(3) Sei Zerlegung z = uvwxy beliebig aber fest
Hier lautet nun die Begründung dass durch Regel |vwx| <= 1, maximal zwei Zeichen gepumpt werden können und somit die Regel (iii) verletzt würde.
Wenn ich das ganze aber nun von der Gegenseite betrachte, dann kann ich doch folgendes tun:
v = abc; w,x = \epsilon; u = restliche a (a^{nL -1}); y = restliche b und c (b^{nL-1} + c^{nL -1})
Bsp.:
nL = 3:
Man bekommt also z = aaabbbccc
=> v=abc, u=aa, y=bbcc
Regeln (i) und (ii) sind offensichtlich nicht verletzt, und Regel (iii) auch nicht, da ich ja doch 3 Zeichen pumpe?!
Wo ist hier der Fehler?
In aaabbbccc kommt kein abc vor, du kannst dein v also nicht so wählen.
ah erkenne gerade zum ersten Mal dass die Reihenfolge wichtig ist:D
ja dann ist klar
Danke Volschaf
ich seh’s schon richtig, dass die Sprache, so wie sie gegeben ist, sämtliche abc-Reihenfolgen zulässt, bei denen einfach die Anzahl gleich ist, die Reihenfolge aber egal, oder?
Also abcabc ist genauso in der Sprache wie aabcbc oder aabbcc.
Und da die negierte Definition vom Pumping-Lemma ja sagt “…es gibt ein z…”, kann ich mir das z so aussuchen, dass die reihenfolge a[sup]n[/sup]b[sup]n[/sup]c[sup]n[/sup] ist und kann im prinzip dann denselben Beweis anwenden, wie wir ihn für L ={a[sup]n[/sup]b[sup]n[/sup]c[sup]n[/sup] | n ∈ N} geführt haben.
Habe ich das richtig verstanden, oder mache ich da einen Denkfehler?
Ja, das hast du richtig verstanden.