Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
klausurvorbereitungen theoinf
Thursday, February 26th 2004, 6:44pm
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, February 26th 2004, 7:54pm
Weiß ich nicht. Du solltest für die Klausur aber schon wissen, wie solche Automaten funktionieren und in der Lage sein, in Textform einen solchen Automaten anzugeben.
Quoted
Original von Krebskasper
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?
Der komplette Vorlesungsstoff ist klausurrelevant. Die Beweise muß man aber natürlich nicht auswendig kennen. Verstanden haben sollte man sie dennoch.
müssen wir das gesamte skript können, oder nur bis zu einem gewissen teil?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, February 26th 2004, 7:56pm
Du mußt noch dafür sorgen, daß im Fall xi <> 0 P1 nicht ausgeführt wird.
Original von Uprooter
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
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, February 26th 2004, 7:58pm
Anschaulich hat das n was mit der Anzahl der Zustände eines endlichen Automaten zu tun.
Original von Lucky
Mal ne wahrscheinlich triviale Frage. Beim Pumping Lemma muss man ja ein |uv|<=n wählen. Was ist das n und wie komme ich darauf? Muss ich da erst einen automaten kunstruieren um dann die Anzahl der Zustände zu erhalten, die ich dann für n einsetze???
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Thursday, February 26th 2004, 8:02pm
Auch höhere Semester werden Dir dazu nichts sagen können, da Herr Vollmer noch nicht sehr lange in Hannover ist und bisher nur die beiden im Netz veröffentlichten Klausuren geschrieben hat.
Original von Artemis
was mir eher aufgefallen ist:
(semi-)entscheidbarkeit, berechenbarkeit
kommt ja erst im multiple choice frageteil dran. it das wohl nur zufall? also ich finde das recht angenehm.
vielleicht weiss ja jemand aus nem hoeheren semester, ob man sihc darauf "verlassen kann", dass man fuer die ersten teilaufgaben nur mit Fragen bzgl. der Zuordnung/ Einordnung in die Chomskiy Hierarchie rechen muss?!
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, February 27th 2004, 11:07am
Dann hast Du das vermutlich falsch abgeschrieben. Die Epsilon-Sonderregel besagt: Kommt eine Produktion S -> eps vor, so darf S auf keiner rechten Seite einer Produktion vorkommen.
Original von NullAhnung
S->eps, X
X->aA, b, bX
A-> aX, bA, a
Warum ist diese Grammatik vom Typ 3 (regulär)?
Es kommt S-> eps und S-> X vor und dies ist laut Tabelle, die ich in der Übung mitgeschrieben hab, nicht erlaubt.
Friday, February 27th 2004, 1:23pm
Original von Joachim
Dann hast Du das vermutlich falsch abgeschrieben. Die Epsilon-Sonderregel besagt: Kommt eine Produktion S -> eps vor, so darf S auf keiner rechten Seite einer Produktion vorkommen.
Original von NullAhnung
S->eps, X
X->aA, b, bX
A-> aX, bA, a
Warum ist diese Grammatik vom Typ 3 (regulär)?
Es kommt S-> eps und S-> X vor und dies ist laut Tabelle, die ich in der Übung mitgeschrieben hab, nicht erlaubt.
Aber für mich heißt das dann nicht, dass ich dann Produktionen wie S-> X einführen darf. Und bei mir in der Tabelle steht das auch nur für kontextsensitiv und kontextfrei. Ist das denn richtig? Oder ist da bei mir ne Zeile verrutscht?
Friday, February 27th 2004, 2:22pm
This post has been edited 2 times, last edit by "Markus" (Feb 27th 2004, 2:25pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, February 27th 2004, 3:30pm
Achso, tschuldigung. Mein Fehler.
Original von NullAhnung
Original von Joachim
Dann hast Du das vermutlich falsch abgeschrieben. Die Epsilon-Sonderregel besagt: Kommt eine Produktion S -> eps vor, so darf S auf keiner rechten Seite einer Produktion vorkommen.
Original von NullAhnung
S->eps, X
X->aA, b, bX
A-> aX, bA, a
Warum ist diese Grammatik vom Typ 3 (regulär)?
Es kommt S-> eps und S-> X vor und dies ist laut Tabelle, die ich in der Übung mitgeschrieben hab, nicht erlaubt.
Ja das weiß ich wohl
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, February 27th 2004, 3:34pm
Man kann den Begriff der regulären Grammatik etwas weiter fassen als wir es in der Vorlesung getan haben. Zum Beispiel könnte man auf die Epsilon-Sonderregel verzichten und S -> X zulassen. Für die Klausur sind aber reguläre Grammatiken relevant, so wie sie in der Vorlesung definiert wurden.
Original von Markus
Ich könnte mir vorstellen, dass S->X auch bei reguären Sprachen machen kann, weil dieses durch obige Konstruktion eh umgangen werden kann.
