Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 46 1 1 3 2000 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: 3 Bitte wenden! Herbst 2000 Einzelprüfungsnummer: 46113 Seite: 2 Thema Nr. 1 Aufgabe 1 Zur Darstellung einer Gleitkommazahl arbeiten wir mit dem Alphabet S = {°+", “-", °.‘, ’E‘, “0°,°17,°27,°3°,°4°,°5°,°6°,°7°,°8°,°9°}. Daraus bilden wir Zeichenketten A, .. ‚G e S’, die wir schließlich mit Hilfe der Verkettungsoperation ‘0° zu Gleitkommazahlen Z kombinieren: Z=AoBoCoDoEoFoG. Für die Zeichenfolgen A, .. , G gelten dabei die folgenden Bedingungen: Zeichenreihe |Länge / darf folgende Zeichen enthalten Einschränkungen A Oi = Er B Lei c 01l21 G 1,20 Zulässige Gleitkommazahlen wären damit etwa „+5“, „9.123“, „1298.222E+2“, „-2E2“. Nicht zugelassen sind dagegen z.B. „.12“, „E12“ oder „IE+*. Verwenden Sie in den folgenden Aufgaben als Abkürzung das Symbol t mit t < {“0’, .. , 9°}! a) L; CS’ sei die Sprache, die man durch Bildung aller möglichen Gleitkommazahlen gemäß der in obiger Tabelle angegebenen Regeln erhält. Zeigen Sie, dass L, vom Typ Chomsky-3 ist, indem Sie eine erzeugende rechtslineare Grammatik G dafür angeben! b) Zeichnen Sie das Zustands-Übergangsdiagramm eines endlichen Automaten, der L, akzeptiert! c) Geben Sie einen regulären Ausdruck für L, an! Fortsetzung nächste Seite! Herbst 2000 Einzelprüfungsnummer: 46113 Seite: 3 Aufgabe 2 Wir betrachten folgendes Programmfragment P (in Pascal-ähnlicher Notation): i:=1;f:=1; while i | an’ Dabeı soll die Zahl n in Binärform (höchstwertiges Bit links) ohne führende Nullen auf dem Band von TM dargestellt sein und der Schreib-Lesekopf anfangs auf dem höchstwertigen Bıt stichen. Nach der Berechnung dürfen führende Nullen auftreten. Außerhalb der Darstellung von n steht an allen anderen Stellen des Bandes das Leerzeichen “#’. b) Wenden Sie Ihre Turınemaschine zur Berechnung von pred(24) an! Geben Sie dabei tur alle Zwischenzustände jeweils die Bandbelegung und den Zustand von TM an! Herbst 2000 Einzelprüfungsnummer: 46113 Seite: 4 Thema Nr. 2 Aufgabe 1 Welche der folgenden regulären Ausdrücke a, beschreiben genau die Sprache, die der endliche Automat mit obigem Zustandsgraph akzeptiert? (Es kann mehrere solche Ausdrücke geben.) oO, = ba)*b o = bfa)*b(b)* % = — (b(a)*b(b)* | a(alb)*a(b)*) hy = b(a)*(b)* % = — bfa)*(b)*d Aufgabe 2 2.1 „Eine Sprache Z ist genau dann regulär, wenn Bedingung.“ Geben Sie vier verschiedene Bedingungen an, für die diese Aussage korrekt ist! 2.2 Gibt es drei Sprachen L,, L,, L, mitL, cl,cL,, so dass L, und L, vom Typ 2 (kontextfrei) sind, aber L, nicht? Geben Sie entweder drei solche Sprachen an oder einen Beweis, dass dies nicht méglich ist! Fortsetzung nächste Seite! Herbst 2000 Einzelprüfungsnummer: 46113 Seite: 5 Aufgabe 3 Ein Palindrom ist ein Wort, das vorwärts und rückwärts gelesen gleich ist, z.B. anna oder uhu. Das leere Wort ¢ ist auch ein Palindrom. Sei £ = {a, b} und sei Z die Menge aller Wörter über I, die Palindrome sind. 3.1 Geben Sie eine Grammatik G = (V, 2, P, S) an mit L = L(G)! 3.2 Beweisen Sie, dass L nicht regular ist! 3.3 Geben Sie eine deterministische Turingmaschine M = (Z, 2, T, 6, s, _, {e}) an, die genau die Palindrome über © akzeptiert, für die also T(M) = L ist! Dabei ist Z die Zustandsmenge, = = {a, b} das Eingabealphabet, [ = {a, b, _} das Bandalphabet, _ das Leerzeichen, s « Z der Anfangszustand, e e Z der Endzustand (hier reicht ein einziger) und ödie Überführungsfunktion. Geben Sie zu jedem von Ihnen verwendeten Zustand in Z eine informelle Erläuterung, welchem Zweck der Zustand dienen soll, etwa in folgender Form: „Zustand r,: nach rechts laufen bis Wortende, anschließend prüfen, ob Wort mit a endet“! 3.4 Geben Sie die Folge der Konfigurationen an, die M jeweils durchläuft für das Eingabewort aba, für das Eingabewort baab und für das Eingabewort abaa! Aufgabe 4 Sei = ein Alphabet. 4.1 Geben Sie die Definition dafür an, dass eine Menge L c >* rekursiv aufzahlbar ist! 4.2 Geben Sie die Definition dafür an, dass eine Menge Z < £* semi-entscheidbar ist! 4.3 Wie hängen die in den Teilaufgaben 4.1 und 4.2 definierten Eigenschaften zusammen? 4.4 Beweisen Sie: Sind Z, und Z, rekursiv aufzählbar, dann ist auch Z,VZ, rekursiv aufzählbar! 4.5 Beweisen Sie: Sind L, und Z, rekursiv aufzählbar, dann ist auch Z, NZ, rekursiv aufzählbar! Hinweis: Benutzen Sie den Zusammenhang zwischen rekursiv aufzählbar und semi-entscheidbar!