Pumping Lemma bei Reguläre Sprache?
Kann jemand mir bei diese Aufgabe helfen? Meine Proffesorin meinte:
für die Widerlegung, dass eine Sprache L regulär ist, wird ein Wort gewählt, aber für ALLE möglichen Zerlegungen mit w=xyz muss gezeigt werden, dass das Wort x(y^k)z nicht in L ist.
ZB beginnt w mit nicht-pumpbaren Zeichen, also die Sprache L ist so definiert, dann w=xxxa^p...
dann müssen alle Zerlegenungen betrachtet werden, das geht mit Fallunterscheidung
x= \epsilon
x=c^i für i=1,2,3
x=ccca^i
1 Antwort
Da müssen wir mal ein bisschen aufräumen... Um mit dem Pumping-Lemma zu zeigen, dass eine Sprache nicht regulär ist, machst du folgendes:
Sei n beliebig, aber fest [d.h. n ist eine Zahl, die du dir aber nicht aussuchen darfst - du musst den Beweis für ein ganz allgemeines n durchführen].
Du musst jetzt ein Wort w mit |w| ≥ n konstruieren, das in der Sprache liegt, bei dem aber kein Teilwort aus den ersten n Zeichen von w beliebig "aufgeblasen" werden kann, ohne dass das Ergebnis irgendwann die Sprache verlässt.
Klassisches Beispiel: L = {a^kb^k | k > 0}.
Wenn n eine beliebige Zahl ist, können wir w := a^nb^n wählen.
Offenbar gilt |w| = 2n ≥ n, d.h. unsere erste Bedingung ist schonmal erfüllt. Und wir können kein Teilwort der ersten n Zeichen beliebig aufblasen, ohne die Sprache zu verlassen: Die ersten n Zeichen bestehen nur aus a's. D.h. wenn wir irgendein nicht-triviales Teilwort daraus aufblasen, ändern wir die Anzahl der a's, nicht aber die Anzahl der b's. D.h. das Resultat wird a^mb^n sein, wobei m und n voneinander verschieden sind. Damit liegt das Resultat nicht mehr in L.
Soviel zur Idee. Der Formalismus von "Kein Teilwort der ersten n Zeichen kann beliebig aufgeblasen werden" ist nun eben dieser Kram mit der Zerlegung. Hier also die Argumentation nochmal in formaler:
Wenn w = xyz mit n ≥ |xy| und |y| > 0 ist, so besteht xy nur aus a's. Insbesondere existieren Zahlen k und j mit x = a^k und y = a^j und n ≥ k + j und j > 0. Ferner muss z "der Rest" des Wortes sein, also z = a^(n - k - j)b^n.
Jetzt blasen wir das Teilwort y auf. Formal heißt das, dass wir y in dem Wort durch y², y³ usw. ersetzen und schauen, ob wir irgendwann L verlassen (y^0 geht oft auch). D.h. wir untersuchen xz, xy²z, xy³z usw und hoffen, dass irgendwann ein Wort herauskommt, das nicht in der Sprache liegt.
Und in der Tat: Ersetzen wir y mit y^0, so erhalten wir das neue Wort
w' = xz
= a^k z
= a^k a^(n - k - j) b^n
= a^(n-j)b^n.
Weil j > 0 ist, ist n-j < n und somit liegt das Wort nicht in L, da die Anzahl der a's und der b's verschieden ist.
Nun zu deiner Aufgabe:
L_1 ist regulär, d.h. da kannst du es dir sparen das Pumping Lemma zu verwenden.
Bei L_2 hingegen kannst du dich durchaus mal selbst an einem Pumping-Lemma-Beweis probieren ;)