Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kenawort Frühjahr — | 46113 Arbeitsplatz-Nr.: . 2 0 1 4 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: 7 Bitte wenden! Frühjahr 2014 Einzelprüfungsnummer 46113 Seite 2 Thema Nr. 1 Aufgabe 1: Reguläre Sprachen I Sei & = {a,b} und I, die Sprache aller Wörter über D, in denen das Wort ab nicht vorkommt. Sei weiterhin D2 die Sprache aller Wérter über &, in denen b genau zwei mal vorkommt. 1.Geben Sie jeweils einen regulären Ausdruck für Ly und Ly an. 2.Eine Grammatik heißt rechtslinear, wenn es für jede Produktion Nichtterminale A, B und ein Terminalsymbol 2 gibt, so dass die Produktion die Form A + xB oder A— e hat. Geben Sie eine rechtslineare Grammatik für die Sprache Le \ Ly an. 3.Geben Sie einen minimalen deterministischen endlichen Automaten an, der die gleiche Sprache erkennt wie der unten aufgeführte Automat! Geben Sie zu jedem Zustand des mininialen Automaten an, zu welchen Zuständen des originalen Automaten er gehört! Fortsetzung nächste Seite! Frühjahr 2014. Einzelprüfungsnummer 46113 Seite 3 Aufgabe 2: Kontextfreie Sprachen 1. Betrachten Sie die Grammatik G = (N,D, P, 5) mit N ={S,T,U,V, A, C} und x = {a,b,c}. Die Menge P besteht aus den folgenden Produktionen: S>AT Voa|lb|CU T-UA Aa U->CV|AT|VV Cc Zeigen Sie mit dem CYK-Algorithmus, dass das Wort acca nicht in L(G) liegt. 2. Zeigen Sie mit dem Pumping-Lemma für kontextfreie Sprachen, dass die folgende Sprache nicht kontextfrei ist: L = { a®ba"ba” | n € N} Fortsetzung nächste Seite! Frühjahr 2014 Einzelprüfungsnummer 46113 \ Seite 4 Aufgabe 3: Komplexitätstheorie Wir betrachten das Problem des Handlungsreisenden (TSP). Zur Erinnerung: Für eine Menge von Städten S und eine Entfernungsfunktion d zwischen diesen Städten stellen wir die folgende Frage: Existiert eine Route, die jede Stadt genau einmal besucht und dann zum Ausgangsort zurückkehrt, so dass die insgesamt; zurückgelegte . Entfernung höchstens x ist? Formal ist das Problem TSP wie folgt definiert: Gegeben: (S,d,z) S ...Menge von Städten d...Totale Distanzfunktion d: Sx 5 +R z ...Maximal erlaubte Gesamtdistanz Problem: Existiert eine Folge s1,...,8, mit |S| =n, so dass alle s; unterschiedlich sind und die Gesamtentfernung (S71 <;cn @(3:, 8141)) + d(Sn, 51) höchstens x ist? 1. Begründen Sie: TSP liegt in NP. 2. Geben Sie eine polynomielle Reduktion von HAMILTON auf TSP an! Das Problem HAMILTON ist die Frage, ob ein Graph einen Hamiltonpfad besitzt. Ein. Hamiltonpfad ist ein Weg im Graphen, der jeden Knoten genau einmal enthält. Formal ist das Problem HAMILTON wie folgt definiert: Gegeben: Graph G = (E, K): - ...Menge von Ecken K ...Menge von Kanten Problem: Existiert ein Hamiltonpfad in G, d.h., existiert eine Folge €1,..., én mit |E| = n, so dass die e; alle unterschiedlich sind und für alel aSbS, S-> X, X->aXb, X->ab. b) Zeigen Sie (durch Angabe einer Ableitung), dass das Wort w=aabbaabb in L(G) bzw. L(G) liegt. Aufgabe 6: Berechenbarkeit Gegeben sei die Sprache PAL={w cwleV|w e {a,b}*} über dem Alphabet {a,b,c}. wie ist w gespiegelt. die die Sprache PAL erkennt! . Beschreiben Sie, wie Ihre Turingmaschine arbeitet! b) Welche Zeitkomplexität in O-Notation hat Ihre Turingmaschine? Aufgabe 7: Komplexität Warum ist die Sprache SAT der erfüllbaren booleschen Ausdrücke in konjunktiver Normalform in NP? Erläutern Sie, was man für einen Ausdruck testen musst Nicht gefragt ist, warum das Problem sogar NP-vollständig ist.