Ich werde bei dem Pummpin' Lemma Theorem aus einem Schritt nicht so ganz schlau.
Und zwar…man sucht ja ein Wort, für dass die festgelegten Bedingungen nicht gelten…

nehmen wir z.B. L:={wcw^rev | w € {a,b}* }
=> z = a^n c a^n

=> Bedingung |uv| <= n ist erfüllt
=> Bed. v >= 1 stimmt auch.

Dann teilt er dass hier in die einzelnen u,v,w Teile auf…:
u = a^k v = a^l w = a^(n-k-l) c a^n

daraus schließt er dann dass für i = 0 uv^iw nicht element L ist.und folglich L nicht regulär ist.

Wie genau kommt er darauf, dass i = 0 nicht € L ist, bzw. müsste dieses kriterium nicht bei egal welchem wort IMMER true zurückgeben, und daher jede Sprache nicht regulär sein?

P.S. gibt es nicht irgeneinen Tipp, wie man möglichst schnell worte findet, die die die notwendigen Kriterien zur Bestimmung nicht gelten?

Danke!

P.P.S Sorry LaTeX is nich mein fach. wenn jemand will kann er ja die Formeln "umLaTeXen"

nehmen wir z.B. L:={wcw^rev | w € {a,b}* }
=> z = a^n c a^n

=> Bedingung |uv| <= n ist erfüllt
=> Bed. v >= 1 stimmt auch.

hier hast du doch u,v,w noch gar nicht gewählt,
wieso sollten die Bedingungen schon erfüllt sein?

|z| >= n ist erfüllt

Dann teilt er dass hier in die einzelnen u,v,w Teile auf…:
u = a^k v = a^l w = a^(n-k-l) c a^n

hier sind die beiden anderen Bedingungen erfüllt
(nicht vergessen: l > 1, k <= n-l),
wichtig ist auch, dass das ALLE möglichen Zerlegungen sind

———

auf jeden Fall gilt für i=0 für alle Zerlegungen:
u v^i w = u v^0 w = a^(n-l) c a^n

und das ist nicht in L da n-l != n da l > 0

dieses Kriterium gilt also nicht immer, sondern nur wenn man es konkret zeigen kann wie oben,


———–

Gegenbeispiel:
L2 = {a^x c a^y | mit x <= y}

diese ist auch nicht regulär,
aber mit dem gewählten Wort a^n c a^n wird man für den Fall i=0
(a^(n-l) c a^n ) hier tatsächlich immer Wörter aus L2 bekommen also immer TRUE,
man muss dann mal was anderes probieren,

————

wie man darauf kommt was funktioniert?, wie man das richtige Wort wählt?
tja, entweder man sieht solche Dinge (was mit etwas überlegen machbar ist)
oder Übung, Übung, Übung..,
(da gibts aber auch wichtigere Aufgaben die man können sollte und die einfacher zu lernen sind)

meistens reichen Wörter mit ^n ^2n oder so,
bei L2 käme man mit a^n c a^n auch zum Ergebnis,
nur nicht mit i=0 danach ;),
wenn es mal nicht klappt dann sollte man beim Versuch mit einem
Standardwort auch erkennen woran es fehlt
(bei L3 = {a^x b^y c^z a^z} kommt man mit a^n b^n c^n a^n nicht weit ;) )

Hi

ich hab auch nochmal eine frage zum pumping-lemma.
dieses n darf ich ja beliebig wählen, es muss nur |z|>= n gelten. dann darf ich doch auch n = 1 wählen oder?

denn mit n=1 kommt ja recht einfach zu einem widerspruch, wenn die menge nicht regulär ist.

Wenn du zeigen willst, dass eine Menge nicht regulär ist, dann darfst du das n nicht einfach belibig wählen. Das Pumping-Lemma sagt ja nur aus, _dass_ es ein solches n gibt, aber nicht _welches_. Daher musst du beim Beweis das n variabel lassen (siehe Beispiel in Script und Folien) und somit zeigen, dass es für alle natürlichen Zahlen zu einem Widerspruch führt.

Daher musst du beim Beweis das n variabel lassen (siehe Beispiel in Script und Folien) und somit zeigen, dass es für alle natürlichen Zahlen zu einem Widerspruch führt.

Nicht ganz. Man nimmt an eine Menge sei regulär. Dann gilt das Pumping Lemma und dies sagt, dass es eine (!) Zahl n gibt, so dass fuer alle Wörter der Menge, deren Länge gleich oder grösser n ist eine Zerlegung z = uvw existiert mit i) … ii) … iii)…

Man wählt also weder das n noch muss man für alle n etwas zeigen. Ist die Menge regulär - d.h. gilt das Pumping Lemma (und dies ist die Annahme die man versucht zum Widerspruch zu führen) -, so gibt es eine Zahl n (die Pumping-Zahl) mit obigen Eigenschaften.

Man muss nun noch ein Wort der Länge grösser-gleich n finden so dass keine (!!) Zerlegung die drei Eigenschaften erfüllt.

Cheers.