Ich habe es nur mit zwei Fällen gemacht: enthält b oder enthält kein b. Wenn es geht, dann pumpe ich bs ansonsten as. Also einfach dein 2. und 3. Fall zusammengefasst.
Hätte es Ihnen bei der Aufgabe gereicht, zu begründnen, dass es einen Kellerautomat gibt, damit die Sprache kontextfrei ist, und somit auch die kf. P.E besitzen muss…
Ich gehe stark von falsch aus, weil ich keinen Zusammenhang sehe, aber mir fehlt eine Begründung/ein Gegenbeispiel.
Kann mir jemand auf die Sprünge helfen?
Wenn die Aufgabe 73 so formuliert ist, wie sie es ist, beinahe ja. Wir haben ja die Beweisrichtung „NPDA ⇒ CFG“ nicht durchgeführt, aber in der Vorlesung wurde das ja als Tatsache verkauft, trozdem muß man’s mir glauben . Einfacher wäre vielleicht die Angabe einer kf. Grammatik gewesen. Natürlich muß dann in jedem Fall auch der Hinweis auf das Pumping-Lemma kommen: Ist L kontextfrei, dann hat L die kontextfreie Pumpeigenschaft.
Insgesamt sind gerade die Aufgaben des letzten Blattes natürlich unter dem Gesichtspunkt zu sehen, daß Sie über den Stoff auch nachdenken und ggf. mehrere Lösungsvarianten ausprobieren, also gerade hier den „Umweg“ über einen NPDA oder eine kf. Grammatik und auch direkt. Auch wenn ich jetzt 2€ ins Phrasenschwein einwerfen muß: Übung macht den Meister.
Koennte man das Wort nicht wie folgt zerlegen und sich diese Fallunterscheidung (die ich btw nich’ versteh’) damit sparen:
L={a^n b^m c^n+m | n,m ≥ 0} == {a^n b^m c^m c^n} besitzt die k.f. Pumpeigenschaft
Mit nl = 2, sodass fuer alle z \in L mit |z| >= nl mit z = uvwxy, gilt:
(1) |vx| >= 1
(2) |vwx| <= nl
(3) fuer alle i >= 0 gilt: uv^iwx^iy \in L
Mit:
u = a^n,
v = b,
w = epsilon,
x = c,
y = c^n
ist:
(1) erfuellt: |vx| = |b c| = 2 >= 1
(2) erfuellt: |vwx| = |b epsilon c| = 2 <= 2
(3) erfuellt: fuer alle i >=0 ist das erzeugte Wort \n L, weil immer gleich viele b wie c dazu-/abgepumpt werden.
Nein, da m und n 0 sein koennen, womit bspw. fuer m=0 dein ‘b’ verschwindet und die Zerlegung folglich nicht machbar ist.
Davon abgesehen passt der letzte Fall nicht, da |vwx| <= p gelten muss. Mit folgender Wahl passts wieder:
u = a^j b^k
v = b
w = epsilon
x = c
y = c^(j+k)
Wir haben ja die Beweisrichtung „NPDA ⇒ CFG“ nicht durchgeführt, aber in der Vorlesung wurde das ja als Tatsache verkauft, trozdem muß man’s mir glauben 
. Einfacher wäre vielleicht die Angabe einer kf. Grammatik gewesen. Natürlich muß dann in jedem Fall auch der Hinweis auf das Pumping-Lemma kommen: Ist L kontextfrei, dann hat L die kontextfreie Pumpeigenschaft.