Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Frü hj ahr 46113 Arbeitsplatz-Nr.: _ 2 0 1 2 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: 4 Bitte wenden! Frühjahr 2012 Einzelprüfungsnummer 46113 Seite 2 Thema Nr. 1 1. Binärzahlen mit Prüfziffer Sei 5 = {0,1}. Eine Binärzahl mit Prüfziffer ist ein Wort der Sprache 0, falls die Anzahl der len in bo... by Ly = {bo..-bnbe | n SOAS = gerade ist } 1, sonst (a) Zeigen Sie durch Angabe einer Grammatik, dass £, regulär ist. (b) Geben Sie die Äquivalenzklassen der Sprache £, (bzgl. des Satzes von Myhill/Nerode) an. (c) Zeigen Sie mit dem Pumping-Lemma: Die Sprache 0, falls die Anzahl der len in bo...b, Lp: = {bo...bnbe | n > OAR = kleiner als die der Oen ist } 1, sonst ist nicht regulär. (d) Zeigen Sie: Die Sprache Lp: ist kontextfrei. 2. Endliche Automaten (a) Sei X = {a,b}. Gegeben sei der folgende nichtdeterministische endliche Automat A über =: Geben Sie die Sprache £(A) des Automaten an. (b) Konstruieren Sie mittels der Potenzmengenkonstruktion einen deterministischen endlichen Automaten A’ mit £(A') = L(A). (c) Minimieren Sie den Automaten A’ oder zeigen Sie, dass dieser bereits minimal ist. Frühjahr 2012 Einzelprüfungsnummer 46113 Seite 3 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 (kontextfrei) ist, reicht die Angabe einer entsprechenden Beschreibung (Automat, Grammatik, 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 erste, dritte und das zweitletzte Zeichen gleich sind. Beschreiben Sie L a) durch einen regulären Ausdruck. b) durch einen deterministischen endlichen Automaten A. Beachten Sie auch die kurzen Worte! Aufgabe 2: regulär oder nicht L besteht aus der Menge aller Binärzahlen ohne führende Nullen über dem Alphabet {0,1}, die durch 3 oder durch 8 teilbar sind. Ist die Sprache L regulär oder nicht? Begründen Sie Ihre Antwort durch die Angabe einer passenden Beschreibung für L oder den Nachweis, dass L nicht regulär sein kann. Aufgabe 3: Abschlusseigenschaften Für zwei Sprachen X und Y sei X @Y={w|(we X und we Y) oder (we X und we Y). Begrtinden Sie, dass X @Y regulär ist, wenn X und Y regulär sind. Fortsetzung nächste Seite! Frühjahr 2012 Einzelprüfungsnummer 46113 Seite 4 Aufgabe 4: Minimierung von deterministischen endlichen Automaten Minimieren Sie den DFA A = (Q, {a,b}, 6,0, F) mit Q = {0,1,2,3,4,5}, F= {1,.2,3} und 6 mit nachfolgender Tabelle 0 11 |2 43 4 5 a 1 1 4 5 b 3 |1 |2 5 4 Aufgabe 5: Gegeben sei die Sprache L mit der Menge aller Worte über {a}* {b}* {a}*, bei denen die Anzahl der a's gleich der Anzahl der b's ist. a) Zeigen Sie, dass L kontextfrei ist. b) Zeigen Sie, dass L nicht regular ist. Aufgabe 6: a) Konstruieren Sie eine Turingmaschine M für die Sprache L={wewR c w | we {a,b}*} Dabei ist wR die Spiegelung von w (w wird rückwärts gelesen). b) Welche Zeit-Komplexität hat Ihre Turingmaschine M? Aufgabe 7: a) Definieren/Beschreiben Sie, wann ein Problem (eine Sprache) NP-vollständig ist. b) Beschreiben Sie ein NP-vollständiges Problem. ‚Die Beschreibung kann etwa so aussehen: Das Kürzeste-Wege-Problem: Gegeben ist ein Graph G mit Längen auf den Kanten, einem Startknoten s . „und einem Zielknoten t und eine Zahl k. Frage/Problem: Gibt eseinen Weg von s nach t der Länge