 Pumping Lemma für reguläre Sprache |
Skrol
unregistriert
 |
|
| 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 16:36 |
|
|
Gast
unregistriert
|
|
| 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:23 |
|
|
Skrol
unregistriert
|
|
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:56 |
|
|
Skrol
unregistriert
|
|
Moment. Das kleinste k wäre doch dann 3 oder nicht?
|
|
|
07.11.2012 18:57 |
|
|
Skrol
unregistriert
|
|
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:04 |
|
|
Gast
unregistriert
|
|
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:32 |
|
|
Skrol
unregistriert
|
|
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:47 |
|
|
Skrol
unregistriert
|
|
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:52 |
|
|
Skrol
unregistriert
|
|
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 19:57 |
|
|
Gast
unregistriert
|
|
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:05 |
|
|
Skrol
unregistriert
|
|
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:10 |
|
|
Skrol
unregistriert
|
|
Also aba steht in der mitte und endet aba sind natürlich als 2 verschiedene Fälle anzusehen
|
|
|
07.11.2012 20:11 |
|
|
|
