Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: | 66115 2008 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: Theoretische Informatik, Algorithmen Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 6 Bitte wenden! Frühjahr 2008 Einzelprüfungsnummer: 66115 Seite: 2 Thema Nr. 1 Aufgabe 1: Reguläre Sprachen Sei > = {a,b} ein Alphabet. Wir betrachten die Sprache L= {wy-+-ttp € Do n22A31Si m} genau eine Chomsky-Typ-2-Sprache ist! Aufgabe 3: Turing-Maschinen Si % = {a,b,c} ein endliches Alphabet. Wir betrachten die Sprache L = {wed *|vs € 4\{a}:|w]s <|wla}, also die Menge der Wörter, in denen a echt häufiger als die anderen Buchstaben vorkommt. a) Geben Sie eine deterministische Turingmaschine an, die Z für das Alphabet )) entscheidet. Die Maschine soll dabei wie folgt verfahren: - Das Arbeitsalphabet I soll zusätzliche Zeichen 0 und © enthalten. - Das Wort steht initial als OwO auf dem Band der Turingmaschine. - Die Turingmaschine sucht nach jeweils einem a,b und c und überschreibt das jeweils erste gefundene Zeichen mit ¢. - Wird dabei kein a gefunden, ist das Wort zu verwerfen. Wird ein a gefunden, aber weder b noch c, wird das Wort akzeptiert. Beachten Sie, dass es dabei möglich ist, ein a und c, aber kein b, oder ein a und b, aber kein c zu finden. - Nach einem solchen Durchgang fährt die Turingmaschine nach links und beginnt von vorne. Beschreiben Sie dabei die Bedeutung der Zustände q € Q Ihrer Turingmaschine informell. Fortsetzung nächste Seite! Frühjahr 2008 Einzelprüfungsnummer: 66115 Seite: 3 b) Geben Sie den Ablauf Ihrer Turingmaschine über dem Wort aba an. c) Geben Sie Laufzeit- und Speicherplatzkomplexität Ihrer Turingmaschine M in O-Notation an. Kann die Laufzeitkomplexität durch die Verwendung einer Mehrband-Turingmaschine verbessert werden? Begründen Sie Ihre Antworten. Frühjahr 2008 Einzelprüfungsnummer: 66115 Seite: 4 Thema Nr. 2 Hinweis: Die einzelnen Teilaufgaben bauen oftmals aufeinander auf, sind aber im Prinzip in beliebiger Reihenfolge lösbar. Sie dürfen hierbei die Angaben und Ergebnisse früherer Teilaufgaben uneingeschränkt zur Lösung späterer Teilaufgaben verwenden! Außerdem dürfen Sie Tatsachen aus dem Informatik-Duden ohne weitere Begründung als bekannt voraussetzen. Aufgabe 1: Effiziente Algorithmen a) Führen Sie den Dijkstra-Algorithmus zur Bestimmung aller kürzesten Pfade vom Startknoten s am folgenden Graphen aus: Dokumentieren Sie Ihre Schritte geeignet. b) Der Dijkstra-Algorithmus benutzt einen Heap R, in dem diejenigen Knoten verwaltet werden, deren Entfernung zu s noch nicht endgültig feststeht. Sei vı,v2,...u, eine Anordnung der Knoten in der Reihenfolge, in der sie aus R mittels deletemin(R,v) herausgenommen werden. Weisen Sie nach, dass in dieser Anordnung die Knoten aufsteigend nach der Entfernung d[v] von s sortiert sind. Zeigen Sie zuerst, dass für alle benachbarten Paare (v;, v;+1) von Knoten gilt: v; < vi41Fortsetzung nächste Seite! Frühjahr 2008 Einzelprüfungsnummer: 66115 Seite: 5 Aufgabe 2: Reguläre Sprachen a) Konstruieren Sie einen deterministischen endlichen Automaten, der die Sprache akzeptiert, die durch den regulären Ausdruck (a + b)*-a- (a+b) - (a+ b)- (a+ 6) beschrieben ist. Hinweis: Konstruieren Sie zuerst einen nichtdeterministischen endlichen Automaten, und wandeln Sie diesen anschließend in einen deterministischen endlichen Automaten um! Geben Sie einen nichtdeterministischen endlichen Automaten (NEA) mit maximal 4 Zuständen an, der die folgende reguläre Sprache akzeptiert: L={zy|x,ye{a,b}* x endet mit bund die Anzahl der Zeichen a in y ist durch 3 teilbar} Ein Wort w ist somit in L, falls das Zeichen b so in w vorkommt, dass die Zahl der Zeichen a, die nach diesem b stehen, durch 3 teilbar ist. Im Gegensatz zu deterministischen endlichen Automaten ist kein einfacher Minimierungsalgorithmus für nichtdeterministische endliche Automaten bekannt. Sie sollen hier dennoch nachweisen, dass jeder nichtdeterministische endliche Automat, der die in Teilaufgabe b) beschriebene Sprache Z akzeptiert, mindestens 4 Zustände besitzt. Betrachten Sie eine Zerlegung des Wortes w = baaa in die folgenden Paare: (x1, y1) = (€, baaa), (£2, 2) = (ba, aa), (23, y3) = (baa, a), (Ta, ya) = (baaa, €) Sei A ein (unbekannter) endlicher Automat, der L akzeptiert. Da w vom Automaten A akzeptiert wird, gibt es für jedes Paar (z;,y:) einen Zustand q, so dass einer der Berechnungspfade den Automaten vom Startzustand aus auf Eingabe x; in den Zustand g; führt, und von q; ausgehend auf der Eingabe y; in einen der— möglicherweise mehreren—Endzustände. Führen Sie nun die Annahme zum Widerspruch, dass A drei Zustände besitzt und zugleich keine Wörter akzeptiert, die nicht in L sind. Aufgabe 3: Kontextfreie Sprachen Gegeben sei die Sprache L= {ww | w € D*} über dem Alphabet 3) = {a,b} a) Beweisen Sie mit Hilfe des Pumping Lemma für kontextfreie Sprachen, dass die Sprache nicht kontextfrei ist. Hinweis: Gehen Sie hierzu von einem Wort der Form ww = a”™b"a"b" aus, bei geeigneter Wahl von n. Hinweis: Das Pumping Lemma für kontextfreie Sprachen lautet wie folgt: Ist L kontextfrei, so existiert n > 0 sodass für alle z € L eine Zerlegung der Form z = uvwry existiert, derart, dass |vx| > 1 und |vwe|] < n und uv'we'y € L für alleöi > 0. Fortsetzung nächste Seite! Frühjahr 2008 Einzelprüfungsnummer: 66115 Seite: 6 b) Begründen Sie, dass für jedes Wort z € D*, das nicht in L ist, einer der folgenden drei Fälle zutrifft: - z hat ungerade Länge, oder - z kann in der Form z = uavbw geschrieben werden mit |u| = m, |w| = n, |u| = m+n für geeignete m,n > 0, oder - z kann in der Form z = ubvaw geschrieben werden mit |u| = m, |w| = n, |u| = m+n für geeignete m,n > 0. Zum Beispiel ist aabababbab @.L und es passt der zweite Fall mit u = a, v = baba, w = bab, alsom=1,n=3. c) Begründen Sie nun, dass das Komplement 5* \ L kontextfrei ist.