Pumping Lemma für reguläre Sprache

Neue Frage »

07.11.2012, 16:36	Auf diesen Beitrag antworten »
Skrol	Pumping Lemma für reguläre Sprache Meine Frage: Hey Hallo Leute, Ich habe mal eine Frage zum Pumping Lemma. Also ich verstehe den Sinn hinter dem Pumping Lemma: Es geht darum zu zeigen, dass bestimmte Sprachen nicht regulär sind. Das macht man dann mithilfe einer Wortzerlegung in w=xyz. Findet man eine Zerlegung, die nicht von der Sprache akzeptiert wird, hat man gezeigt, dass die Sprache nicht regulär ist. So nun ist meine Aufgabe explizit anzugeben, wie die Sprache die alle Wörter mit "aba" (Das Alphabet besteht nur aus a´s und b´s) als Teilwort akzeptiert, pumpbar ist. Ich weiß hierbei dass es sich logischerweise um eine reguläre Sprache handelt, da ich einen Automaten für diese zeichnen kann. Es geht also in diesem Fall nicht darum zu zeigen, dass eine Sprache nicht regulär ist sondern nur anzugeben wie diese pumpbar ist, doch da scheitert es bei mir. Ich hoffe auf eure Hilfe Meine Ideen: Das einzige was ich bisher dazusteuern kann ist folgendes: Die Sprache akzeptiert alle Worte die "aba" als Teilwort enthalten. Das bedeutet es können unendliche viele as und bs vor dem Wort und nach dem Wort stehen. Wir haben also keine Schleife in der Mitte, sondern am Anfang und am Ende eine. Aber wie genau komme ich jetzt an eine Zerlegung, die die 3 Bedingungen erfüllt, welche das Pumping Lemma aufstellt.


07.11.2012, 18:23	Auf diesen Beitrag antworten »
Gast	RE: Pumping Lemma für reguläre Sprache Hi, bedenke, dass du NICHT eine Zerlegung suchst, sodass du durch die Schleife alle Wörter bilden kannst, sondern eine oder mehrere (es sind 2) mögliche Zerlegungen uvw für ein und das selbe k, die einfach nur die 3 Bedingungen erfüllen, sobald du ein Wort "reinschmeißt" Tipp: in einem Fall ist das "aba" im u , was ist also das kleinste k dass du wählen kannst? im anderen Fall im w viel erfolg!
07.11.2012, 18:56	Auf diesen Beitrag antworten »
Skrol	Hey, Danke schonmal für die Antwort Also ich verstehe schonmal nun was ich machen muss. Ich benötige also nicht eine Zerlegung für das Wort z sondern ZWEI. Beide Zerlegungen müssen für dasselbe k gelten und einmal nehme ich aba als u und einmal als w um die Schleifen dahinter und davor packen zu können? Nun ist mein Problem das k. Ich verstehe nicht wie man das bestimmt. k soll ja die maximale Länge des Wortes sein? oder vertue ich mich da? Desweitern ist die Bedingung gestellt dass der Betrag von \|uv\| <= k sein soll. Wie komme ich dann an ein bestimmtes k wenn u z.b. "aba" ist.
07.11.2012, 18:57	Auf diesen Beitrag antworten »
Skrol	Moment. Das kleinste k wäre doch dann 3 oder nicht?
Anzeige

07.11.2012, 19:04	Auf diesen Beitrag antworten »
Skrol	Also ich habe mir jetzt mal folgendes überlegt: Ich brauche 2 Zerlegungen für k=3. Da das kürzeste Wort aba sein kann. Meine erste Zerlegung ist: w=uvw wobei u=aba, v=(beliebige a´s oder b´s) w ist leer? Meine zweite Zerlegung ist: w=uvw wobei u ist leer, v=(beliebige a´s und b´s) und w ist aba. Ich vermute da ist noch was falsch aber das war jetzt mal ein versuch meinerseits
07.11.2012, 19:32	Auf diesen Beitrag antworten »
Gast	k ist so zu wählen, dass für alle wörter, deren länge>=k ist eine zerlegung existiert. wenn also u=aba ist, dann muss immer noch \|v\|>0 gelten, somit muss k mindestens =4 sein. deine zerlegungen sollten aber so funktionieren, außer im ersten fall muss v={a,b}{a,b}* , also mindestens ein buchstabe im zweiten fall darf w auch aba{a,b}* sein, denn hinter aba darf auch noch etwas stehn
07.11.2012, 19:47	Auf diesen Beitrag antworten »
Skrol	Okay also das k mindestens 4 sein muss ist mir jetzt klar. Ich hatte einfach die 3 Bedingung vergessen, dass das mittlere Zeichen nicht leer sein darf. Dennoch verstehe ich die die Zerlegungen nicht ganz: Wort= uvw Erste Zerlegung: u=aba, v={a,b}{a,b}, w=leer Zweite Zerlegung: u=leer, v={a,b}, w=aba{a,b}* Soweit alles richtig? Die Idee ist doch jetzt, dass ich mit diesen Zerlegungen alle Wörter größer gleich k abedecken kann oder? Wenn ja dann hab ichs jetzt verstanden und danke dir vielmals
07.11.2012, 19:52	Auf diesen Beitrag antworten »
Skrol	Moment eine Sache noch: Reicht nicht die 2 Zerlegung vollkomen aus? Mit der kann man doch alle Wörter abbilden oder irre ich mich da?
07.11.2012, 19:57	Auf diesen Beitrag antworten »
Skrol	Ah nein! Denn das mittlere Wort darf ja nicht leer sein. Richtig? das heißt die untere Zerlegung deckt nicht den Fall ab, dass das Wort mit aba anfängt. Dafür ist dann die erste Zerlegung. Richtig? Und tut mir leid das ich hier so rumspamme aber wenn ich etwas verstehe muss ich erst nen bisschen rumprobieren Aber tausend Dank für deine Hilfe
07.11.2012, 20:05	Auf diesen Beitrag antworten »
Gast	ah wir haben eine bedingung vergessen^^, \|uv\|<=k=4 erfordert bei jedem fall natürlich eine kleine anpassung aber sonst sollte es so richtig sein! Wort= uvw Erste Zerlegung: u=aba, v={a,b}, w={a,b}* Zweite Zerlegung: u=leer, v={a,b}, w={a,b}aba{a,b}
07.11.2012, 20:10	Auf diesen Beitrag antworten »
Skrol	Ah stimmt Soweit ich das sehe müssten deine Zerlegungen jetzt alle Fälle abdecken: Die erste Zerlegung deckt den Fall ab dass das Wort mit aba anfängt. Die zweite Zerlegung deckt die Fälle ab: Nur aba, aba steht in der Mitte und endet mit aba. Richtig? Danke dir
07.11.2012, 20:11	Auf diesen Beitrag antworten »
Skrol	Also aba steht in der mitte und endet aba sind natürlich als 2 verschiedene Fälle anzusehen

Neue Frage »

Antworten »

Pumping Lemma für reguläre Sprache

Verwandte Themen