Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 461 1 3 2006 Arbeitsplatz-Nr.: 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 2006 Einzelprüfungsnummer: 46113 Seite: 2 Thema Nr. 1 Sämtliche Teilaufgaben sind zu bearbeiten! Teilaufgabe | Gegeben sei der nicht-deterministische endliche Automat M mit dem Eingabealphabet I = {a,b}, der Zustandsmenge Q = (a, Id» a} , Anfangszustand go, Endzustand g3 und der Übergangsfunktion 6 mit: L(M) sei die von M akzeptierte Sprache. a) Beweisen Sie: al) abbba € L(M) a2) Injedem w € L(M)kommt a mindestens einmal vor. a3) Zujedem ne N gibtesein w € L(M), indem a mehr als n-mal vorkommt. b) Geben Sie eine reguläre (Typ-3-) Grammatik an, die L(M) erzeugt. c) Konstruieren Sie aus M einen deterministischen endlichen Automaten, der L(M) akzeptiert. d) Geben Sie einen regulären Ausdruck an, der L(M) beschreibt. Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 46113 Seite: 3 Teilaufgabe 2 Gegeben seien das Alphabet > = {a,b}, die Grammatik G = ({8,A},2,5, P) mit der aus den Produktionsregeln S— Ab A b|aAa bestehenden Menge P sowie die Sprache L = [a"ba"b m > o} über D. a) Beweisen Sie: Z ist die von G erzeugte Sprache. b) Beweisen Sie: Z ist nicht regulär. c) Überführen Sie G in Chomsky-Normalform. Teilaufgabe 3 Es seien $ ein Alphabet, a ein Zeichen von % und Z, und Z> zwei Sprachen über %. Gelten folgende Aussagen? Begründen Sie Ihre Antworten. a) Sind L, und L2 semi-entscheidbar, so ist L, \ Z, semi-entscheidbar. b) Sind Z; und Z; entscheidbar, so ist die Funktion f : 2’ — D’mit a falls wveLNZ, fw) = aa sonst berechenbar. c) Ist Zı mit einer deterministischen Turing-Maschine mit einer Zeitkomplexitat O(n) entscheidbar, so gilt dies auch für I’ \L,. (n ist die Länge der jeweiligen Eingabe.) d) Sind sowohl Z, als auch Z> mit einer deterministischen Turing-Maschine mit einer Zeitkomplexitat O(n’) entscheidbar, so gilt dies auch für L, UL,. (nist die Lange der jeweiligen Eingabe.) Herbst 2006 Einzelprüfungsnummer: 46113 Seite: 4 Thema Nr. 2 Aufgabe 1 (reguläre Sprachen und endliche Automaten) Die Elemente einer regulären Sprache können durch deterministische oder nicht-deterministische endliche Automaten erkannt werden. Betrachten Sie folgenden nicht-deterministischen endlichen Automaten A= (2,0% Qs a,} 5 {o, 11,5, I {a, }) mit Zustandsmenge {4.4 9,95%} Eingabealphabet [0, i} , Anfangszustand qg; und Endzustandsmenge {a Ag Die Übergangsfunktion 6 sei durch folgende Tabelle definiert: a qi G2 q3 OY Fava | warme] ta | Tad ta} | fd | 0 | tod | to) a) Zeichnen Sie das Übergangsdiagramm des Automaten mit Zuständen und Übergangskanten. b) Beschreiben Sie die von Aı erkannte reguläre Sprache L|, indem Sie eine mathematisch exakte Definition der Menge der erkannten Worte über {0, 1} angeben. Begründen Sie Ihre Antwort. c) Geben Sie einen möglichst kurzen regulären Ausdruck an, der die Sprache Z beschreibt. d) Wandeln Sie den nicht-deterministischen endlichen Automaten A, in einen deterministischen endlichen Automaten A, um, indem Sie die Teilmengenkonstruktion anwenden. Konstruieren Sie dazu ausgehend vom Anfangszustand von Aı die e-Folgezustände der jeweils entstehenden Zustände. Geben Sie für Aa sowohl ein Übergangsdiagramm als auch eine tabellenférmige Darstellung der Übergangsfunktion an. e) Definieren Sie die Äquivalenz von Zuständen in endlichen Automaten. f) Bestimmen Sie mit Hilfe des Table-Filling-Verfahrens alle äquivalenten Zustände von A». Bauen Sie dazu die vollständige Tabelle mit Zustandspaaren schrittweise auf und markieren Sie, ob die jeweiligen Zustände unterscheidbar sind. Erläutern Sie jeden durchgeführten Schritt. Fassen Sie anschließend die äquivalenten Zustände zusammen und konstruieren Sie den resultierenden deterministischen endlichen Automaten A;, indem Sie für A ein Übergangsdiagramm und eine tabellenförmige Darstellung der Übergangsfunktion angeben. g) Gibt es einen deterministischen endlichen Automaten mit weniger Zuständen als Aa, der die reguläre Sprache Lı erkennt? Begründen Sie Ihre Antwort kurz. Geben Sie gegebenenfalls einen deterministischen endlichen Automaten mit weniger Zuständen als A; an. Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 46113 Seite: 5 Aufgabe 2 (kontextfreie Sprachen und Kellerautomaten) a) Betrachten Sie die kontextfreie Sprache L = {a’b";n > 1} über dem Alphabet {a,b}. Geben Sie eine kontextfreie Grammatik G mit Terminalsymbolen, Nichtterminalsymbolen und Produktionen an, die Z erzeugt. b) Konstruieren Sie einen nicht-deterministischen Kellerautomaten K = (Q,2,T,6,q,,2,,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 Z erkennt. c) Erläutern Sie den Unterschied zwischen nicht-deterministischen und deterministischen Kellerautomaten durch Angabe der exakten Definitionen. Welche Unterschiede in den Verarbeitungsschritten gibt es? d) Kann die Sprache L = {a"3";n > 1} durch einen deterministischen Kellerautomaten erkannt werden? Begründen Sie Ihre Antwort. e) Betrachten Sie die folgende kontextfreie Grammatik G = ({5},{0,1,+,*}, P,S) mit den Produktionen P = {s 3 $+5,8 +8+*S,5 40,5 } . Beweisen Sie, dass diese Grammatik mehrdeutig ist. Aufgabe 3 (Berechenbarkeit und Turingmaschinen) a) Konstruieren Sie eine deterministische Turingmaschine zum Erkennen der Sprache L= {orn 1}über dem Alphabet {0,1}. Beim Start der Turingmaschine stehe das Eingabewort w € {0,1} aufdem Band. Erläutern Sie die Rolle der Zustände der von Ihnen konstruierten Turingmaschine und geben Sie die Übergangsfunktion in Tabellenform an. b) Illustrieren Sie die Arbeitsweise der von Ihnen konstruierten Turingmaschine, in dem Sie die Berechnungsschritte für die Eingabe 0011 als Konfigurationsübergänge angeben. c) Erläutern Sie die Funktionsweise nichtdeterministischer Turingmaschinen. Erkennen nicht-deterministische Turingmaschinen dieselbe Sprachklasse wie deterministische Turingmaschinen? Geben Sie eine ausführliche Begründung für Ihre Antwort.