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.
L_2b = { 
^ k a^j b^ĵ 
^ k | k,j >= 0} vs. L_2c = { a ^ k ^j b ^k ^j | k,j >= 0 }
Alte Thinf Aufgabe überschrieben mit “II-2”…
zu Zeigen war…
a) L_2b = { ^ k a^j b^j ^ k | k,j >= 0} besitzt k.f. P. E.
Hier würde es ja ausreichen zu begründen, dass es einen entsprechenden PDA gibt, der Wörter der Sprache L_2b akzeptiert.
Idee hierbei es gibt zweiverschiedene Tellersorten. grüne, rote Teller.
Bei jedem freundlichen Smiley werden Flache grüne Teller auf den Stapel gelegt, dann kommt ein roter Teller mit Beginn des ersten a, für jedes weitere a wird wieder ein grüner Teller auf den Stapel gelegt, beim Abräumen analog, für jedes b wird ein …
Kann es dieses groß Gamma und klein delta geben?
b) L_2c = { a ^ k ^j b ^k ^j | k,j >= 0 } besitzt k.f. P.E.
Problem: Wegen FIFO-Prinzip eines Kellerspeichers / automaton, kann es einen PDA, der Sprache L_2c akzeptiert, nicht geben.
Wir wissen leider aber dennoch nichts über die k.f. P.E. … => direktes Anwenden der Definition k.f. P.E. nicht
Aufgrund von |vwx| <= n wissen wir, dass max. zwei verschiedene aufeinanderfolgende Zeichen des Eingabe-Alphabets Groß Sigma (weg)gepumpt werden können. Ferner aufgrund von vx ≠ ε mind. ein Zeichen. D.h. es lässt sich leicht für verschiedene Zerlegungen ein i=0 finden,so dass uwy nicht Teil der Sprache sein kann. Entweder ich möchte a’s und b’s gleichzeitig pumpen, also auf v und x verteilen oder gleichzeitig Smileys pumpen. Leider geht das nicht, weil mind. n Zeichen dazwischen liegen und somit der “String” vwx >= n wird… q.e.d
@Prof. Wanka aka rwanka: Beweis aus b) ausreichend für 80% der Punkte?
Heutzutage steht an solchen Stellen (schon seit Jahren) zusätzlich durch Anwendung der Definition. 
Ja, und noch einfacher wäre es, eine kf. Grammatik anzugeben. Erinnern Sie sich, was ich über den Zusammenhang kontextfreier Sprachen mit korrekten Klammerfolgen gesagt habe? Hier haben Sie sowas wie die korrekte Klammerungen. Deswegen habe ich die Exponenten mal farbig gemacht.
Jedenfalls wollte ich, daß tatsächlich die Pumpeigenschaft direkt nachgewiesen wird und nicht über den Umweg über einen NPDA oder eine kf. Grammatik. Das ist ja inzwischen in den Formulierungen geheilt.
Hier sehen Sie „unkorrekte“ Klammerungen. Daher gilt für die Intuition, daß L[sub]2c[/sub] die k.f. P.E. nicht haben kann. Ein Beweis ist das nicht. Da muß man mal wieder das Quantoren-Geraffel anwenden. 
Vielleicht etwas haarspalterisch, aber ich würde sagen, z besteht aus vier Blöcken jeweils aus a’s, 
's, b’s, 
's, und vwx kann höchstens zwei aufeinanderfolgende Blöcke treffen …
Sie finden ein i=0? So kann man nicht formulieren. Warum weichen Sie denn vom Quantoren-ins-Deutsche-Übersetzen-Schema ab? Sagen Sie doch
Hier wird’s unscharf. i=0 nimmt aus den
-Blöcken oder- und b-Blöcken oder-BlöckenSach ich getz nix zu. Gut schaut’s ingesamt aber aus.
MfG
Rolf Wanka