Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: : 46 1 1 3 2002 Arbeitsplatz-Nr.: Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen - Prüfungsaufgaben - Fach: Informatik (nicht vertieft studiert) Einzelprüfung: Theoretische Informatik Anzahl der gestellten Themen (Aufgaben): 2 Anzahl der Druckseiten dieser Vorlage: 4 Bitte wenden! Frühjahr 2002 Einzelprüfungsnummer: 46113 Seite: 2 Thema Nr. 1 Teilaufgabe 1 Für einen regulären Ausdruck R sei L(R) die durch R dargestellte Wortmenge. Im Folgenden sind jeweils Paare von Wortmengen über dem Alphabet {a,b} gegeben, die durch reguläre Ausdrücke sowie die Mengenoperationen N und — beschrieben sind. (Es ist W- V= {une W]| u& V};das+ in den regulären Ausdrücken wird in der Literatur manchmal ° auch als | geschrieben.) Man gebe jeweils an - mit Begründung -, ob die beiden Mengen gleich sind oder nicht und ob eine in der anderen erhalten ist. a) L(((ab)*(ba)*)*) und L ((abba)*) b) {a,b}*-L((aaa(a+b)*) und L((b+ab + aab + aaaa) (atb)* +e) c) L(a(atb)*) 1 L ((at+b)*b) und L (a(atb)*b) Teilaufgabe 2 Sei k eine feste natürliche Zahl (k = 0) und {a,b} ein Alphabet. Welche der folgenden Sprachen ist regulär, kontextfrei oder kontextsensitiv? Man gebe jeweils eine Grammatik oder einen akzeptierenden Automaten für die Sprache an - mit Begründung - sowie einen Beweis dafür, dass die Sprache nicht regulär bzw. nicht kontextfrei ist! a) {a*b™a*b™|m = 1} b) {a*a*b™b™|m = 1} c) {a"b™a"b™|n, m = 1} Fortsetzung nächste Seite! Frühjahr 2002 Einzelprüfungsnummer: 46113 Seite: 3 Teilaufgabe 3 Man untersuche die folgende rekursiv definierte Funktion: f= {2 für n<7 \f(f(ndiv8)+nmod8) sonst Dabei sei div die ganzzahlige Division ohne Rest, und mod liefert diesen Rest. a) Man berechne die Werte von f(n) für folgende Werte vonn: 8,11, 15, 16, 19, 83, 517 b) Man beweise: Für 0 < m, k <7 gilt m+k fir m+k<7 f(8m+k)=f(m+k)={™tk sonst c) Man beweise (mit vollständiger Induktion): Für n=Z ° 88+ 74° 88+... +21 °8+2Z mit z€E {0,1,..,7} gilt f(n) =f(f(£(........ f (2 + Ze) + Zz) +. +21) +2) d) Man gebe ein iteratives Programm (in einer abstrakten Programmnotation) an, das f (n) aus der Oktaldarstellung 2x Zx-ı Zx-2.... zı zo vonn berechnet. Man nehme an, die Ziffern der Oktaldarstellung liegen in einem Feld z[0], z[1], ..... z[k-1], z[k] vor und k sei ebenfalls gegeben. Man verwende b) und c) und begründe damit auch die Korrektheit des Programms! Frühjahr 2002 Einzelprüfungsnummer: 46113 Seite: 4 Thema Nr. 2 Teilaufgabe 1 Gegeben sei die Grammatik I’ mit der Menge {a, b} von Terminalzeichen, der Variablenmenge {S, A, B, C}, dem Startsymbol S und den Produktionsregeln S>a4AlbC|e A >aA|bB|bCle B>bCle Cad (e bezeichne das leere Wort.) £’ (I) sei die von I erzeugte Sprache. a) Geben Sie einen nicht-deterministischen endlichen Automaten an, der genau die Elemente von £ (T) akzeptiert. b) Beweisen oder widerlegen Sie: bl) baabba €E£(T) b2) Es gibt ein Wort von @ (I), das mit bb beginnt. b3) Kein Wort von 2’ (I) enthalt bbb als Teilwort. Teilaufgabe 2 Sei L = {a'b’ | i,j E No, i + 1