Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
GTI, WS 2006/2007, Übung4
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 25th 2007, 8:17pm
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?
Monday, February 26th 2007, 1:35am
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)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, February 26th 2007, 8:09am
Da solltest Du selber drüber nachdenken.
Original von Neo
Aber was bringt das für meinen Beweis zu wissen, dass die Differenz immer
größer wird?
Hat was mit dem "Aufpumpen" zu tun. Schau Dir mal hyperions Kommentar an.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.
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)
Monday, February 26th 2007, 4:21pm
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.
Monday, February 26th 2007, 4:27pm
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)
Wednesday, February 28th 2007, 5:07pm
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.
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, March 1st 2007, 10:51am
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.
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.
Thursday, March 1st 2007, 8:48pm
Wenn Du darüber keinen Weg findest, musst Du Dir was anderes überlegen. Vielleicht findest Du ja eine andere Argumentation, weshalb das nicht klappen kann. 
