Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: 46 1 1 3 2001 Arbeitsplatz-) 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: > Bitte wenden! Frühjahr 2001 Einzelprüfungsnummer: 46113 Seite: 2 Thema Nr.1 1. a) Man gebe einen deterministischen Kellerautomaten an, der L = {a‘b*a| k > 1} akzeptiert. # sei das Kellerbodenzeichen, als weitere Kellerzeichen verwende man A, B, ..., die Zustände bezeichne man mit Z, Z,, ...; Z Sei der Anfangszustand. Die Überführungsfunktion schreibe man so: (Zustand z;, Eingabezeichen a oder b, oberstes Kellerzeichen) > (Zustand z,, das das oberste Kellerzeichen ersetzende Wort). b) Man gebe eine kontextfreie Grammatik für L an. c) Fragen: a) Ist auch der L, = {a‘b*a"|k, m > 1} deterministisch kontextfrei? B) Ist L, kontextfrei? Man gebe jeweils eine Begründung an. 2. SeiL, = {a'b"cln, m, k= 0, m = 0 oder k = 0} und L, = {ab n,m,k20,m=noderk=n}. a) Welche der zwei Sprachen ist regulär, welche nicht? b) Sind beide kontextfrei? Hinweis: Um zu zeigen, dass eine der Sprachen regulär ist, genügt es, einen regulären Ausdruck oder einen endlichen Automaten für die Sprachen anzugeben. Zum Nachweis der Nichtregularität können Sie statt des Pumping Lemmas auch Operationen auf regulären Sprachen verwenden, sowie die Tatsache, dass L, = {a'b"| n> 0} nicht regular ist. 3. Man betrachte die Grammatik G mit den Produktionen S— AS|AB| SS B>Cc A>a Coc a) Man vereinfache die Grammatik durch Verringerung der Zahl der Variablen (4, B, C). b) Man zeige, dass die erzeugte Sprache L(G) regulär ist — etwa durch Angabe eines regulären Ausdrucks oder eines akzeptierenden endlichen Automaten (mit Begründung). Fortsetzung nächste Seite! Frühjahr 2001 Einzelprüfungsnummer: 46113 Seite: 3 4. Man betrachte die allgemeine Chomsky-Grammatik G (Grammatik vom Typ 0) mit folgenden 6 Produktionen: (1) S>LaR (2) La > LB (3) Ba + aaB (4) BR > aaR (5) Loe (6)R € a) Welche Sprache (Teilmenge von {a}*) erzeugt G? Hinweis: Man betrachte zunächst nur die ersten 4 Produktionen (ohne die Löschproduktion für L und R) und gebe die Satzformen an, die kein B mehr enthalten und mit den obigen 4 Regeln erzeugt werden können. b) Ist diese Sprache kontextfrei? Frühjahr 2001 Einzelprüfungsnummer: 46113 : Seite: 4 Thema Nr. 2 1. Beantworten Sie die folgende Aussage mit ja oder nein! (kurze Begründung) (ab | a) * a ist mit a (ba Ja) * äquivalent 2. Zeigen Sie mit dem Pumping Lemma, dass die folgende Sprache L nicht regulär ist! L = {a’ba”ba”””: n,m2>1} 3. Sei L die Sprache {we {0,1} * : der Teilstring 011 ist nicht in w enthalten} a) Geben Sie das Zustandsdiagramm für einen endlichen Automaten an, der L akzeptiert! b) Geben Sie eine reguläre Grammatik G an, die L erzeugt! 4. Sei G = (V,L,R,S) eine kontextfreie Grammatik, wobei V = {a,b,A,S}, Y = {a,b} und die Menge R der Regeln oder Produktionen wie folgt gegeben ist: S aAS|a A SbA|SS|ba Geben Sie für das Wort aabbaa einen Parsebaum an! 5. Betrachten Sie die durch folgende Produktionen definierte kontextfreie Grammatik G mit den Regeln: aAB aBB a bCC b c. auu>>u Geben Sie für die Sprache L@ = {w ef{a,b,c}* : S >*,w} einen regulären Ausdruck an! Hinweis: L(G) sei die Menge aller Wörter, die nur aus Terminalsymbolen bestehen und die von der Grammatik G abgeleitet werden können. Fortsetzung nächste Seite! Frühjahr 2001 Einzelprüfungsnummer: 46113 Seite: 5 6. Ist die folgende Funktion f : {0,1,....9}* {0,1} rekursiv? Die Eingabe x wird als Dezimialzahl interpretiert. Es ist f(x) = 1 genau dann, wenn es in der Dezimaldarstellung von [] einen geschlossenen Block von mindestens x Siebenen gibt. Beweisen Sie Ihre Antwort. 7. Eine Turingmaschine (Einbandturingmaschine) M = (Q,I,T,8,s,h,#) wird durch @ (ii) (iii) (iv) vy) (vi) beschrieben. eine endliche Zustandsmenge Q ein endliches Eingabealphabet I ein endliches Arbeitsalphabet T, wo I