Prüfungsteilnehmer Prüfungstermin Einzelprüfungsmunmer Kennzahl: Herbst Kennwort: 200L 66LL2 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie,Komplexität,Algorith. Anzahlder gestellten Themen(Aufgaben): 2 Anzahlder Druckseiten dieserVorlase: 5 Bitte wenden! Herbst200L Einzelprüfungsnummer : 66112 Seite:2 Thema Nr. 1 Sämtliche Teilaufgaben sind zu bearbeiten! 1. Gegeben seidie Sprache L: {anb'cn ln > 0, m > 0} überX: {a b, c}. a) Ist L regulär?(Begründung!) b) Ist L kontextfrei?(Begründung!) (Begründung!) c) Ist L kontextsensitiv? d) Ist L entscheidbar?(Begründung!) 2. KonstruierenSie einenvollständigendeterministischenerkennendenAutomaten,der genaudie Wörter der Form anmit "n ist wederdurch4 noch durch 6 teilbar" akzeptiert. 3. DiskutierenSiedie Frage,ob die Menge 14: {x e N ] Die ZiffemfolgederDezimaldarstellung von x kommt (alsTeilwort)in der Dezimaldarstellungder Zahl n vor ) entscheidbar ist. (Beispiel:n = 3,141592... enthält159,aiso 159 e M) 4. Frir die Simulationder Stapelaigebramit WHllE-Programmen benötigtman eineFunktion code: N* -+ N, die endlicheFolgennati.irlicher Zahlencodiert.Seidurchstapel: [x1,...,x1] ein StapelnatürlicherZahlenmit oberstemElementx1 gegeben. (Hinweis:EinePaaa) DefinierenSieeinegeeignete Funktioncodeund erläuternSiecode(stapel) rungsfunktionist nützlich!). b) Berechnen Siecode([2,4]). c) GebenSie WHILE-Programmean, die die Stapel-Operationen etnpty,pwh, pop, top, isempty implementieren. 5. Nebender Turingnr.aschine mit einembeidseitigunendlichenBand gibt esaucheineVariante,die nur ein einseitig(nachrechts)unendlichesBand zur Verfügunghat. a) PräzisierenSie die Definition einer solchen"einseitigen"Twingrnaschinb. b) ZeigenSie die Aquivalenz der beidenVariantenvon Turingnaschinen. 6. SeiF die Formel(-(A + B) v - (- A v C)) n -.,A a) Ist F erfüllbar?@egründung!) b) Ist F eineTautologie?@egründung!) _ ? - Herbst2001 Seite:3 er: 66I 12 Einzelprüfungsnumm ThemaNr. 2 SämtlicheTeilaufgabensind zu bearbeiten! Hinweis: VerwendenSiezur Formulierung vonAlgorithmenbzw.Datentypeneinegängigehöhere AIgoPseudocode.Erläutern Sie alle anzugebenden Programmierspracheoder einenentsprechenden rithmen undAutomatenausgiebigdurch Kommentare. TeilaufgabeI JedesSpielwird von "Nimm'LSpielengeltenfolgendegeneinsameSpielregeln: Für eineKlasse,/V von 2 SpielemI und "Bmit Spielsteinenauf einemSpielbrettgespieltund begirmtin einerAnfangsstellung,in der n > 0 Spielsteineauf dem Brett stehen.I und.Bmachender Reihenachabwechselnd jeweils einenSpielzug,wodurchsicheineFolgevon Nachfolge-Stellungen als Spielablauferg1bt. A 3 verschiedene Spielzüge machtdenerstenSpielzug.In jederStellungstehenjedemSpielerhöchstens zur Verfügung.JederSpielzugverringert die Anzahl der Spieisteineauf dem Brett. JedeStellungist charakterisiertdurch die Angaben, - welcherSpieleramZug ist, - wievieleSpielsteineauf demBrettstehen, - ob I oder B gewonnenhat oder ob noch kein Spielergewormenhat. Ein Spielabiaufendet,wenn ein Spielergewonnenhat oderwenn keine Spielsteinemehr auf dem Brett stehen.Die LängeeinesSpielablaufsist die Anzahl der dabeidurchgeführtenSpielzüge. Regeln(überArt derSpielzüge,Art der JedesSpielderKlasse,{ definiertdurchseinezusätzlichen u.a.) eine Menge .S aller seiner möglichar Spielabläufe. Gewinnstellungen GebenSie einengeeignetenDatent)? zur DarstellungderartigerMengen,SsowieAlgorithmen ar, die für einederartigeDarstellungeinesSpielsfolgendeAufgabenlösen: a) Bestimmungder maximal auftretendenLängeeinesSpielablauß. b) Bestimmungder Anzahl der Spielabläufe,in denender SpielerI gewinnt. c) Klärung der Frage,ob eseinenSpielablaufgibt, in demeine Stellungerreichtwird, in der alle möglichenSpielfortsetzungenirgendwannzum GewirmdesSpielersftihren, der geradenicht am Zue ist. FortsetzungnächsteSeite! Herbst2001 Einzelprüfungsnunrmer : 66lLz Seite:4 Teilaufgabe 2 Gegebensei das Alphabet I : {0, I } und Z - {w e I* | * :0 oderw beginntmit dem Zeichen1}. Jedesw: wm... w2wlrro e Z kann als Binärdarstellungder natürlichenZahl 1V(r) : wm2- + ... + wz22+wt2 I wo aufgefasstwerden.Umgekehrt gibt es zu jedem n e Ns eine derartigeBinäirdarstellung W(") e Z (d.h.:N(W(")) - n.) Weiter sei die Grammatik G - (V,2, P, S) mit Z: {S,A} und der Menge P der Produktionen S+111A A+1l1Al0S gegeben. {(q sei die von G erzeugleSprache. a) Geben Sie eine reguläre Grammatik (Typ 3) an, die Z erzeug!. b) GebenSie eine Ableitung der Zeicheweihe 11101011011 in G an. c) BeweisenSie:.C(G)g Z. d) BeweisenSie:Fia jedesw e !(Q ist.ly'(w)ungerade. akzeptiert. e) GebenSieeinendeterministischen endlichenAutomatenan,derdie Sprache.4(G) f) Ist die Menge {n e Ne I W(n) e t(G)} entscheidbar? BegründenSie Ihre Anrwort. Sei nun N c Ne die Mengealler nattirlichenZahlen n : 2P2c- 1 mitp > 3 und 0 < q