klausurvorbereitungen theoinf - Page 5 - Grundlagen der Informatik - Fachrat Informatik

NullAhnung

Erfahrener Schreiberling

Posts: 332

Date of registration: Apr 28th 2003

81

Wednesday, February 25th 2004, 11:52am

Kann man einfach bei z.B. L3 w und z unbeachtet lassen? Also ein Wort nehmen wie t=x^3n y^n ????

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

82

Wednesday, February 25th 2004, 11:57am

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 ????

L2 meinst Du wahrscheinlich.

Man kann für das Pumping Lemma jedes beliebige Wort aus der Sprache nehmen, das mindestens die Länge n hat. Bringt in diesem Fall aber nix, da L2 regulär ist.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

Markus

the one and only Unterstrich!

Posts: 2,571

Date of registration: Oct 9th 2003

83

Wednesday, February 25th 2004, 12:24pm

hat jemand von euch zufällig das Scripzvontheo inf und kann mir das schicken?

Auf der HP steht das zwar zum Download, allerdings muss das von der Uni aus geschehen (warum /(!!§$!% auch immer).

Charmant sein? Hab ich längst aufgegeben. Glaubt mir doch eh keiner...

Go to the top of the page

Arne

ThI

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

84

Wednesday, February 25th 2004, 1:11pm

log dich halt per vpn oder über ssh aufn stud ein und saugs dir von dort per wget

"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Go to the top of the page

NullAhnung

Erfahrener Schreiberling

Posts: 332

Date of registration: Apr 28th 2003

85

Wednesday, February 25th 2004, 1:47pm

Wäre nett, wenn mir jemand den dritten Teil zuschicken könnte. Danke schonmal.

Go to the top of the page

Torrero

Senior Schreiberling

Posts: 854

Date of registration: Oct 16th 2003

Location: Laatzen

Occupation: Angewandte Informatik

86

Wednesday, February 25th 2004, 2:28pm

Ich könnte es dir schicken, nur leider gibst du hier keine EMAIL-Adresse an wohin man es schicken könnte.

Go to the top of the page

Uprooter

Junior Schreiberling

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

87

Wednesday, February 25th 2004, 6:29pm

gibt es denn irgendwo klausuren von den letzten zu finden?

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

88

Wednesday, February 25th 2004, 6:35pm

Quoted

Original von Uprooter
gibt es denn irgendwo klausuren von den letzten zu finden?

Wer suchet, der findet:

http://www.thi.uni-hannover.de/lehre/ws02/gthi/aktuell/
http://www.thi.uni-hannover.de/lehre/ss03/gthi/

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

Uprooter

Junior Schreiberling

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

89

Wednesday, February 25th 2004, 6:48pm

dankeschön

zwei kleine frage: wie kann nachweisen, dass eine sprache nicht kontextsensetiv ist? gibt es dazu überhaupt ein verfahren?

gibt es ein gezielteres verfahren zur erstellung von 2 sprachen, deren durchschnitt zb nicht kontextfrei ist, als nur rumzuprobieren?

Go to the top of the page

iriania

Junior Schreiberling

Posts: 222

Date of registration: Nov 24th 2003

Location: Waqwaq

Occupation: Wie? Ich studiere? seit wann denn?

90

Wednesday, February 25th 2004, 9:57pm

Wo findet man die alten Klausuren & ihre Musterlösungen?

Die lösungen zu den Übungsaufgaben finde ich auch nirgends (auf der theoinf Webseite stehen nur die Musterlösungen 2 und 11)

...und sie dreht sich doch!

Go to the top of the page

Benjamin

Segelnder Alter Hase

Posts: 3,827

Date of registration: Oct 1st 2002

Location: Region Hannover

Occupation: Alumni

91

Wednesday, February 25th 2004, 10:08pm

Quoted

Original von Joachim

Quoted

Original von Uprooter
gibt es denn irgendwo klausuren von den letzten zu finden?

Wer suchet, der findet:

http://www.thi.uni-hannover.de/lehre/ws02/gthi/aktuell/
http://www.thi.uni-hannover.de/lehre/ss03/gthi/

Wer suchet, der findet...

für die alten Klausuren + Musterlösungen schau mal 2 bis 3 Posts nach oben

Es gibt nur eine bessere Sache als auf dem Wasser zu sein: Noch mehr auf dem Wasser sein.

Go to the top of the page

NullAhnung

Erfahrener Schreiberling

Posts: 332

Date of registration: Apr 28th 2003

92

Thursday, February 26th 2004, 8:27am

Quoted

Original von Torrero
Ich könnte es dir schicken, nur leider gibst du hier keine EMAIL-Adresse an wohin man es schicken könnte.

Hab ich jetzt schon von wem anders. Trotzdem danke

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

93

Thursday, February 26th 2004, 12:41pm

Quoted

Original von Uprooter
zwei kleine frage: wie kann nachweisen, dass eine sprache nicht kontextsensetiv ist? gibt es dazu überhaupt ein verfahren?

Sprachen, die nicht entscheidbar sind, sind auch nicht kontextsensitiv.

Quoted

gibt es ein gezielteres verfahren zur erstellung von 2 sprachen, deren durchschnitt zb nicht kontextfrei ist, als nur rumzuprobieren?

Leider nein.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

Go to the top of the page

Uprooter

Junior Schreiberling

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

94

Thursday, February 26th 2004, 12:42pm

hehe, bis zur entscheidbarkeit bin ich noch nicht vorgedrungen

Go to the top of the page

Uprooter

Junior Schreiberling

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

95

Thursday, February 26th 2004, 2:04pm

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, 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.

Go to the top of the page

Joachim

Guru

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

96

Thursday, February 26th 2004, 2:55pm

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

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

, 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.

Ja, gute Idee. So könnte man es machen. Man müßte nur begründen, warum es keine solchen Fibonacci-Zahlen gibt.

Ich dachte aber an einen anderen Lösungsweg:

Wenn 0^k eine Fibonacci-Zahl ist, dann ist nach Pumping-Lemma auch 0^{k + |v| + |x|} eine solche. Und 0^{k + 2 * |v| + 2 * |x|}, 0^{k + 3 * |v| + 3* |x|} usw. auch.

Das bedeutet dann aber, daß es eine unendliche Folge von Fibonacci-Zahlen gibt, die jeweils zum Nachbarn den selben Abstand haben. Da der Abstand zwischen zwei benachbarten Fibonacci-Zahlen aber immer größer wird, kann das nicht richtig sein.

Daher ist die Annahme falsch und die Sprache nicht kontextfrei.

The purpose of computing is insight, not numbers.

– Richard Hamming, 1962

This post has been edited 2 times, last edit by "Joachim" (Feb 26th 2004, 2:56pm)

Go to the top of the page

Krebskasper

Praktikant

Posts: 24

Date of registration: Dec 18th 2003

Location: Mutterns Bauch

Occupation: Mathe / Inf

97

Thursday, February 26th 2004, 5:00pm

also,

ich habe mir die alten klausuren angeguckt und bemerkt, dass da ja nichts über kellerautomaten und turingmaschinen dran kam.

frage: ist das immer so, weil das zu zeitaufwendig wäre? oder ist das schlichtweg ein zufall?

müssen wir das gesamte skript können, oder nur bis zu einem gewissen teil?

ich bedanke mich recht herzlich schon im voraus für die zahlreichen antworten.

Go to the top of the page

Uprooter

Junior Schreiberling

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

98

Thursday, February 26th 2004, 5:24pm

ich denk mal alles was in den übungen angerissen wurde könnte vorkommen

Go to the top of the page

Uprooter

Junior Schreiberling

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

99

Thursday, February 26th 2004, 5:36pm

würde das für "IF xi=0 THEN P1 ELSE P2" gehen?:
=> xk:=1
LOOP xi DO xj:=1 END;
LOOP xj DO P2 END;
LOOP xk DO P1 END

This post has been edited 1 times, last edit by "Uprooter" (Feb 26th 2004, 5:36pm)

Go to the top of the page

EnteTaylor

Trainee

Posts: 111

Date of registration: Oct 24th 2003

Location: Göttingen

Occupation: weil's toll is

100

Thursday, February 26th 2004, 6:06pm

TMs Kellerautomaten und L6

Ich nehm auch an, dass kellerautomaten und Turingmaschinen nicht drankommen werden, da Turingmaschinen ja für alle Sprachen da sind, wenn ich das richtig verstanden hab. Daher kann man damit ja auch nicht belegen ob eine sprache z.b kontextfrei oder regulär ist. Und anstelle von nem Kellerautomaten kann man ja auch ne kontextfreie Grammatik angeben, was wie ich finde viel einfacher ist. Daher heißt es für mich zumindest in bezug auf kellerautomaten: Mut zur Lücke!

übrigens zu L6:
kann das so gehn, wenn man schon mit Pumping Lemma den Beweis gemacht hat, dass L6 nicht regulär ist?

S->mAX S-> nAY S->mmm
A->mAX A->nAY
X->n
Y->m
A->mmm A->mnmm A->mmnm

Meine Gedächtnisprotokolle: www.janwy.de

Go to the top of the page

Fachrat Informatik - Forum

Quoted

Quoted

Quoted

Quoted

Quoted

Quoted

Quoted

Quoted

Quoted

TMs Kellerautomaten und L6