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.
Pumping Lemma für kontextfreie Sprachen
Hallo,
Wie zeige ich das ww mit w∈{0,0} nicht kontextfrei ist? (Kommt in ThI1 - 5. Übung - Aufgabe 22 iv vor)
Dummerweise sind kontextfreie Sprachen bzgl. Schnitt ja nicht abgeschlossen - also nix mit a^nb^ma^n^bm und pumpen?
viele Grüße
Matthias
wenn n die pumping zahl ist wählst du l(w) = n also is ww genau 2n lang. jetzt muss aber uvwxy = ww sein, |vwx| ≤ n und |vx| ≥ 1. vwx erstreckt sich also über maximal ein w, wenn vxw nur eins der beiden w’s abdeckt is ja klar das die symetrie verloren geht (oder?). wenn vwx beide w’s (zum teilo) abdeckt kann man also ww so schreiben
stst (w = st) und vxw erstreckt sich über ts (das in der mitte). pumpen macht also sttsst und stt ≠ sst. also nicht in L(G).
Ersteinmal danke für die Antwort 
Du schriebst u.a.:
Woher weisst Du das es das macht? Schliesslich werden beim Pumpen nur v und x potenziert, nicht aber w.
Vielleicht kann man Deine Argumentation aber insoweit nutzen, dass man ww in stpstp aufteilt und w „halt“ p ist.
Dann würde durch die Potenzierung sttpsstp werden.
ja du hast recht.
hmm… steht im skript nicht das beispiel mit w = 2n und ww = 4n länmge? das würde dieses beispiel erklären. hmhmhmhmhmhmhmhm… ich muss d amorgen mal drüber nachdenken. sorry
Hmn. Willst Du damit sagen, ich hätte keinen Fehler gemacht. Also quasi das ich recht hätte?
Nicht wirklich. Ich meine … wir sprechen hier von ThI.