. PrüfuagEtemitr Prüf,ulgsteilnebaer Eitzelplrifrugstrumer Kennzahl: 66rL2 Frühjahr Kennwort: 1998 Arbeitsplatz-Nr. Erste : St,aatsprüfung für ein Lehramt an öffentlichen Schulen Prüfungsaufgaben Facb,: (vertieft Informatik Einzelprüfung : Automatentheori gestellten Artzahl der Anzahl der Druckseit,en - , Komplexi tät , Algori Themen (Aufgaben) : dieser Vorlagre: Bitte studiert) wenden ! 2 6 th. r rLLnJ anr Lyeä sämtliche E]-nze,j pt:Lrrungsnr. : Thema Nr. 1 Teilaufgaben sind 66LL2 Seite: zu bearbeiten ! l. Man beweiseoderwiderlegefür SprachenLt,h. übereinemAlphabetE: a) Lt Gz Lr)* = (Lr b)*Lr b) (Lr^ b)* = Ll* ^b* c ) ( L r * ) *= L l * einesParsers. 2. SkizzierenSie AufbauundEigenschaften entscheidist dasLeerheitsproblem derChomsky-Hierarchie 3. Für welcheSprachenklassen bar?(Begnindungen!) 4, Wasverstehtman unter'lazy evaluation'? 5. Zeigensie,daß(x, y Lf ist. Paarfunktion Qy + 1)-l) eineprimitiv-rekursive Siediemit Prioritätenaq undbeschreiben 6. GebenSieeinenDatenfypfür Warteschlangen senumgangssprachlich. '1. sind für beliebigeWHllE-PrograrnmeP entscheidWelcheder folgendenEigenschaften bar?(Begründung!) a) b) c) d) P terminiertbei Eingabe0 (Null). P berechneteineprimitiv rekursiveFunktion. WHILE-Schleifen. P enthiilthöchstens3 ineinandergeschachtelte mit gibt Programm P' nur einerWHILE-Schleife. ein äquivalentes es ZuP Fortsetzung nächste Seite ! 2 t'runl anr L> > ö r.LIT.ZeLPI.t,tItlngSür . : 66 LLZ Sel-tre: (nachH. Pansch).(AbbildungBeispiel) E. AktualisiereneinerFlug-Informationstafel destination 8A947 | London - . . ' S R5 5 I Zürich LH253l Berlin r departure I I | 7.55 | 9.30 | 10.30 l 10.55 | delayed LH 4271 B r e m e n l t O . + S l t O . + S Gegebenist eine Liste von Einträgen.Ein Eintragkanneine l*eneile odereineFlug-Infoblle sein.Die Flug-rnfa-kilen sindnachAbflugzeitengeordnet. Die Aktualisierungsoll alle Flug-Info-kilen (wiederumgeordnet)an den Anfangder Liste undalle Leerzeilenrns Endebringen. Konstnriercn Sieein Programm,dasdie Aktualisierungsaufgabe löst. GebenSieinsbesondere eineformaleSpezifikation, geeignete Datenstnrkturen, sowiezur Vegeeignete rifikation Invariantenan. 4 J ErLIIzeLPILl.l.uJ'rgtilt.[ . : Thema Nr. sämtl j-che Teilaufgaben bbIJ_./ Ser-E,e: 4 2 sind. zrr bearbeiten t Auf gabe L: Gegebensei das AlphabetI = {0,1}, die Menge L = { O n 1 ^ | n > 0 , f r > 0 , u n dn + m i s t u n g e r a d e } von Zeichenreihenüber I sowie die Grammatikf mit X als Menge der Terminaizeichen, den Nichtterminalzeichen Z und A, dem Axiom Z undden Produktionsregeln Z + O Z + 1 Z+OA Z+1A Z+OOZ A+11 [+11A. a) Ist f mehrdeutig? BerveisenSie Ihre Behauptung. b) BeweisenSie: Für den Sprachschatz T(f) von f gilt: _f(f) = L. ^\ KonstruierenSie direkt aus f einennicht-deterministischen endlichenAutomaten.der genau dre Zeichenreihen von I akzeptiert. d) Geben Sie eine (deterministische)TuringmaschineM an. die außer einem Leerzeichen nur die Zeichen aus Z venvendet und I in folgendem Sinne akzeptiert: Angeserzt auf das erste Zeichen eines auf dem ansonstenieeren Band stehendenWortes lr€ I* erreicht M genaudann nach endlich vielen Schritten einen Endzustand.wenn ru e I isr. Aufgabe 2: Mit sequ integer sei im folgenden die Menge aller endlichen Folgen ganzer Zahlen bezeichnet. Für sequ integer seien als Grundoperationenverftigbar: empty:- sequinteger, isempry:sequinteger - boolean firsc sequrnteger-+integer, rest sequinteger - sequinteger. prefix: integerx sequinteger.+sequinteger, postfix:sequintegerx integer+ seguinteger, o: seguintegerx sequinteger+ sequinteger, empty = leere Folge ßemptlt{s) = ntte €3 sr ist leer - ", frrs,t(s,,...,srr) rest (s,,sr...,sr,)* (sr,...,srr) prefix: bc,(sr,...,"J)* (x,Sr,...,sr) postfir ((s,,...,srr),r)- (sr,...,srr,x) o: ((sr,...,sr,),(rr,...,t^)) r ("r r...rsrr,f',... rt ^) (für s = empty sind ,lirsr(s) und resr(s) nicht definiert. Die "Konkarenarion"o wird im folgendenin Infixschreibweiseverwendet.o ist assoziativ,d.h. es gilt uo(vow)=(uou)orp für alle u.v,w € sequinteger.) Fortsetzung nächste Seite ! Frührjahr L998 Einzelprüfungsrr. : 661L2 Seite: a) Berveisen Sie, daßfür beliebigex eintegerund.s.f€seguintegergilt: a1) prefidx,sor) = prefiAx.s)or. a2) postfix{s,x)or = .soprefix(x,r). Sei nun weiter a > 0 eine fest vorgegebene ganze Zahl. Für i = !,2,3 seien die Funktionen teil,: sequ integer -' sequ integer definiert durch: teil,(i = I u^pry, fails s = empty falis s+ empty und pr(frsr(s)) = trse, sonst, | nrefix(frsr(s),teil,(resr(s)), l, rcil,(resr(s)) wobei gilt: pr(x) = mte €c v . -etrr(x) = tnte e -eS x S a, pr(x) = true€ x > c. Die Funktion ordnen:sequ integer -+sequ integer sei definiert durch: ordnen(s) = rcilr(s) o reil.(s) o teilr(s). Außerdem sei foigende Funktionsvereinbarunggegeben: function ORDALL(S,u,lu:segu integer) sequ integer: if isemp-ty-(s) then vow rfEe if frsr(s) . :a üren prefi.x{frrsr(s) .oRDALL(rest(s),y,p)) [ -a s frrsr(s) n firsr(s)s a thenoRDALL(resr(s). posji*b.7trcr(s)).*,) efse ORDALL(resr(s),v,postfix{w, first(s))) endif endif b) Besrimmen Sie die werte von reil,(s), teilr(s), teil"(s). ord.nen(s)und oRD. LL(s.r,.u,) f l i r a = 5 , s = ( 2 . i . - 6 . 9 . - 3 , - 8 , 7r)=, ( 0 , 0 ) r l e = ( 1 , 1 ) . c) BerveisenSie. daß für alle s e sequinteger giit: ordnen( s) = ORDALL(s, emty,empty) . d) Aus ORDILL soli in systematischerWeise ein iterativer Algorithmus zur Berechnung von ordnen(s) flür aile s € sequ rnteger ennvickeit werden, der nur die angegebenen Grundoperationenverwendet. Betten Sie dazu 7RDALL in einen geeigneten allgemeineren repetitiv rekursivenAlgorithmus ein. und entrekursivierenund speziaiisieren Sie diesen zu dem gesuchteniterativen Algorithmus. Ifinweis: Venvenden Sie zur Formuiierung der Algorithmen eine programmiersprachenähnliche Notation. rvie sie enva zur Verein-barunguon Onbif verwendet ist. Fortsetzungr nächste Seite I 5 Frühjahr 1998 Einzelprüfungsnr. : 65LLz Seite: Auf gabe 3 : Durch die Funktionsvereinbarungen : functionF (n: nat)boolean i f n = 0 t h e nt r u e 0 n = 1 v n = 2 v n = 3 t l r e ni a l s e else G(n-l) ^ G(n-2) n G(n-3) endif, functionG h: nat)boolean: it n= 0 then false I n = 7 v n = 2 v n = 3 t h e nt r a e else F(n-l) v F(n-Z) v F(n-3) endif sind zrvei FunktionenF,G: No -{tnte.false} definiert. BerveisenSie, daßfür beiiebigesn € No gilt: a) F(n) terminiert. b) F(n) = tnne e ft ist durch4 teilbar. Auf gabe 4: Gegeben sei eine unendliche Teiimenge M von No und eine p-rekursive (,,berechenbare,,) Funktion g:No * N0, so daß für alle n e Nn gilt: neMo,g(n)=0. Durch die noch unvoilständige Definition f(n) = U,.(e(x)= 0), falls n= 0, f*(...?...). f a i l sn > 0 sei eine weitere Funktionf,No - No gegeben. BestimmenSie den unvollständigen Teil ...?...der Definitionvon f so, daß/folgende drei Ei genschaftenbesitzt: i) / ist p-rekursiv. ii) Für alle n e No gilt: /(n) . f(n*t). iii) Für alle n e No gilr: n e M o 3m(f(m) = n). BegründenSie Ihre fuitwortl Himreis: Der operator F- ist für (k+11-rt"llige (/c>0) prädikate p(x,,...,xk,x) definiert durch: Frh(x,,...,xk,x)) = y, falls p(x,,...,x.r,!)und nicht p(xr,...,xo,z)fi.ir0 s Gilt p(x1,...,xp,i)für kein 3 e Ne, so ist F_(p(x,,...,xrc,x)) undefiniert. z