Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: | Herbst A 61 1 3 2011 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: 6 Bitte wenden! Herbst 2011 Einzelprüfungsnummer: 46113 Seite: 2 Thema Nr. 1 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Aufgabe 1: reguläre Sprachen a) Formulieren Sie die Aussage des Pumping-Lemmas für reguläre Sprachen. Wie kann das Pumping-Lemma dazu verwendet werden, zu zeigen, dass eine Sprache nicht regulär ist? b) Beweisen Sie mit Hilfe des Pumping-Lemmas für reguläre Sprachen, dass die Sprache Lı = {a”b"a”b” |m > 1,n > 1} nicht regulär ist. Erläutern Sie Ihre Argumentation. c) Sei L eine reguläre Sprache. Sei n die Zahl des Pumping-Lemmas zu L. Beweisen Sie, dass folgende Aussage gilt: | L |= co & es gibt in Z ein Wort w mit n <| w |< 2n d) Begründen Sie, warum reguläre Sprachen unter Vereinigung. abgeschlossen sind. Betrachten Sie dazu zwei reguläre Sprachen ZL und M und begründen Sie, warum auch LUM eine reguläre Sprache ist. e) Sei A = (Q,2,6,90, F) ein deterministischer endlicher Automat, der eine reguläre Sprache L erkennt. Konstruieren Sie zu A einen deterministischen endlichen Automaten B, der die reguläre Sprache L = D* — L akzeptiert. Erläutern Sie die Funktionsweise des von Ihnen konstruierten Automaten. Fortsetzung nächste Seite! Herbst 2011 Einzelprüfungsnummer: 46113 Seite: 3 Aufgabe 2: kontextfreie Sprachen und Kellerautomaten a) Betrachten Sie die folgende Sprache Dy = {ab"a™b™ | m>1,n > 13 Geben Sie eine kontextfreie Grammatik mit Terminalsymbolen, Nichtterminalsymbolen und Produktionen an, die L, erzeugt. Erläutern Sie die Arbeitsweise der von Ihnen angegebenen Grammatik. b) Definieren Sie die Begriffe Linksableitung und Rechtsableitung einer kontextfreien Grammatik. Geben Sie für die von Ihnen in Aufgabenteil (a) konstruierte Grammatik eine Linksableitung für das Wort abaabb € Ly an. c) Kontextfreie Sprachen kénnen mit Hilfe von Kellerautomaten erkannt werden. Geben Sie eine mathematisch exakte Definition eines Kellerautomaten an. Erläutern Sie den Unterschied zwischen nicht-deterministischen und deterministischen Kellerautomaten. Welche Unterschiede in den Verarbeitungsschritten gibt es? d) Konstruieren Sie einen Kellerautomaten K = (Q,3,T, 6, 90, Zo, F), der die Sprache L, aus . Aufgabenteil (a) akzeptiert. Geben Sie eine mathematisch exakte Definition der Übergangsrelation d an. Erläutern Sie die Arbeitsweise des von Ihnen konstruierten Kellerautomaten K und begründen Sie, warum K alle Worte aus L, akzeptiert. Ist der von Ihnen konstruierte Kellerautomat deterministisch oder nicht-deterministisch? Begründen Sie, warum 1, durch einen deterministischen Kellerautomaten erkannt werden kann. e) Formulieren Sie die Aussage des Pumping-Lemmas für kontextfreie Sprachen. Erläutern Sie die Gültigkeit dieses Lemmas. Erläutern Sie, wie das Pumping-Lemma für kontextfreie Sprachen dazu verwendet werden kann zu beweisen, dass eine gegebene Sprache nicht kontextfrei ist. f) Betrachten Sie die folgende Sprache La = {a"b"a*b* |m > 1,n > 1}. Beweisen Sie mit Hilfe des Pumping-Lemmas für kontextfreie Sprachen, dass La nicht kontextfrei ist. Herbst 2011 Einzelprüfungsnummer 46113 Seite 4 Thema Nr. 2 (Aufgabengruppe) Es sind alle Aufgaben dieser Aufgabengruppe zu bearbeiten! Annahmen: Sie dürfen als bekannt und bewiesen voraussetzen: Die Sprache {a" b" c®| n> 1} ist nicht kontext-frei. Um zu zeigen, dass eine Sprache L regulär (bzw. konxtexfrei) ist, reicht die Angabe einer entsprechenden Beschreibung (Automat, Grammatik, Ausdruck). Sie müssen nicht mehr zeigen, dass Ihre Beschreibung korrekt ist und genau die vorgegebene Sprache beschreibt. Aufgabe 1: reguläre Mengen Sei L. die Menge aller Worte über dem Alphabet {0,1}, die eine durch vier teilbare Binärzahl ohne führende Nullen darstellen. a) Beschreiben Sie L durch einen regulären Ausdruck. b) Geben Sie eine vollständige Beschreibung eines deterministischen endlichen Automaten A für L an. c) Wenn Ihr Automat A nicht minimal ist, konstruieren Sie einen äquivalenten minimalen Automaten. d) Beschreiben und begründen Sie in Worten, warum der Automat aus Teilaufgabe 1 b bzw. 1 c minimal ist. Durch welche Figenschaft(en) wird ein minimaler Automat charakterisiert? Fortsetzung nächste Seite! Herbst 2011 Einzelprüfungsnummer 46113 | Seite 5 Aufgabe 2: deterministisch Konstruieren Sie zum folgenden Automaten einen äquivalenten deterministischen endlichen Automaten. Anfangszustand ist der Zustand 0, akzeptierende Endzustände sind 2 und 5: Aufgabe 3: regulär oder nicht L={we {ab,c}* | w=al bi ck mit ,j,k>0 und j=k} Ist die Sprache L regulär oder nicht? Begründen Sie Ihre Antwort. Aufgabe 4: Zeigen Sie, dass die Sprache L ={we {ab,c}* | w=al bi ck mit ,j,k>1 und (j=k oder i=j)} . kontextfrei ist. Es reicht die Angabe einer entsprechenden Grammatik bzw. eines Kellerautomaten. Fortsetzung nächste Seite! Herbst 2011 Einzelprüfungsnummer 46113 Seite 6 Aufgabe 5: a) Konstruieren Sie eine Turingmaschine für die Sprache ~L={u#v| uve {fab}* und u#v}. b) Welche Zeit-Komplexität hat Ihre Turingmaschine M? Welche Speicher-Komplexität hat Ihre Turingmaschine M? Aufgabe 6: NP Sei BE= {a | a ist ein erfüllbarer boolescher Ausdruck über “, v, -—, =>, <<, <>} Begründen Sie in Worten: a) BE istin NP. b)BE ist NP-vollständig. _ Hierzu darf nach dem Satz von Cook & Levin vorausgesetzt werden, dass das Erfüllbarkeitsproblem (SAT) NP-vollständig ist.