Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: F ru hj ahr 46113 Arbeitsplatz-Nr.: | 2 0 1 3 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: 6 Bitte wenden! Frühjahr 2013 Einzelprüfungsnummer 46113 Seite 2 Thema Nr. 1 Aufgabe 1: Reguläre Sprachen I 1. Seid = {a,b}. Für ein we D* und x € DB bezeichnen wir mit |w|, die Anzahl der z in w. Sei L = {w € 2* | |w|a gerade}. Geben Sie einen regulären Ausdruck a mit L(a) = DL an. 2. Eine Grammatik heißt rechts-linear, wenn es für jede Produktion Nichtterminale A,B und ein Terminalsymbol x gibt, so dass die Produktion die Form A — zB oder A — e hat. Geben Sie eine rechtslineare Grammatik für die Sprache D aus Teilaufgabe 1 an. 3. Geben Sie einen endlichen Automaten (gegebenenfalls mit s-Transitionen) an, der die Sprache L(c(alb*c)*c) erkennt. Aufgabe 2: Reguläre Sprachen II Sei © ein Alphabet. Für eine Sprache L C %&* nennen wir zieh(L) = {at a2... afr | akt ah? ...ake € LAa1,ay,...‚mE% A1<&4 0;m gerade} 2. Bringen Sie die Grammatik Gi = (Ni, D1, 1, S$) in Chomsky-Normalform. Dabei sei N = {S,T, UV}, “y= {a,b,c} und P; bestehe aus den folgenden Produktionen: S>aT ToaTUl|e U-+be 3. Betrachten Sie die Grammatik Ga = (Na, Ya, Pa, 5) mit No = {S,T,U, A, B,C} und D2 = {a,b,c}, wobei P, aus den folgenden Produktionen besteht: S— AU| SS T-AB|BT|TC U- BA|BO|UB A-a Bob Cec Verwenden Sie den CYK-Algorithmus um zu zeigen, dass das Wort babe nicht in L(Gs) liegt. 4. Für ein X € No sei Gx = (No, Xe, Po, X) mit No, 42 und P2 aus der vorherigen Teilaufgabe. Geben Sie ein X € Na an, so dass babe € L(Gx) gilt. Aufgabe 4: Komplexitätstheorie Mit EX bezeichnen wir die Menge aller aussagenlogischen Formeln, die ausschließlich aus den Konstanten 0 und + und logischen Variablen aufgebaut sind (Klammern sind erlaubt). Dabei ist x + y so definiert, dass es die gleiche Wahrheitstafel wie x — ay hat. Wir betrachten das Problem EXSAT: Gegeben: FEEX Problem: Ist F erfüllbar, d.h.,gibt es eine Belegung der Variablen mit 0 oder 1, so dass F' den Wert 1 annimmt? 1. Begründen Sie: EXSAT liegt in NP. 2. Finden Sie eine Formel F(x) in EX, die äquivalent zu -x ist und z nur einmal enthält. 3. Zeigen Sie: EXSAT ist NP-hart. Sie dürfen dazu benutzen, dass das SAT-Problem NP-hart ist. Fortsetzung nächste Seite! Frühjahr 2013 Einzelprüfungsnummer 46113 Seite 4 Aufgabe 5: Entscheidbarkeit Sei & = {0,1}. Wir nehmen an, dass jedes w € D eine Turingmaschine kodiert und bezeichnen diese TM mit M,„. Die von M„ berechnete Funktion bezeichnen wir mit y,,. 1. Welche der folgenden Sprachen sind entscheidbar? Begründen Sie kurz. a) Ly := {w € * | yy (x) = « für alle Eingaben x}. | b) Lo := {w € E* | dw! , so dass y,, (x) = Yu (x) für mindestens ein x}. c) Lg := {w € X* | M, hat mindestens 12 Zustinde} 2. Semientscheidbarkeit a) Eine Sprache ist semientscheidbar genau dann, wenn sie rekursiv aufzählbar ist. Definieren Sie einen dieser beiden Begriffe. b) Geben Sie eine semientscheidbare Sprache an, die nicht entscheidbar ist. Begründen Sie, dass die Sprache diese beiden Eigenschaften besitzt. 3. Konstruieren Sie eine Turingmaschine M mit Eingabealphabet 3, die alle 0-en aus dem Eingabewort entfernt. Das heißt, M berechnet die folgende Funktion 3* — D*: fe)=e fllw)=1f(w) fw) = fw) Beispiel: Für die Eingabe 0110001 soll M die Ausgabe 111 liefern. Frühjahr 2013 | Einzelprüfungsnummer 46113 Seite 5 Thema Nr. 2 Aufgabe 1: regulär Sei L die Menge aller Worte über dem Alphabet {a,b,c}, bei denen der zweite und der zweitletzte Buchstabe übereinstimmen. a) Listen Sie alle Worte aus L der Länge 3 auf. b) Beschreiben Sie L durch einen regulären Ausdruck. c) Geben Sie für L einen deterministischen endlichen Automaten (DFA) an. Aufgabe 2 : endliche Automaten a) Konstruieren Sie zum nachfolgenden nichtdeterministischen endlichen Automaten (NFA) A einen äquivalenten DFA. A hat die Zustände £0,1,2,3}, den Anfangszustand 0, den Endzustand 3 und die angegebenen Zustandsübergänge i a,b (0) a b) Minimieren Sie Ihren DFA oder, falls er bereits minimal ist, begründen Sie warum. Aufgabe 3: regulär Sei L={a"b"| n>0} a) Zeigen Sie, dass L kontextfrei ist. b) Zeigen Sie, dass L nicht regulär ist. Fortsetzung nächste Seite! Frühjahr 2013 Einzelprüfungsnummer 46113 Seite 6 Aufgabe 4: kontextfrei ‚Sei G=(N,T,S,P) eine kontextfreie Grammatik mit den Produktionen S > aaSb, S > A, A> aAb, A > ab. a) Konstruieren Sie eine äquivalente kontextfreie Grammatik G’ in Chomsky-Normalform. b) Beschreiben Sie L in Worten in der Form: L besteht aus der Menge aller Worte w über dem Alphabet {a,b} mit w=.... Aufgabe 5: Turingmaschinen Konstruktion von Turingmaschinen a) Konstruieren Sie eine (k-Band) Turingmaschine M für die Sprache PAL= {aM cat cadl n>0} b) Welche Zeit-Komplexität hat Ihre Turingmaschine M. Aufgabe 6: Was ist mit dem P- NP - Problem gemeint? Definieren Sie P und NP und beschreiben Sie,was mit P versus NP gemeint ist.