Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
klausurvorbereitungen theoinf
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 29th 2004, 1:04pm
Falls Du wissen willst, ob das eine kontextfreie Grammatik ist, so lautet die Antwort ja.
Quoted
Original von NullAhnung
Kann man für eine kontextfreie Sprache auch sowas erzeugen:
S->e, aXbX (?)
X-> ab, aXb
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 29th 2004, 1:05pm
Sofern in der Aufgabe nicht explizit steht, daß ein DEA konstruiert werden soll, ist das natürlich erlaubt.
Original von Uprooter
also darf man ruhig einen NEA erstellen wenn man zeigen soll, dass eine sprache regulär ist?
Sunday, February 29th 2004, 5:24pm
identisch?)und umgekehrt auch?)!
Sunday, February 29th 2004, 5:40pm
Original von Ernestinum[xic]
1.) was "zum Himmel" bedeutet dieses (mod 3)!?!? Habe es nach längerem Lesen immer noch net wirklich herausgefunden (z.B. 1. Aufgabe Klausur SS2003) und was bedeutet das gleichheitszeichen mit 3 Strichen
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 29th 2004, 7:29pm
Das wurde in der Übung erklärt.
Original von Ernestinum[xic]
1.) was "zum Himmel" bedeutet dieses (mod 3)!?!? Habe es nach längerem Lesen immer noch net wirklich herausgefunden (z.B. 1. Aufgabe Klausur SS2003) und was bedeutet das gleichheitszeichen mit 3 Strichen
Ja, das sind die Endzustände. Endzustände sind genau die Zustände, die einen der Endzustände des NEAs "enthalten".
2.) dann in Aufgabe 3. der klausur im ss2003 im DEA M' nach der Potenzmengenkonstruktion. Sind {{z2},{z0,z2},{z1,z2},{z0,z1,z2}} die Endzustände(was irgendwie in meinem jetzigen Verständnis bis jetzt nicht hineinpasst), wenn ja warum, und wenn nicht, was ist es dann und wie kommt man darauf?
Unendlich viele nicht, siehe Definition der Überführungsfunktion. Aber selbstverständlich kann (und muß!) von jedem Zustand aus für jedes Zeichen des Eingabealphabets eine Zustandsüberführung vorhanden sein.
3.) kann von einem Zustand zx eines DEA´s unendlich viele Überführungsaktionen ausgeführt werden und entgegenkommen, wenn sie natürlich nicht identisch sind. Sprich z0 mit Überführungsaktionen a zu z1 mit b zu z2 mit c zu z3.....!
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 29th 2004, 7:30pm
Eine kontextfreie Grammatik fällt mir dazu spontan auch nicht ein, aber man kann einen (deterministischen) Kellerautomaten konstruieren, der die Sprache erkennt. Grundprinzip: Zählen der Differenz zwischen "m"s und "n"s und genau dann akzeptieren, wenn diese 3 beträgt.
Original von Uprooter
Joachim, hast du vllt einen kleinen tipp, wie man den typ von dieser sprache rausfinden kann, denn das lemma für kontextfreie sprachen will nicht so recht, wenn ich das wort m^nn^nmmm betrachte und eine kontextfreie gramm ist auch nicht so einfach...
L={w | |w|m=|w|n+3}
This post has been edited 1 times, last edit by "Joachim" (Feb 29th 2004, 7:31pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 29th 2004, 9:51pm
Ich sehe in der Musterlösung der Klausur genau zwei Endzustände, das ist auch völlig korrekt so. Die weiteren möglichen (End-)Zustände wurden weggelassen, da sie ohnehin nicht erreichbar sind (das steht aber auch in der Musterlösung).
Original von Ernestinum[xic]
Habe aber da noch einen noch nicht verstandenen hacken, wenn man den NEA in einen DEA umwandelt und dann guckt wo überall der endzustand von NEA bei DEA enthalten ist und dann die Endzustände zählt, ergibt es doch 2 Endzustände, aber in der Klausur sind doch dann mehr als 2 Endzustände oder sehe ich das falsch?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Sunday, February 29th 2004, 11:08pm
Ein paar Begriffsklärungen:
Original von NullAhnung
Was ist eigentlich der Unterschied zwischen Sprachklasse und Typen (0,1,2,3) ??? Weil wenn es da keinen Unterschied gibt, wäre die niedrigste Sprachklasse ja immer die vom Typ 0, oder nicht?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, March 1st 2004, 3:07pm
Im Zusammenhang mit Berechenbarkeit geht man von deterministischen Turing-Maschinen aus. Siehe auch die Definition von "turing-berechenbar" im Skript.
Original von Uprooter
wenn man eine tm erstellen soll, die zB zu einem bandinhalt 1 addiert, muss diese tm deterministisch oder nichtdet. sein oder ist das egal?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, March 1st 2004, 4:12pm
Steht alles hier: http://www.thi.uni-hannover.de/lehre/ws03/gthi/aktuell/
Original von sos1981
Kann mir vielleicht jemand sagen, wo wir nun Theo.Inf. schreiben?
Es waren ja Audimax und B305 angekündigt; hängt vielleicht irgendwo ein Zettel aus, von dem ich nichts weiß, oder existiert hier eine allgemeine Informationslücke?
Monday, March 1st 2004, 4:13pm
Quelle: http://www.thi.uni-hannover.de/lehre/ws03/gthi/aktuell/
Informationen zur Klausur
* Termin: Di, 2.3.04, 13.15h-14.45h, Raum AM.
Bitte finden finden Sie sich bis 13h im Saal ein.
* Dauer der Klausur: 90 Minuten.
* Es sind keine Hilfsmittel zugelassen.
* Mitzubringen sind Studentenausweis, Lichtbildausweis (z.B. Personalausweis oder Reisepass) und Papier. Jede Aufgabe wird auf einem eigenen Blatt zu lösen sein.
This post has been edited 1 times, last edit by "thommyslaw" (Mar 1st 2004, 4:13pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, March 1st 2004, 4:14pm
Da bei einer solchen TM sowieso kein Eingabewort das Symbol # enthalten sollte, kann man es in diesem Fall auch weglassen.
Original von Uprooter
das eingabeaplhabet einer tm, die eine fkt berechnet muss ja stets {0,1,#} sein, ist das auch so wenn man nur eine einzige zahl berechnen will? ich meine # wird doch nur zur trennung der einzelnen eingabewerte benutzt, bei einer zahl ist das unnötig
