Die letzten 10 Beiträge |
Skrol |
Also aba steht in der mitte und endet aba sind natürlich als 2 verschiedene Fälle anzusehen
|
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
|
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}* |
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
|
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? |
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
|
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 |
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
|
Skrol |
Moment. Das kleinste k wäre doch dann 3 oder nicht? |
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. |
Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |