Pumping-Lemma

Marcus · Gast

Hallo,
es geht mir um das Pumping-Lemma für reguläre sprachen.
jede endliche sprache ist regulär (kann man ganz einfach sehen: für jeden buchstaben jedes einzelnen wortes wird eine (entsprechend reguläre)ableitungsregel aufgestellt).

ist nun eine sprache regulär, dann folgt für diese sprache, dass die eigenschaften des Pumping-Lemmas gelten müssen (umkehrung gilt nicht).

mein problem ist jetzt, dass man das Pumping-Lemma nicht auf endliche sprachen anwenden kann, weil man da nicht beliebig (=unendlich oft) pumpen kann, denn es gibt ja nur endlich viele wörter. (die aufzupumpende zeichenkette darf laut Lemma auch nicht das leere Wort sein).

ich kann in den vorraussetzungen des Pumping-Lemmas auch keine einschränkung auf unendliche sprachen finden, jetzt frage ich mich also: an welcher stelle wird der widerspruch aufgelöst?

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Das Pumping Lemma besagt, dass es für jede reguläre Sprache L eine Zahl k gibt, so dass für alle Wörter der Sprache, die größer oder gleich k sind eine Zerlegung existiert .... (usw)...

Jetzt benutzen wir einfach die Tatsache, dass All-Aussagen auf der leeren Menge immer wahr sind:

Sei L endlich, dann existiert ein

, so dass

(Es gibt also ein größtes Wort in L und k ist noch größer).

Dann gibt es natürlich keine Wörter, die länger sind als k (--> leere Menge). Damit ist das Pumping-Lemma trivialer weise erfüllt.

Der Sinn dahinter ist: Eine Sprache mit beliebig langen Wörtern muss eine gewisse Konstruktionsregel besitzen damit sie endlich beschreibbar ist. Eine endliche Sprache ist trivialerweise endlich beschreibbar.

Marcus · Gast

Hallo Tobias,
danke für deine schnelle antwort und sry wegen meiner verspäteten, hatte dieses WE leider keine zugangsmöglichkeit.

meine ausgangsfrage ist mit deinem post auch zufriedenstellend beantwortet worden, keine weiteren fragen diesbezüglich. vielen dank!

Gruß, Marcus.

Remington Steele · Anmeldungsdatum: 04.06.2005 Beiträge: 31

Sorry für die etwas banale Frage, aber mich würde jetzt 'mal dazu interessieren:

Man führt ja mit dem Pumping Lemma zum Widerspruch, d.h. zeigt dann, daß Pumping Lemma - Bedingung nicht gelten kann und eine Sprache damit nicht kontextfrei oder regulär ist.

Muß man das jetzt aber anhand von einer Zerlegung oder von allen Zerlegungen zeigen?

Also man wählt doch ein beliebiges Wort z und zeigt an diesem, daß irgendeine Pumping Lemma - Bedingung verletzt ist.

Aber irgendwas war doch, daß man für "alle" zeigen muß? grübelnd

(ist schon wieder so lange her und so ganz hatte ich das auch damals nicht verstanden - demnächst folgt die Nachklausur)

Danke schonmal...

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

Remington Steele · Anmeldungsdatum: 04.06.2005 Beiträge: 31

stimmt, muß größer als n sein bzw. k, wie Du es nennst.

Danke, das hat also schonmal etwas Licht in's Dunkel gebracht: "Dieses wort darf KEINE Zerlegung haben, die sich fachgerecht aufpumpen liesse."

Hm, aber das heißt schon, "richtig" aufpumpen, quasi gegen unendlich oder?

Oder würde auch ein Pumpen der größe i = 2 gelten?

Gast

Ich wuerde an deiner Stelle die Aussage mit Quantoren hinschreiben und dann verneinen und nach den Regeln der Praedikatenlogik umformen.

Falls dir das schwer faellt, solltest du es ueben. Das brauchst du eh.

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122

ED209

Remington Steele · Anmeldungsdatum: 04.06.2005 Beiträge: 31

ED209 · Anmeldungsdatum: 30.05.2005 Beiträge: 122