Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Herbst 461 13 Arbeitsplatz-Nr.: _ _ 2 0 1 0 Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (Unterrichtsfach) Einzelprüfung: Theoretische Informatik Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 5 Bitte wenden! Herbst 2010 Einzelprüfungsnummer 46113 Seite 2 Thema Nr. 1 Aufgabe 1 Chomsky-Hierarchie a) Zeigen Sie jeweils durch Angabe einer Sprache, dass die Typ 3-Sprachen echt in der Menge der Typ 2-Sprachen, sowie die Typ 2-Sprachen echt in der Menge der Typ 1-Sprachen enthalten sind. b) Gegeben sei die Sprache L= {zx € {0,1,2,3}* \ {e}-| & (als Zahl im Dezimalsystem gelesen) ist nicht durch 3 teilbar}. Ordnen Sie die Sprache Z in die Chomsky-Hierarchie ein und beweisen Sie Ihre Aussage durch Angabe eines akzeptierenden Automaten. Aufgabe 2 Endliche Automaten Gegeben sei der folgende deterministische, endliche Automat D: 0,1 a) Konstruieren Sie aus D einen Minimalautomaten Dyin. b) Geben Sie explizit die Sprache an, die der Automat D bzw. Din akzeptiert. c) Geben Sie einen regulären Ausdruck für diese Sprache an. Aufgabe 3 ‘Pumping Lemma und Satz von Myhill-Nerode Sei = = {a,b,c} ein Alphabet und seien die folgenden beiden kontextfreien, nicht-regulären Sprachen über 3 gegeben: Li ={a”b"”c"|m>0,n>1} La = In U {b, c}* a) Geben Sie eine kontextfreie Grammatik für £, an. b) Zeigen Sie, dass La die Behauptung des Pumping Lemma für reguläre Sprachen erfüllt. c) Geben Sie den Satz von Myhill-Nerode an. d) La ist eine nicht-reguläre Sprache. Dies kann nach Teil b) dieser Aufgabe nicht mit dem Pumping Lemma gezeigt werden. Beweisen Sie nun mit Hilfe des Satzes von Myhill-Nerode, dass La nichtregulär ist. [Hinweis: Es reicht, unendlich viele nicht-äquivalente Wörter z € D* zu finden.] Fortsetzung nächste Seite! Herbst 2010 Einzelprüfungsnummer 46113 Seite 3 Aufgabe 4 Berechenbarkeit Sei eine Funktion f gegeben, die für jede Eingabe w € {0,1}* das Wort w’ € {0,1}* berechnet, das aus w entsteht, indem man jedes Vorkommen von 0 durch 00 ersetzt. Beispiel: f(00101) = 00001001 a) Geben Sie eine deterministische Turing-Maschine M an, die f berechnet. Beschreiben Sie dabei die Bedeutung der Zustände bzw. Übergänge Ihrer Turing-Maschine informell. b) Geben Sie den Ablauf von M für die Eingabe 01 an. c) Bestimmen Sie Laufzeit-. und Speicherplatzkomplexität von M in O-Notation. : Herbst 2010 Einzelprüfungsnummer 46113 Seite 4 Thema Nr. 2 Annahmen: Sie dürfen als bekannt und bewiesen voraussetzen: Die Sprache {a"b"| n> 1} ist nicht regular. Die Sprache {a" b"c"| n > 1} ist nicht kontextfrei. Um zu zeigen, dass eine Sprache L regular (kontextfret) ist, reicht die Angabe einer entsprechenden Beschreibung (Automat, Grammatik, regulärer Ausdruck). Sie müssen nicht mehr zeigen, dass Ihre Beschreibung korrekt ist und genau die vorgegebene Sprache beschreibt. Aufgabe 1: reguläre Mengen Sei L die Menge aller Worte über dem Alphabet {a,b}, bei denen das zweite und das zweitletzte Zeichen gleich sind. Beachten Sie auch die kurzen Worte. Beschreiben Sie L a) durch einen regulären Ausdruck b) durch einen deterministischen endlichen Automaten A. Aufgabe 2: regulär oder nicht L besteht aus der Menge aller Worte über dem Alphabet {a,b}, bei denen die Anzahl von a's gerade und die Anzahl der b's ungerade ist. Ist die Sprache L regulär oder nicht? Begründen Sie Ihre Antwort. Aufgabe 3: Sei PAL = {w | w= w“, w e{a,b}*}, w” ist w gespiegelt oder rückwärts gelesen. a) Geben Sie alle Worte bis zur Länge 5 von PAL an. b) Klassifizieren Sie PAL: Ist PAL regulär? Begründen Sie Ihre Entscheidung. Ist PAL kontextfrei? Begründen Sie Ihre Entscheidung. Ist PAL rekursiv aufzählbar (positiv semi-entscheidbar)? Begründen Sie Ihre Entscheidung. Fortsetzung nächste Seite! Herbst 2010 Einzelprüfungsnummer 46113 Seite 5 Aufgabe 4: Konstruieren Sie eine Turingmaschine M für die Sprache - L=-{a@b’c'|n>1} Welche Zeit-Komplexität hat Ihre Turingmaschine M? Welche Speicher-Komplexität hat Ihre Turingmaschine M? Aufgabe 5: Das Feedback-Arc-Set Problem (FAS) Gegeben: Ein gerichteter Graph G = (V, E) mit Knotenmenge V und Kantenmenge E und eine Zahl k. Problem: Gibt es eine Teilmenge von höchstens k Kanten F,FCE, |F|