Lutz Oberst wrote:
ich brauche i als Zahl ueberhaupt nicht. Das w_i ist das interessante. Nachdem ich 2i Zeichen gelesen habe ist der Keller leer, richtig.
Hinter dem (zu ratenden) fragelichen Partner muessen noch n-i (nicht 2i+j sorry) Zeichen kommen,
Hier benutzt du da i ja doch wieder. Das ist aber nicht mehr vorhanden.
aber (n-i), denn das ist doch das geratene j. (das j wird komplett neu geraten ohne vorheriges Wissen von i). Du benutzt das j dann zweimal um das w_(i+n) zu finden, denn der Abstand von w_(2i) zu w_(i+n) und von w_(i+n) zu w_(2n) ist gerade das j=n-i
Wenn also das j=n-i richtig geraten wurde, dann liegen gerade so viele Symbole wieder im Keller das man bis ans Ende vom Wort kommt.
Was passiert hier:
w = w_1 ... w_{n-3} w_{n-2} w_{n-1} w_{n}
w_i := w_{n-3}. Der Partner zu w_i wäre dann, wenn ich dich richtig verstanden habe, w_{n-1}, da die Anzahl der Symbole die zwischen w_{n-3} und w_{n-1} auf den Stack kommen, genau die Anzahl der Sybole ist, die zwischen w_{n-1} und dem Ende des Wortes vom Stack genommen werden.
Dann könnte auch w = abcdabcd ^ ^ akzeptiert werden.
Nein. Darum ueberspringe ich, wenn ich meine i gefunden zu haben, erst einmal noch einmal i Zeichen. (das hast du oben nicht gemacht.) Dadurch kann so etwas nicht passieren.
Idee bei a) ist, daß sich das Komplement forgendermaßen darstellen läßt: { L^m U^n L^k | m!=n } \cup { L^k U^m L^n | m!=n } \cup \ { \epsilon }
hmmm... L^n U^n L^n U^n ist da aber z.B. nicht drin....
Ahrg.
U^n w | w aus Sigma-Stern darfst Du auch nicht vergessen.
hab' keinen cvs-Zugang. (liegt dort auch was anderes als eure Loesungen?)
Nö, aber ich hab dir mal meine Lösung zugeschickt.
Thanx. (auch wenn sie dann wohl falsch ist ;-) Die Idee das Komplement jetzt als kontextfreie Teilmengen zu sehen scheint mir mittlerweile aber die beste Loesung zu sein.
