Pr{lfun3ttollnehme Prtllun3rtermln r Eln zelprtlf un 3 tnurrune r Kennzelrl: 66110 HERBST 1990 Kennwort: Arbeltrpletz-Nr. : Erste Staetrprüfung für eln Iahramt an öffentltchen Schulen Prüfungsaufgaben (vertleft rtudlert) Fach: Inforsratlk Elnzelprüfung: Autmstentheorle,Algorlthtn. Anzatrl der gestellten lbeloen Anzahl der Dnrckgelten (Aufgaben): dlerer Vorlage: spraehen I l sämtliche leilaufgaben sind zu bearbeilen! Teilaufqabe I M von Zeichenreihen Gegebensei das Alphabet A=lr,b,cl. Die Mengen M., Mb, M"und über Ä seien definiert durch Mr= (weAtl w = urxy mit u,veÄtl M = M.uMbuMc' für r = l, b bzw.c, al BeschreibenSie M durch einen regUlärenAusdnrck! bt a n , d e r g e n a ud i e Z e i c h e n - \ G e b e n s i e e i n e n d e t e r m i n i s t i s c h e ne n d l i c h e nA u t o m a t e n reihen von M akzePtiert! c) sprachschatzhat! Geben sie eine regutäre Grammatik an, die M ats Fortsetzunq nächste 5erte l ' rl l f r i l r g o I a r m l r tt l f o r b n t 1 9 9 0 - S o l t o2 i l l r z a l p r U f u r t g o r t u n n|o r6 6 1 l 0 Ieilaufoabe 2 G e g e b e ns e i d i e G r a m m a t i k f m i t l r . b l a l s M e n g e d e r T e r m i n a t z e i c h e nd, e n N i c h t t e r m i n a l z e i c he n Z , A , B , d e m A x i o m Z u n d d e n P r o d u k t i o n s r e g e l n ZaAB AqZA A + r 8+ZB B-+b a) Zeigen Sie. daß die Zeichenreihe rebbrbeb zum Sprachschatzvon F gehört! b) ÜberfUhren Sie I in die Greibach-Normalform! cl ) ellerautomaten 8r, der G e b e n S i e e i n e n ( g e g e b e n e n f a l l sn i c h t - d e t e r m i n i s t i s c h e n K genau den Sprachschatzvon I akzeptiertt Teilaufqabe J 4. Durch die Funktionsvereinbarung i functlon h( m,n:netlnrt: II m=0 thrn n dse 2'h(m-l'n) .: ; : ? ist eine Funktionh:Noz-No definiert' : : geweisen Sie ondif a) durch Berechnungsinduktion, (nachm)' b) durch Parameterinduktion gilt: daßfür alle m,neD''lo hlm.2tn) = 2'hlm,nl. ! a F o r t s e t , z u n on ä c h s t e S e i t e l l ' r U f o n g s t c r m l nH t o r b o t1 9 9 0 - Sclto t - Elnrclprtlfungsnurmcr r 661 leileufoabe 4 Durch die Funktionrvereinbantng lunctlonfln:nrt)net: lf ns2 tfrrn n rlro 2.f1n-l)+fln-31 rndlf ist eine FunktionftNo*No definiert. a) BeweisenSie, daßf flir atle neNo terminiert! b) Die Funktiont,Nof -No rei gegebendurch g(n,x,y,7)= r.fl n+21+yrfln+t) + 7,4flnl. BeweisenSie: = ',';::r1;ox+e.z,r), r(n,x,v,z) fil :::. c) EntwickelnSie mit Hilfe von b) zunächsteinenrepetetivrekursivenAtgorithmuszur n,x,!,ZeNounddarauseineniterativenAlgovon g(n,xg,Z) für gegebene Berechnung rithmus zur Berechnungvon flnl für gegebenesne hlo! wie PASCAL, Hinweis: FormulierenSie die Atgorithmenin einer Programmiersprache "Pseudocode",wie er in obiger FunktionsvereinMODU[A o.ä. oder in einem barungverwendetist! ' Teilaufoabe5 Für reR bczcichnclrl dic (eindcutigbcrtimmtclgenzcZahl a mit atr