Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: 1999 66L12 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen - PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie,Komplexität,Algorith. Anzatrlder gestelltenThemen(Aufgaben): z Anzahlder DruckseitendieserVorlage: 5 Bitte wenden! Frtihjah 1999 Einzelprüfungsnumrne r : 66tI2 Seite:2 fhema Nr. L Sämtliche Teilaufgaben sind zu bearbeiten! Teilaufgabe 1: In dieser und den foigendenAufgaben geht es um die Kiassed.ersog. regulüren Sprachen, also der Sprachenvom Typ 3 in der Klassifizierung von Chomsky. a) Geben Sie eine genaueDefinition der Klasse der regulären Sprachenan und erläutern Sie die darin vorkommendenBegriffe. für dieseKlasseder regulären b) Es gibt mehrereäquivaienteBeschreibungen verwendenkönnte): als Definitionen ebensogut (die also Sprachen man Zählen Sie solcheweiteren Beschreibungenauf, die Sie kennen. Erläutern Sie ggf. die verwendetenBegriffe. c) Unter welchen Operationen auf Sprachen ist die K1asseder regulären Sprachen abgeschlossen?Zählen Sie die Ihnen bekannten auf. d) Welche Hilfsmittel kennen Sie, um die l{icht-Regularität einer formaien Sprachenachzuweisen.Erläutern Sie dies an einem Beispiel Ihrer Wahl. e) In welchen Bereichender Informatik haben reguläre Spracheneine praktische Bedeutung? Erläutern Sie solche Anwendungen, wenn möglich unter Angabe reievanterAlgorithmen (in Pseudocode)- Teilaufgabe 2: In dieserAufgabe werden Sprachenüber dem Aiphabet f : {0, 1} betrachtet. Für ein Wort tl _ luour...?rnn € I* bezeichne(*), die Interpretation von T.r'als Binärdarstellung einer natürlichen Zahl, wobei das führende Bit links steht: ( * ) , : u ) o 2 ^1 u r 2 ^ - r * I rxrn-r2' + u*20 (N.8. es wird nicht vorausgesetzt, dass tuo - 1 ist, d.h. es sind beiiebigviele führende Nullen erlaubt). Für n,k € N mit 0 < k < n sei m o d ( n, k ) , - { w € t * ; ( u ) 2 = k (modn)} die Spracheder BinärdarstellungenderjenigenZahlen,,die kongruent zuk modulo n sind. a) Konstruieren Sie einen endlichen Automaten, der die Sprachemod(5, 0) erkennt. Wie erhält man darausdie endlichenAutomaten, die die Sprachen mod(5,,k)mit 1 S fr ( 4 erkennen? b) Formulieren Sie eine allgemeineAussageüber die Erkennbarkeit der Sprachen mod(n, k) durch endlicheAutomaten. SkizzierenSie einen.Beweis. Fortsetzung nächste Seite! Frühjatrr 1999 Einzelpnifungsnumm er 66I 12 Seite:3 Teilaufgabe 3: In dieserAufgabe werden Sprachenüber dem Alphabet I - {o,,b} betrachtet. Für ein Wort u € I* bezeichnelu.'1,(bzw. lrlu) die Anzahl der Vbrkommen von o (bzw'. ö) in dem Wort tr. Betrachten Sie die Sprachen C p : :{ , e X - ; l u l " : l . l o n , r r - u . *u l l u l o -l " l r S l t } ( k> 1 ) D :: {to e I-; ltr[._ l.la] Offenbar veilt CtCCzCCeC...CD u n d l i m f , r , 4 * C -t p a) ZeigenSie, dass die SprachenCr (k > 1) regulär sind. b) Konstruieren Sie endliche Automaten, die die Sprachen Ct bzw. akzeptieren. Cz c) Zeigen Sie, dassdie SpracheD nicht regulär ist. d) Zu welcher Sprachklassegehört die Sprache D? Ntit welchem Typ von "Automaten" kann man die SpracheD erkennen? (Auf beide Fragen ist natürlich eine möglichst stark eingegrenzteAntwort erwünscht). -4 Frähjahr 1999 Eirzelprüfungsnumme r : 66IL2 Seite:4 Thema Nr. 2 SämUicheTeilaufsabeü sind zu bearbeiten! Teilaufgabe 1: GebenSiepnrzritiv rehtrsive Terme für die Funktionenin a) - e) an: a) Die Fakultätsfirnktion/ (x) = ;1. b) Die Funkrion even nllt even(x):{ x gerade ' ä äLT ( l,wen:rx>0 c) Die Signumfunktionsig mit sig(x) : t 0 ,onrt y, O = U' d) DieFunktion casemit case(x, . : O ä"# e) Die ganzzstrlige Division div rrrrtöv(x, y) = k genaudrnn, wennk * y + m = x, wobei m 2 und das vorletzteZeichenvon c ist ein a}. a) BeschreibenSie K durch eine reguläreMenge. b) Geben Sie eine Typ-3-Grammatik G mit dem Sprach.schatz K an und zeigenSie,dassL(C) = K gilt. c) Geben Sie einen (evtl. nichtdeterministischen) endlichenAutomaten M mttT(M):K an. d) Geben Sie einen deterministiscbenKellerautomatenM an mit l/(M) {o'nb; n € Ni. Fortsetzung nächste Seite! Frütrjahr 1999 Einzelprüfungsnurlmer : 66LLz Teilaufgabe3: Programmieren Sie in einer imperativen Programmiersprache Ihrer Wahi nach folgenden Angaben: schreiben sie eine Funktion Tag, d\ebestimmt, d.erwievielte Tag nach dem letzten Februartag eines Jahres zwischen 1900 und 2099 Osters-onntagist. Dies lässt sich mit dem folgenden verfahren ermittein: - g sei das Ergebnis der ganzzabligen Division d.er Jahreszahl j (1900< j<2099)durch4. - a sei der Rest der gatzzahrigen Division von j durch 1g. - b sei der Rest der ganzzahligen Division von (204 - 11 * a) durch 30. Falls b:28 oder ö = 2g ist, so ist mit b = 2T bzw. b - 2g weiterzurechnen. - c sei der Rest der ganzzahligen Division von (j * g * ö - 13) durch z. Das Ergebnis ist dann 28 + b - c. schreiben sie ein programm, das eine natürlicheZahll mit 1900 < j < 2099 einiiest, nach Ü-berpnifung auf korrekte Eingabe rnit lIilfe der Funktion Tag und, einer Prozedur Catum das Datum des Ostersonntags des Jahres bestimmt und d.asErgebnis ausgibt. Das Datum sei dabei in d.er Prozedur dargestellt durch ,*.i Al-rrgabeparameter t und m (2.8. t - 7 und m = Bfür den z. M:i"rz) Teilaufgabe4: Ein Firmengebäude hat 140 Räume. Es gibi ein Verzeichnis aller B"äume, in dem für jeden Raum folgende Angaben gemacht werden: r Raumkennung, bestehend aus eiaem Zeichen (r.8.'E' für Keiler) und einer natürücher Zahl, für Erdgeschoss,'K' r Größe in Quadratmetern (als neAf -ZahI), r Angabe, ob der Raum einen Telefona:rschlusshat, r Marcimale Anzahl der Personen, die in diesem Raum arbeiten können (Nu11,wenn es sich um einen Lagerraum bandelt), r Aktuelle Anzahl d.er Personen.dje in diesem Raurn arbeiten. Progrnmmieren Sie in einer imperativen ProgremmierspracheIhrer Wahl nach foigenden$ngaben: a) Geben Sie geeigneteDatenstrukturen Raumund Raumverzeichnis an. b) Geben Sie eine Prozedur an, die das Raumverzeichnis verändert, wenn einem neuen Mitarbeiter ein Raum zugeteilt wird, wobei man in einem Parameter angeben kann, ob man einen Raum mit oder ohne Telefonanschiusshaben will. Beachten Sie dabei, dass die ma:rimale Personenanzahl pro Raum nicht überschritten wird. Der erste passendeRaurn kann gewäi.bltwerden. Sie können annehmen, dassein solcher Raum vorhanden ist. c) Geben Sie eine F\-rnktion an, die die Gesamtgröße aller Lagerräume in Quadratmetern ermittelt. Seite:5