Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: — . 46113 | 2010 | 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! Frühjahr 2010 . Einzelprüfungsnummer: 46113 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! 1. Betrachten Sie über dem Alphabet = {a,b} die Sprache L, die durch folgendes Regelsystem vollständig gegeben ist: - Das Wort hört - (Gehört ein Wort w zu L und endet w mit einem a, so gehört auch wb zu L, d.h. für u€ >* gilt uae LD => uabe L. - Gehért w zu L, so gilt auch ww € L. - Folgen in einem Wort w € L drei a’s unmittelbar aufeinander, so gehört auch das Wort zu L, das man aus w erhält, wenn man aaa durch b ersetzt, d.h. für vv € 2* gilt uaaav € L => ubv € L. - Folgen in einem Wort w € L zwei b’s unmittelbar aufeinander, so gehört auch das Wort zu L, das man aus w erhält, wenn man bb streicht, d.h. füruve2*gitubveL>weLl. Beispielsweise gehört das Wort baab zu L, was man an der Ableitung at aa! aaaa} ba + bab + babbab + baab sieht. Da das Regelsystem sowohl verlängernde als auch verkürzende Regeln enthält, ist die Zugehörigkeit eines Worte w € D* zur Spache Z scheinbar nicht einfach zu entscheiden. Da das Regelsystem keine reguläre Grammatik ist, ist auch nicht klar, ob die Sprache L regulär ist. a) Zeigen Sie, dass alle Wörter w € L die Eigenschaft haben: (*) Die Anzahl |w|, der Vorkommen von a in w ist nicht durch 3 teilbar. b) Tatsächlich charakterisiert die Eigenschaft (*) die Sprache L, d.h. es gilt L={we2*;3#lwla}. Verwenden Sie diese Aussage (die Sie nicht beweisen sollen!) um einen minimalen vollständigen DFA zu konstruieren, der die Sprache L akzeptiert. c) Beweisen Sie, dass Ihr Automat tatsächlich minimal ist! 2. Betrachten Sie die Funktion des ganzzahligen Quadratwurzelziehens: sqrt: N->N: ar |Vz2| a) Geben Sie ein Programm für sqrt in einer Ihnen geläufigen Programmiersprache an. b) Geben Sie ein WHILE-Programm für sqrt an. c) Geben Sie ein Loop-Programm für sqrt an. ) d) Zeigen Sie, dass sqrt eine primitiv-rekursive Funktion ist, indem Sie eine entsprechende Definition angeben. Fortsetzung nächste Seite! Frühjahr 2010 - Einzelprüfungsnummer: 46113 Seite: 3 Hinweise: - Sie können, falls Ihnen das hilfreich erscheint, die Tatsache verwenden, das 1+3+5-+ + (2n —1) =n? ist. - |x| bezeichnet die gré8te ganze Zahl, die kleiner oder gleich x ist, also z.B. |3,1] = 3. 3. Beweisen oder widerlegen Sie die folgenden Behauptungen über Sprachen A,BC %*. AAB= (A \ B)U(B\ A) bezeichne dabei die symmetrische Mengendifferenz. a) Sind A und B regulär, so ist auch AAB regulär. | b) Sind A und B kontextfrei, so ist auch AAB kontextfrei. c) Sind A und B entscheidbar, so ist auch AAB entscheidbar. d) Sind A und B partiell-entscheidbar, so ist auch AAB partiell-entscheidbar. e) Sind A und B polynomiell-entscheidbar, so ist auch AAB polynomiell-entscheidbar. 4, ALICE und Bos verfügen jeder über einen DFA über dem Alphabet © = {0,1}. Der Automat von ALICE sei 21, der Automat von BoB sei 8. Beide Automaten haben die gleiche Anzahl n von Zuständen. ALICE und BOB wollen die Frage klären, ob es ein Wort w € D* gibt, das von beiden Automaten akzeptiert wird. ALICE, argumentiert: ”Diese Frage können wir gar nicht entscheiden, denn dafür müssten wir unendlich viele Wörter aus %* durchprobieren.“ Boß hält dem entgegen: ” Das geht doch ganz einfach: Wenn ein Automat n Zustände hat, können alle akzeptierenden Zustände in höchstens n — 1 Schritten erreicht werden. Es genügt also, Wörter der Länge < n zu testen, ob eines von ihnen von beiden Automaten A und B akzeptiert wird.“ Kommentieren Sie die beiden Aussagen! Sollten Sie weder ALICE noch BoB zustimmen, so zeigen Sie einen Weg auf, die Frage zu beantworten. Geben Sie ein Entscheidungsverfahren an oder weisen Sie nach, dass es sich um ein unentscheidbares Problem handelt. Frühjahr 2010 Einzelprüfungsnummer: 46113 | Seite: 4 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! 1. Gegeben ist die folgende Sprache L1 über dem Alphabet © = {a, b}: Ii = {we%* | die Anzahl der a in w ist gerade und b kommt in w genau einmal vor}. a) Geben Sie einen deterministischen endlichen Automaten’an, der die Sprache L1 akzeptiert. b) Geben Sie einen regulären Ausdruck an, der die Sprache L1 beschreibt. Die folgende Sprache L2 ist eine Erweiterung von L1: L2 = {we%* | die Anzahl der a in w ist gerade und die Anzahl der b in w ist ungerade}. c) Geben Sie einen deterministischen endlichen Automaten an, der die Sprache 22 akzeptiert. d) Geben Sie eine rechtslineare Grammatik an, die die Sprache L2 erzeugt. 2. Gegeben ist die folgende Sprache L über dem Alphabet © = {0,1}: L = [wel*|w# e,w enthält gleich viele 0-en wie l-en und in jedem Anfangswort von w kommen mindestens soviele O-en wie 1-en vor}. a) Geben Sie alle Wörter we L mit Länge |w| < 4 an. b) Geben Sie eine kontextfreie Grammatik an, die die Sprache I, erzeugt. c) Zeigen Sie, dass L nicht regulär ist. Der Beweis kann ohne Anwendung des Pumping Lemmas unter Verwendung der beiden folgenden Tatsachen geführt werden: i) Der Durchschnitt zweier regulärer Sprachen ist regulär. ii) Die Sprache L’ = {0719 | j > 0} ist nicht regulär. Wir betrachten nun für alle natürlichen Zahlen n € N die folgenden Teilsprachen L, von L: In. = T{weL]|in jedem Anfangswort von w kommen höchstens n mehr 0-en vor als I-en}. d) Für alle natürlichen Zahlen n ist L„ regulär. Zeigen Sie dies für den Fall n = 3. e) Wie kann man aus den Tatsachen, dass L nicht regulär ist und L, für allen € N regulär ist, schließen, dass die Vereinigung abzählbar unendlich vieler regulärer Mengen nicht notwendigerweise regulär ist? : 3. Zeigen Sie, dass die Funktion f:N — N, mit f({n) = 2 % 2) für allen € N, primitiv rekursiv ist. Dabei bezeichnet n div 2 die ganzzahlige Division durch 2. Beim Beweis ist das Schema der primitiven Rekursion zu verwenden, d.h. es sind geeignete primitiv rekursive Funktionen g: N— N und h: N? — N anzugeben, so dass gilt: f(0) = 9, f(n+1) = h(n, f(n)) fir allen EN. Es kann vorausgesetzt werden, dass die Multiplikation und die Fallunterscheidung, ob eine natürliche Zahl gerade ist oder nicht, primitiv rekursiv sind. Fortsetzung nächste Seite! Frühjahr 2010 Einzelprüfungsnummer: 46113 Seite: 5 4. Entscheiden Sie, welche der folgenden Aussagen richtig und welche falsch sind und geben Sie jeweils eine kurze. Begründung für Ihre Antwort an. Unter einer totalen Funktion wird im Folgenden, wie üblich, eine auf allen Argumenten definierte Funktion verstanden. Jede u-rekursive totale Funktion ist primitiv rekursiv. Jede primitiv rekursive Funktion ist eine totale j-rekursive Funktion. Das Komplement jeder primitiv rekursiven Teilmenge M der natürlichen Zahlen ist primitiv rekursiv. (Eine Menge heißt primitiv rekursiv, wenn ihre charakteristische Funktion \ primitiv rekursiv j AEPIGL Ca 4 Das Komplement jeder entscheidbaren Teilmenge M der natürlichen Zahlen ist entscheidbar. Das Komplement jeder rekursiv aufzählbaren Teilmenge M der natürlichen Zahlen ist rekursiv aufzählbar.