Fachrat Informatik - Forum

Hi,
ich wurde heute in "Formale Sprachen" geprüft (bei Arne Meyer) und solange es noch halbwegs frisch ist fass ich hier mal kurz zusammen. Es wurde (wie das wohl meistens üblich ist) vor allem in die Breite geprüft. Beweise detailliert aufschreiben musste ich eher nicht. Es kam bis auf 2DEAs und Mealy/Moore-Automaten alles ein bisschen dran:
Abschlusseigenschaften der verschiedenen Sprach-Klassen (REG, DCFL, CFL, CSL, Typ 0-Sprachen) - letztlich einfach Vereinigung, Schnitt und Komplement für alle Klassen, syntaktischer Monoid (wobei ich das erst vorgeschlagen habe), Myhill-Nerode, Immerman & Szelepczenyi (aber nur Resultat, nicht Beweis). Dann noch Erzeugung des Minimalautomaten aus nem gegebenen DEA (mit Laufzeit) ohne Beispiel, Erklärung und Laufzeit reichten. Insgesamt reichten meist relativ grobe Erläuterungen. Entscheidbarkeit kam auch noch kurz: Schnittproblem für CFLs (bzw DCFLs), wobei ich da den Beweis doch nicht mehr erläutern sollte, da reichte, dass ich von PCP reduzieren wollte. Dafür dann noch die Reduktion aufs Äquivalenzproblem für CFLs (und auch die Frage, wie es da mit DCFLs aussieht). Insgesamt (da fällt mir spontan eben das Äquivalenzproblem für DCFL sowie Satz von Immerman und Szelepczenyi ein) kamen auch Sachen dran, die in der Vorlesung nicht bewiesen wurden (bzw. im Falle von Immerman und Sz. der Beweis nicht prüfungsrelevant war) - aber da reichte eben dann auch die Aussage ohne Beweis.
Achja, es wurde auch noch nach Entscheidungsalgorithmen für das Wortproblem für die verschiedenen Typen gefragt, also alle Klassen von oben. DCFL hatten wir glaube ich nicht explizit, geht aber wegen Determinismus linear.

Gruß, Anselm

So ein Myst.