Pumping-Lemma - Seite 2

Remington Steele · Anmeldungsdatum: 04.06.2005 Beiträge: 31

Glaube mir - ist aber so smile

. Wenn man manchmal in Skripte anderer Unis 'reinschaut wird einem regelrecht unheimlich, wie anders das dort aufgezogen ist grübelnd

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Man braucht nicht unbedingt eine ausführliche Einführung in die Prädikatenlogik um das Pumpinglemma zu verstehen. Ich finde es macht einen überheblichen Eindruck andere nur auf "Lücken" aufmerksam zu machen ohne sachbezogen dem Problem dienlich zu sein.

Das Pumpinglemma fordert:

Es existiert ein k, so dass für alle Wörter größer als k spezielle Zerlegungsregeln gelten.

Dann ist die Verneinung davon:

Zu jedem k gibt es ein Wort größer als k, das nicht den Zerlegungsregeln entspricht.

Es reicht also nicht zu zeigen, dass es zu einem gegebenen k ein "falsches" Wort gibt sondern du musst zeigen, dass du einen "Verbrecher" zu jedem beliebigen k findest.

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Remington Steele · Anmeldungsdatum: 04.06.2005 Beiträge: 31

Danke ED..., die Zeit ist leider nur sehr knapp und der Stoff sehr groß, daher wird es schwer, sich jetzt noch in diese Präd.logik einzuarbeiten.

@Tobias: grübelnd

Habe ich das denn nicht richtig verstanden:

Sagen wir, man soll zeigen, daß a^n b^2n c^n nicht kontextfrei ist.

Sei die Bedingung |z| >= |n| die entsprechende Bedingung aus dem Pumping Lemma (z ist das Wort)

Also ich sage "sei z = a^n b^2n c^n". Dann ex. laut PL eine Zerlegung ... bla.... wegen Bedingung soundso und soundso kann - bla - nur aus - bla bestehen.
Bei Aufpumpen muß das und das sein, ist aber nicht erfüllt --> PL verletzt --> nicht kontextfrei.

Also ich dachte, ich muß mir ein Wort wählen und dann halt für größere (alle?? Ggf. wie?)Zerlegungen zeigen, daß es nicht kontextfrei (bzw. regulär in anderem Fall) ist?
Hilfe

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Das Problem ist dass DU dir das z nicht aussuchen kannst. Denn die Bedingung darf fuer kein z gelten.

Das heisst du musst bei zu jedem gegebenen z ein Wort a^n b^2n c^n finden, das sich nicht aufpumpen laesst.
Da du nur EIN Wort brauchst kannst du fuer das n auch etwas einsetzen. Zum Beispiel z :)

Denn fuer jedes gewaehlte z >1 gilt: |a^z b^2z c^z| ist groesser als z.
Fuer dieses Wort muesstest du jetzt beweisen, dass es KEINE Zerlegung gibt fuer die fuer EINE Zerlegung nicht gilt, dass u v^i w ein Element von a^n b^2n c^n ist.