Hi, ich hab diese Aufgabe gefunden und frage mich wie man da rangeht:

beweisen sie mit dem Pumping Lemma:
L1 = {w element {a,b}* | w enthält doppelt so viele a's wie b's}
ist nicht regulär

da ich hier ja irgendwie keine Reihenfolge von a und b habe fällt mir hier das Anwenden des pumping-Lemma recht schwer.

Kann man diese Menge einfach mit L3 = {a}*{b}* schneiden?

Dann würde sich ja a^2n b^n ergeben. Aufgrund der Abschlußeigenschaften muss nun a^2n b^n regulär sein, wenn L1 regulär war (L3 is ja auch regulär).

Wenn ich nun das pumping-lemma auf a^2n b^n anwende und einen Wiederspruch finde, dann kann doch auch L1 nicht regulär gewesen sein und ich habe die Aufgabe beantwortet.

Ist das ein kluger Weg? Oder hab ich da einen Denkfehlerß oder wie würde man sonst vorgehen.

Kann man diese Menge einfach mit L3 = {a}*{b}* schneiden?

Dann würde sich ja a^2n b^n ergeben. Aufgrund der Abschlußeigenschaften muss nun a^2n b^n regulär sein, wenn L1 regulär war (L3 is ja auch regulär).

Wenn ich nun das pumping-lemma auf a^2n b^n anwende und einen Wiederspruch finde, dann kann doch auch L1 nicht regulär gewesen sein und ich habe die Aufgabe beantwortet.

Ist das ein kluger Weg?

Ja, das geht so in Ordnung, aber wenn Sie direkt aus [img]http://mokrates.de/cgi-bin/texstring?%20L_%7B1%7D[/img] das Wort [img]http://mokrates.de/cgi-bin/texstring?z%3Da%5E%7B2n%7Db%5En[/img] wählen, wobei n die Konstante aus dem uvw-Theorem ist, so erzeugt jedes rauf- oder runter Pumpen Wörter, die nicht mehr in [img]http://mokrates.de/cgi-bin/texstring?%20%20L_%7B1%7D[/img] sind. Insgesamt ist das also kürzer!

PS. es heißt hier, wie so oft betont, stets "Wörter" nicht "Worte"!

Deine Idee ist doch gut. Ablauf:

1) Annahme L1 sei regulär.
2) L2 := {a}*{b}* ist regulär, da die regulären Sprachen unter Durchschnitt abgeschlossen sind ist auch L3 := L1 cap L2 regulär.
3) Zeige, dass L3 nicht regulär ist (bspw. mit dem Pumping Lemma.

Folglich muss die Annahme falsch gewesen sein, d.h. L1 ist nicht regulär.

—

Aber du kannst L1 doch auch direkt mit dem Pumping Lemma "angreifen": Annahme L1 sei regulär. Dann gilt die Aussage des Pumping Lemmas; sei n die Zahl aus dem Pumping Lemma, betrachte das Wort z = a^2n b^n \in L1. Man kann zeigen, dass jede Zerlegung von z in uvw zu einem Widerspruch führt (was relativ schnell geht, da wegen |uv| <= n und |v| >= 1, v aus einem oder mehr a's bestehen muss. Einmal pumpen schon ist u v^2 w nicht mehr in L1.)

[Die Aussage des Pumping Lemmas ist, dass wenn eine Sprache regulär ist eine natürliche Zahl n existiert, so dass für alle Wörter der Länge >= n eine (mindestens eine) Zerlegung in uvw exisitert mit den drei Eigenschaften i)… ii)… ii)…

Für einen Widerspruch muss man also zeigen, dass für ein (mindestens ein) Wort der Länge >= n überhaupt keine Zerlegung in uvw zum Erfolg führt, d.h. alle Zerlegungen führen zum Widerspruch.]

Hoff' es hilft [img]http://www.fb18.de/gfx/22.gif[/img]

Cheers,
Frank

P.S. Theorinix war schneller, aber ich lösch das jetzt mal nicht, vielleicht hilft's ja wirklich noch beim Verständnis ein Stück [img]http://www.fb18.de/gfx/25.gif[/img]

Achso ich darf also direkt das Wort nehmen. Das war mir nicht ganz klar, vielen Dank an beide!

Hat mir sehr geholfen

Wenn man das uwv Theorem nutzt, ein Zerlegung findet und uv^{i}w \not\subseteq R, dann kann man doch aufhören?
Oder müssen alle Zerlegungen getestet werden?

Nein, es müssen alle möglichen Zerlegungen getestet werden. Das Pumping-Lemma sagt doch, dass es (mindestens) EINE Zerlegung gibt, für die die Folgerungen zutreffen. Um nun das Gegenteil zu zeigen, musst beweisen, dass es KEINE Zerlegung gibt, für die das gilt. D.h. du musst zeigen, dass für ALLE Zerlegungen die Folgerungen NICHT gelten.