Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frtihjahr Kennwort: 2001 66112 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen - PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie,Komplexität,Algorith. Anzahl der gestelltenThemen(Aufgaben): 2 Arzahl der DruckseitendieserVorlage: 7 Bine wenden! Früttjahr2001 Seite:2 er 66I L2 Eiruelpnifungsnumm Thema Nr. 1 SämtlicheTeilaufgabensind zu bearbeiten! Aufgabe 1 GegebenseidasAlphabetI : {0,1} und die Sprache 1 = {l 0r lj 0 I iundj sindgerade,i,j >0}. a) GebenSie einen regulärenAusdruck mit SpracheL an. b) GebenSie eine rechtslineareGrammatikan, die L erzeugt. AutomatenohneLeerübergänge,der die SpracheL c) KonstruierenSie einen nichtdeterministischen akzeptiert. d) KonstruierenSie einen minimalendeterministischenAutomaten,der L akzeptien. Aufgabe 2 Gegebensei die folgendeGrarnmatikG zur ErzeugungarithmetischerAusdrücke: c : ({E}, {a, b, +, *, (,)}, P, E} wobei p = {E -+ E+8, E -+ E*E, E -+ (E), E -r a, E -+ b}. a) GebenSie eineAbleitungfür denAusdruck(a+b)*(a*b) an. b) ZeigenSie, dassdie GrammatikG nicht eindeutig(dh. ambig)ist. wie G hat' c) Gesuchtist eine eindeutigeGrammatikG" die dieselbe.Sprache VervollständigenSie dzzu den folgendenAnsatzdurch Hirzunahne weiterer Produltionsregeln: G' = ({8, F, c}, {a, b, +, *, (,)}, P', E} wobei P ' = { E - + E * F , E - + F , . . . . . . . .} . FortsetzungnächsteSeite! Frtihjatrr 2001 Einzelprüfungsnumme r : 66I 12 Seite:3 Aufgabe 3 Beim Beweisder folgendenAufgabenist jeweils das Schemader primitiven Rekursionmit geeigneten primitiv rekursivenFunktioneng: N" --1 |rJrrndh: No*2-+ N anzuwenden. (N bezeichnetdabei die Menge der nattirlichenZahlen einschließlich0.) a) Zeigen Sie, dassdie folgendenFunktionenprimitiv rekursiv sind: iszero:N -+ N, iszero(O): l, iszero(x)- 0 falls x * 0. even:N -+ N, even(x)= I falls x gerade,even(x): 0 falls xungerade. case:N3 -+ N, case(x,y, z) = y falls x = 0, case(x,!, z) = z falls x * 0. b) ZeigenSie: Ist f: N -+ N primitiv rekursiv, dannist auchr: N2 -+ N mit r(x, r) : f(x) primitiv rekursiv. Dabei bezeichnetf die Identiüit und für i > 0 bezeichnetf die i-malige Hintereinanderausführung f(....f(x)...)von f. Aufgabe 4 dassdas folgendePrograrnmbezüglich der eingeBeweisenSie mit Hilfe der Zusicherungsmethode, fügten Zusicherungenpartiell korrekt ist. {n>o} i z::I; - 2"'^} {x > 0 nz x: WHILE x>0 DO z::2r2; x::x-l; END; {z - 2"1 FortsetzungnächsteSeite! Fnihjahr 2001 er: 66I L2 Efuzelprüfungsnumm Seite:4 Aufgabe 5 Die folgendenAufgabenkörmenin Pascal,Modula-2,C, C+ + oderJavagelöstwerden. a) Definieren Sie einenDatentyp(oder eine Klasse)mit Namen,Bin Tree" zur Darstellungbinärer Bäumemit garuenZahler' als Knotenmarkierungen. b) Ein binärer Baum t ist sortiert wenn t leer ist, oder wenn seineWurzel n größerals alle im linken Teilbaum I von t vorkommendenKnoten und kleiner gleich allen im rechtenTeilbaumr von t vorkommendenKnoten ist und wenn I und t ebenfallssortiert sind. ImplementierenSie eine OpebinärenBaumfeststellt,ob er soniertist. rationmit Namen.isSorted",die für einengegebenen c) ImplementierenSie eine Operationmit Namen,insert", die eine ganzeZahl x so in einenbinären Baumeinfligt, dassdiesernachAusführungder Operationwiedersortiertist. -5 Seite:5 r : 66tL2 Einzelprüfungsnumme Frütrjahr2001 ThemaNr. 2 SämtlicheTeilaufgabensind zu bearbeiten! Hinweis: VerwendenSiezur FormulietangvonAlgorithmenbzw.Datentypeneinegöngigehöhere AlErlöuternSiealle anzugebenden Pseu"docode. oder einenentsprechenden Programmiersprache gorithmenundAutomatenausgiebigdurch KommentareAufgabe 1 : seigegeben,wer mit wem Für einenicht-leereMengevon Personen - eng verwandt, weitläufig verwandt, bekarurt (aber nicht verwandt), weder verwandt noch bekannt ist. Davon ausgehendsollen folgendeAufgabengelöst werden: a) Für eine beliebigePersonsoll bestimmtwerden,mit wie vielen anderenPersonensie eng verwandtist. b) Es soll(en) diejenige(n)Person(en)nit den meistenBekanntenund weitläufig Verwandtenbestimmtwerden. c) Es soll festgestelltwerden,ob esdrei Personengibt, die untereinanderweder verwandtnoch bekannt sind. - sowie Personenbeziehungen GebenSie einengeeignetenDatentypzur Darstellungder gegebenen Algorithmen zur Lösung der Aufgabena), b) und c) an. Aufgabe 2 Gegebensei die Grammatikf mit der Menge {a, b} von Terminalzeichen,dem StartsymbolS als einzigemNicht-Terminalzeichenund den 4 Produktionsregeln S+a S+aS S+aSb S -+ bSa sowieder reguläreAusdruck R-a(aa*b*baaa*). FortsetzungnächsteSeite! er: 66112 Einzelprüfungsnumm Frtihjahr2001 Seite:6 Sprache.SchließlichseiI die Z(R) die durchR beschriebene I(f) sei die von f erzeugteSprache, über t., b), in denena öfter alsb vorkommt. Mengealler nicht-leerenZeichenreihen a) GebenSie eineAbleitung derZeichenreihe aababaaab in f an. Sie:t(R) 5 Zffl 9 L. b) Beweisen endlichenAutomatenan, der die SpracheI(R) akzeptiert. c) GebenSie einendeterministischen an, die t(R) 5 Produktionsregeln d) GebenSie einekontextfreieGrammatik(Typ 2) mit höchstens erzeugt. e) BeweisenSie, dassL keinereguläreSpracheist. an, der die SpracheL(f) akzeptiert. Kellerautomaten f) GebenSie einennichtdeterministischen an, die die SpracheI akzeptiert. Turingmaschine g) GebenSie einedeterministische Aufgabe3 Durch den rekursivenAlgorithmus F : function f (n, rn: nat)nat: if n