Ich kann's zumindest gerne versuchen [img]
http://www.fb18.de/gfx/25.gif[/img]
Also: Da am Anfang schon der Bezug zu S.83 hergestellt wurde meinst du mit "Widerspruch" wohl, warum man nicht mit dem Pumping-Lemma (für reguläre Sprachen) zeigen kann, dass die Sprache nicht regulär ist (in der Tat ist sie nicht regulär, mit dem Pumping Lemma kann man das aber nicht zeigen).
Wenn man versucht mit Hilfe des Pumping Lemmas nachzuweisen, dass L nicht regulär ist nimmt man zunächst an L wäre regulär und versucht dies dann zum Widerspruch zu führen. Das geht hier aber nicht, denn angenommen L sei regulär. Wir betrachten ein Wort z aus L.
Kommt in z kein c vor, so können wir z beliebig in uvw zerlegen (und daran herumpumpen) und erhalten nur immer Wörter, die wieder in L sind (da sie eben kein c enthalten).
Kommt in z ein c vor (zu Anfang), so gibt es stets eine Zerlegung z = uvw, so dass die Bedingungen des Pumping Lemmas erfüllt sind. Man wählt einfach u = \lambda, v = c und w als Suffix (d.h. w ist der Rest des Wortes z ohne das führende c). Nun gilt |uv| = 1 und man kann auch an v herumpumpen so viel man will, es entstehen stets Wörter die wieder in L sind. Daher ist auch diese Bedingung des Pumping-Lemmas erfüllt (z wird nämlich gleich viele a's und b's haben und nur weil wir an den vorderen c's herumpumpen ändert sich daran nichts).
Da also für jedes Wort aus L eine Zerlegung derart exisitert, wie vom Pumping-Lemma gefordert, kann man nicht mit Hilfe des Pumping-Lemmas folgern L wäre nicht regulär (man kann nun aber auch keinesfalls folgern, dass L regulär wäre!!)
Anmerkung: Das Pumping Lemma sagt, dass für eine reguläre Sprache eine Zahl n exisitert, so dass für jedes Wort (der Sprache) der Länge >= n (mindestens) eine (!!) Zerlegung existiert, so dass …..
Es reicht also nicht für ein Wort *eine* Zerlegung zu finden, so dass das Pumping Lemma nicht gilt, man muss dies für alle möglichen Zerlegungen tun (wenn man mit Hilfe des Pumping Lemmas zeigen will, dass eine Sprache nicht regulär ist). Umgekehrt heisst dass, wenn man für jedes Wort (irgend-)eine Zerlegung finden kann, so dass das Pumping-Lemma erfüllt ist, so hilft es einem nicht weiter. (Dies ist hier der Fall.)
Hoff es hilft [img]
http://www.fb18.de/gfx/23.gif[/img]
Cheers.
