Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Das Pumping-Lemma ist schon der richtige Ansatz. Der Beweis wird dann wie üblich indirekt geführt. Man nimmt also an, die Sprache der Fibonacci-Wörter wäre kontextfrei. Dann gilt das Pumping-Lemma für kontextfreie Sprachen und es gibt eine entsprechende Zerlegung.Quoted
Original von Neo
http://www.thi.uni-hannover.de/lehre/ws0…ngsblatt_04.pdf
Hierzu hätte ich Mal eine Frage zur 3. Aufgabe:
Wie kann man zeigen, dass es keinen Kellerautomat gibt, der
die Fibonacci Wörter akzeptiert?
Evntl. mit Pumping Lemma (uvwxy-theorem)? Oder gibt es eine einfachere Lösung?
Quoted
Wie verhält sich der Term F_{i + 1} - F_i für wachsendes i? Wird diese Differenz kleiner, größer, bleibt sie gleich groß, oder ...?
This post has been edited 3 times, last edit by "Neo" (Feb 26th 2007, 1:42am)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Da solltest Du selber drüber nachdenken. Hat was mit dem "Aufpumpen" zu tun. Schau Dir mal hyperions Kommentar an.Quoted
Original von Neo
Aber was bringt das für meinen Beweis zu wissen, dass die Differenz immer
größer wird?
Nein. In dieser Aufgabe ist ein mathematischer Beweis gefragt. Und die vage Aussage "das geht halt nicht" ist alles andere als ein Beweis. Die menschliche Intuition liegt bei solchen Sachen gerne mal daneben. Deswegen ist eine unwiderlegbare Argumentation so wichtig.Quoted
Edit: Reicht es nicht einfach zu sagen, dass Kellerautomaten nicht zählen können?
This post has been edited 1 times, last edit by "Joachim" (Feb 26th 2007, 8:10am)
Quoted
Original von hyperion
Ich würde sagen, dass es das selbe ist wie mit L={w^k | k ist eine Quadratzahl}. Dies funktioniert auch nicht, da k nicht immer eine Quadratzahl ist. Daher würde ich annehmen, dass der Automat auch nicht immer auf die nächste Fibonacci Zahl kommt, sondern auch einmal zwischen zwei Zahlen und damit funktioniert es nicht mehr.
Quoted
Da solltest Du selber drüber nachdenken. Hat was mit dem "Aufpumpen" zu tun. Schau Dir mal hyperions Kommentar an.
This post has been edited 2 times, last edit by "Neo" (Feb 26th 2007, 4:31pm)
This post has been edited 1 times, last edit by "Neo" (Feb 26th 2007, 6:33pm)
Quoted
Original von Arne
Fibonacci-Zahlen sind natürliche Zahlen, das ist also nicht die Begründung. Vielleicht solltet ihr mal überlegen, inwieweit das Wachstum der Wortlängen mit dem Pumping Lemma machbar ist.
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
An der Formulierung dieser Aussage solltest Du noch etwas arbeiten. Ich ahne zwar, daß Du das richtige meinst, aber verständlich ist es bei weitem nicht.Quoted
Original von Neo
Es ist nicht machbar, da mit dem Pumping Lemma Wörter beliebiger Länge gemacht
werden können. Jedenfalls sind da auch Wörter drinnen, deren länge nicht einer
Fibonacci Zahl entspricht.
This post has been edited 2 times, last edit by "Neo" (Mar 1st 2007, 7:28pm)