Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
L2 meinst Du wahrscheinlich.Quoted
Original von NullAhnung
Kann man einfach bei z.B. L3 w und z unbeachtet lassen? Also ein Wort nehmen wie t=x^3n y^n ????
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Wer suchet, der findet:Quoted
Original von Uprooter
gibt es denn irgendwo klausuren von den letzten zu finden?
Junior Schreiberling
Date of registration: Nov 24th 2003
Location: Waqwaq
Occupation: Wie? Ich studiere? seit wann denn?
Quoted
Original von Joachim
Wer suchet, der findet:Quoted
Original von Uprooter
gibt es denn irgendwo klausuren von den letzten zu finden?
http://www.thi.uni-hannover.de/lehre/ws02/gthi/aktuell/
http://www.thi.uni-hannover.de/lehre/ss03/gthi/
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sprachen, die nicht entscheidbar sind, sind auch nicht kontextsensitiv.Quoted
Original von Uprooter
zwei kleine frage: wie kann nachweisen, dass eine sprache nicht kontextsensetiv ist? gibt es dazu überhaupt ein verfahren?
Leider nein.Quoted
gibt es ein gezielteres verfahren zur erstellung von 2 sprachen, deren durchschnitt zb nicht kontextfrei ist, als nur rumzuprobieren?
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
n muß keine Fibonacci-Zahl sein. Du mußt also die die nächste Fibonacci-Zahl betrachten, die größer gleich n ist. Wenn Du diese k nennst, dann mußt Du vom Wort 0^k ausgehen. Und da k >= n ist, läßt sich das Pumping Lemma auch auf dieses Wort anwenden.Quoted
Original von Uprooter
ich komme irgendwie mit dem fibonacci-teil nicht wirklich weiter, ich habe folgende überlegungen bisher:
die ersten fibonacci zahlen lauten 0 1 1 2 3 5 8 13...
ich betrachte speziell das wort 0^n, |0^n|=n
Ja, gute Idee. So könnte man es machen. Man müßte nur begründen, warum es keine solchen Fibonacci-Zahlen gibt.Quoted
, dann gilt n=|uvwxy|<|uv^2wx^2y|=<n +n=2n, wenn man also v und x quadriert, dann kann die länge max doppelt so gross werden. und ich denke es gibt keine fibonacci-zahl, die man mit 2 multiplizieren könnte, dann eine andere fibonacci-zahl ergibt, ausser! die ersten 3, 0*2 zB ergibt wieder null oder 1*2=2 und das sind fibonacci-zahlen, kann man diese irgendwie ausschliessen und dann sagen, dass es für die restlichen aber gilt? bin mir gar nicht sicher, ob es dann ein beweis ist.
This post has been edited 2 times, last edit by "Joachim" (Feb 26th 2004, 2:56pm)