Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: | Kennwort: Ä Herbst A 61 1 3 Arbeitsplatz-Nr.: _ _ 2 0 0 9 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 2009 Einzelprüfungsnummer 46113 Seite 2 Thema Nr. 1 Aufgabe 1: Reguläre Mengen Sei Lc {a,b}* die Menge aller Worte, deren zweites und zweitletztes Zeichen verschieden sind. Das leere Wort gehört nicht zu L. (a) Konstruieren Sie einen regulären Ausdruck für L. (b) Konstruieren Sie einen deterministischen endlichen Automaten A mit L(A)=L. Aufgabe 2: Konstruktion von Turingmaschinen a) Konstruieren Sie eine (k-Band) Turingmaschine M für die Sprache PAL = {wew | we {a,b}*}. Dabei ist wR die Spiegelung von w. b) Geben Sie die Menge der Worte der Länge 5 und 6 an, die Element von L sind. c) Welche Zeit-Komplexität hat Ihre Turingmaschine M? d) Ordnen Sie PAL in die folgende Hierarchie ein: die regulären Mengen, die kontextfreien Sprachen, P, NP, die rekursiven (entscheidbaren) Mengen. Was ist die kleinste Klasse in der PAL liegt? . Aufgabe 3: Formale Sprachen a) Zeigen Sie, dass die Sprache L= fat bNc4|n,m,gq> 0, n=m oder n=q} kontextfrei ist. Es reicht die Angabe einer geeigneten Grammatik oder eines geeigneten Automaten. b) Zeigen Sie, dass die (obige) Sprache L = {a" b™ c4| n,m,q>0, n=m oder n=q} nicht regulär ist. Der Beweis z. B. des Pumping Lemmas und von Abschlusseigenschaften wird nicht verlangt. Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 46113 Seite 3 Aufgabe 4: Abschlusseigenschaften a) Zeigen Sie: Wenn L eine reguläre Sprache ist, dann ist auch L* regulär. Es reicht die Angabe der Konstruktion; ein Korrektheitsbeweis Ihrer Konstruktion ist nicht verlangt. b) Zeigen Sie: Wenn L_ eine kontextfreie Sprache ist, dann ist auch 'L* kontextfrei. Es reicht die Angabe der Konstruktion; ein Korrektheitsbeweis Ihrer Konstruktion ist nicht verlangt. Aufgabe 5: Komplexität Begründen Sie, warum NP< REK gilt. NP ist die Klasse der nicht-deterministisch in Polynomzeit lösbaren Probleme (Sprachen); REK ist die Klasse der entscheidbaren (oder rekursiven) Sprachen. Herbst 2009 Einzelprüfungsnummer 46113 Seite 4 Thema Nr, 2 Aufgabe 1: Reguläre Sprachen Reguläre Sprachen können durch reguläre Ausdrücke mit den Operatoren e (Konkatenation), + (Vereinigung) und * (Abschluss) definiert werden. (a) Geben Sie eine genaue induktive Definition von regulären Ausdrücken über einem gegebenen Alphabet )) mit Basis- und Induktionsteil. (b) Geben Sie reguläre Ausdrücke für die folgenden regulären Mengen an: (a) die Menge aller Binärzahlen über {0,1}*, die durch 4 teilbar sind, (8) die Menge aller Worte über {0,1}*, die abwechselnd 0 und 1 enthalten, (y) die Menge aller Worte über {0,1}*, die eine gerade Anzahl von Oen und len enthalten. (c) Neben regulären Ausdrücken können auch endliche Automaten zur Beschreibung regulärer Mengen verwendet werden. Dabei kann zu jedem beliebigen regulären Ausdruck R über einem Alphabet 5° ein endlicher Automat konstruiert werden, der die von R definierte Sprache L(R) erkennt. Zeigen Sie, wie diese Konstruktion für einen beliebigen regulären Ausdruck R funktioniert. Geben Sie dabei entsprechend der induktiven Definition aus Aufgabenteil (a) für jeden Teil der Basis und des Induktionsschritts den zu den definierten regulären Ausdrücken gehörenden endlichen Automaten an. Begründen Sie Ihre Konstruktionsschritte. Ist der so entstehende Automat deterministisch oder nicht-deterministisch? (d) Verwenden Sie die Konstruktionsvorschrift aus Aufgabenteil (c) zur schrittweisen Konstruktion eines Automaten zum regulären Ausdruck 1(0+1)* über dem Alphabet {0,1}. Begründen Sie die durchgeführten Schritte. Fortsetzung nächste Seite! Herbst 2009 Einzelprifungsnummer 46113 Seite 5 Aufgabe 2: Kontextfreie Sprachen und Grammatiken (a) Betrachten Sie die folgende Sprache Ly = {a"b™c"d" für m > 0,n > 0}. Ist dies eine kontextfreie Sprache? Begründen Sie Ihre Antwort. Wenn L, eine kontextfreie Sprache ist, geben Sie eine kontextfreie Grammatik mit Terminalsymbolen, Nichtterminalsymbolen und Produktionen an, die L, erzeugt. Erläutern Sie die Arbeitsweise der von Ihnen angegebenen Grammatik. (b) Formulieren Sie die Aussage des Pumping-Lemmas für kontextfreie Sprachen. Erläutern Sie die Gültigkeit dieses Lemmas. Erläutern Sie, wie das Pumping-Lemma für kontextfreie Sprachen dazu verwendet werden kann zu beweisen, dass eine bestimmte Sprache nicht kontextfrei ist. (c) Betrachten Sie die folgende Sprache Lz = {a"b™c"d™ für m > 0,n > O}. Beweisen Sie mit Hilfe des Pumping-Lemmas für kontextfreie Sprachen, dass L2 nicht kontextfrei ist. (d) Argumentieren Sie, warum die kontextfreien Sprachen unter der Vereinigungsoperation abgeschlossen sind. Konstruieren Sie dazu für beliebige kontextfreie Grammatiken G, bzw. Ga zur Erzeugung von kontextfreien Sprachen Lı bzw. La eine kontextfreie Grammatik zur Erzeugung von Lı UL». Erläutern Sie die Arbeitsweise von G. Aufgabe 3: Kellerautomaten (a) Kontextfreie Sprachen können mit Hilfe von Kellerautomaten erkannt werden. Geben Sie eine exakte mathematische Definition eines Kellerautomaten. Erläutern Sie ‘ den Unterschied zwischen nicht-deterministischen und deterministischen Kellerautomaten. Welche Unterschiede in den Verarbeitungsschritten gibt es? (b) Betrachten Sie die Sprache L, = {a"b"c”d” für m > 0,n > 0} aus Aufgabe 2, Teil (a). Konstruieren Sie einen (nicht-deterministischen) Kellerautomaten K = (Q,L,T, 6,90, Zo, F), der Lı erkennt. Geben Sie eine genaue Definition aller Elemente des Kellerautomaten mit einer mathematisch exakten Definition der Übergangsrelation ö an. Erläutern Sie die Arbeitsweise des Kellerautomaten und begründen Sie, warum K alle Worte aus L erkennt. (c) Kann die Sprache aus Aufgabenteil (b) durch einen deterministischen Kellerautomaten erkannt werden? Begründen Sie Ihre Antwort.