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.
#72 von Übungsblatt 14 (WS2012)
a)
z.Z. L hat kf. P.E. nicht.
<=> Für Alle p ∈ N existiert ein z ∈ L, |z| ≥p für alle u,v,w,x,y ∈ {a,b,c}*, z:= uvwxy, so dass/mit :
(i) |vwx| ≤ p (ii) |vx| ≥ 1 bzw. v ≢ ε v x ≢ ε (iii) Es exisitert ein i ≥0: uv[sup]i[/sup]wx[sup]i[/sup]y ∉ L.
- Sei p “Element N” beliebig, aber fest.
- Setze z= a[sup]p[/sup]b[sup]p[/sup]c[sup]p[/sup] so dass z Element der Sprache L und |z| ≥ p.
- Sei u,v,w,x,y beliebig, aber fest.
Da v≢ε und |vwx| ≤ p.
“Trivialer” Fall:
u = a [sup] p -1 [/sup], v = a, w =ε x = ε, y= b [sup]p[/sup] c [sup]p[/sup]
Für i=0: Ein a wurde weggepumpt, damit nicht mehr #a = #b = #c. q.e.d.
PROBLEM: Es kann nur an zwei stellen gepumpt werden. => Entweder nur ‘a’s, oder a,b’s oder b’s oder b’ und c’s oder nur c’s können gleichzeitig gepumpt werden.
=> L hat nicht kf P.E.
(Außerdem wissen wir zumindest, dass Sprache nicht kontextfrei ist, da nur p-Teller auf den Stapel gelegt werden können und danach wieder abgeräumt werden können, aber dann nicht mehr wissen wieviele Teller maximal auf dem Stapel lagen bzw. in Summe auf dem Stapel hätten liegen müssen, wenn nicht abgeräumt worden wäre… [aber kännte ja trotzdem P.E. haben… :-(] )
Mein formales Problem: Müssen alle Möglichkeiten der Zerlegung für gesetztes z “durchgemacht” werden… ?
Kann ich das so schon stehen lassen
Für das gewählte Wort müssen alle (erlaubten) Zerlegungen funktionieren, d.h. “Sei z = uvwxy eine beliebige, aber feste Zerlegung von z mit |vwx| <= p und |vx| >= 1”
Die Aufgabe ist sehr ähnlich zu der in der Vorlesung “Beispiel 3.29 c)”. Im Grunde “sieht” man, dass durch die schlaue Wahl deines Wortes nicht alle drei Zeichen erwischt werden können und die Schlussfolgerung für alle Zerlegungen gelten muss. Bei anderen Aufgaben sieht man das aber nicht ganz so schön, mindestens da braucht man dann Fallunterscheidungen für verschiedene Zerlegungen.
Ob man solche Fallunterscheidungen in der Klausur immer braucht, oder eine kurzer Erklärung reicht, weiß ich aber nicht. In der Vorlesung war es bei besagtem Beispiel letzteres.
mit z=uvwxy. 
Es kann v = ε sein. Es ist vx ≢ ε!
Hier gleich weitermachen mit: Wegen |vwx| ≤ p enthält vx maximal nur zwei Sorten von Zeichen. Also wird mit i=0 das Wort uwy erzeugt, in dem maximal von zwei Sorten die Anzahl verkleinert wird, wegen vx ≢ ε von einer auch mindestens. Und da stimmt dann die Anzahl nicht mehr mit der nicht vorkommenden Sorte überein … fertich
So, wie es jetzt oben steht, werden alle Fälle abgedeckt. Wichtig für das „alle Fälle“ sind die Wörter „mindestens“ und „maximal“. Dann(!) reicht es.
MfG
Rolf Wanka
The Take Home-Message:
Danke. Jetzt komme ich langsam zu Recht.
Weitere Postings folgen…