Prüfungs tei lnehmer Prüfungst,ermin Einzetprüf unslsnummer Kennzahl: Herbst 66110 Kennwort: 1997 ArbeitsplaEz-Nr. Erste : Staatsprüfung für ein Lehramt an öffentlichen Prüfungsaufgaben Fach: Einzelprüfung : Automatentheorie Anzah1 der gestellt,en Anzahl (vert,ief t Inf ormatik der Druckseiten , Argori thm. Themen (Aufgaben) : dieser Vorlage: Bitte studiert) wenden ! l_ 4 sprachen Schulen Herbst t997 Einzelprüfungsnr. sämtriche Teilaufgaben : 6G110 Seite: sind. zu bearbeiten ! 1- Aufgabe (Rechenstrukturen und Termersetzungssysteme) Gegebensei eine Rechenstruktur NAT mit der Signatur: f - (sxar, FNer) mit srya1 {bool, nat} und Fuar - {zero. succ, pred} Den beiden Sorten seien die folgendenTrägermengenzugeordnet: boolNAT : BL :: BU {I}, natNAT : Iy'r :: Iy' U {f } Dabei ist /f : {0, L,2,...} die Menge der natürlichen ZahTenund B {rRun, FALSE} die Menge der BooleschenWerte. Das Symbol r steht für,,undefiniert,,. Die Spezifikationender den Funktionssymbolen zero)succ und pred zugeordnetenstrikten Funktionen lauten: ="roNAT t --f _ o; ="toNAT "rr..NATr lvrr + /ft; "u..NAt(r) - u *1: -) predNAT : 1gr //t; predNAt(") x)IundpredNAT(0) :r Im folgendennehmen wir an, daß jede natürliche Zahl durch einen Grundterm darsestelit ist, der nur aus den Konstruktoren zero und succ besteht. //t; a) Geben Sie ein Termersetzungssystem an, das die Funktion pred auf die Konstruktoren zero und succ zurückführt! b) |trun sollen die strikten Funktionen add und sub mit den Spezifikationen addNAT , /fr x //r -) /ft; addNAT@,y) _ r * A subNAT: //ax.A/r -r /ft; subNAT@,y)- r-yfalls rly subNAT(r,y) - rfaiis r //t; -> //r: nultNAT(r,y) _ divNAT(r,y) _ divl{AT(r, o) x.y r +yfalls y > 0 r Sie dürfen dabei auch die Funktionen add, sub aus b) verwenden. Wir betrachten nun den seit dem Altertum bekannten EuklidischenAlgorithmus in der Notation einer imperativen Programmiersprache(orb seienvon der Sorte nat) (*) while albao while a < b do ö:-- ö - a od ( o , b ): - ( b , a ) od Fortsetzung nächste Seite t 2 Herbst L997 Einzelprüfungsnr. : 56LL0 Seite: 3 d) Stellen Sie einen exemplarischenAblauf des Algorithmus für die Variablenbelegung a : 32,ö - 18 als Folge von Zuständen des Variablenraumesdar. e) Der Algorithmus soll nun mit Hilfe der Zusicherungsmethodenach Floyd und Hoare verifiziert werden.Geben Siefür beide while-Schleifen geeigneteInvarianten an,und beweisenSie damit die Korrektheit des Algorithmus. Hinweis: Gehen Sie von der Zusicherung{P n a : rrlg A ö : ng A.n,m teilerfremd} mit P : a ) 0 A ö ) 0 vor Beginn der ersten while-Anweisung aus. f) Formulieren Sie den EuklidischenAlgorithmus rekursiv in einer beliebigenNotation. g) Geben Sie ein Termersetzungssystem auf der Rechenstruktur NAT für den Euklidischen Algorithmus an. Sie dürfen dabei alle in den Teilaufgaben a) mit c) auf NAT eingeführten Funktionen und Hilfsfunktionen verwenden. h) BeweisenSiedie Terminierung der beiden while--Schleifenin unsererursprünglichen Formulierung (*) des Euklidischen Algorithmus. 2. Aufgabe (Rekursive Rechenstrukturen) Gegebensei die rekursiveRechenstruktur Liste : Leer | (Float, Liste) der Listen über reellenGleitpunktzahlenmit den Funktionen o head: Liste -> Float o tail : Liste -->Liste . mklist : Float x Liste -> Liste Für diese Funktionen gelten folgende Spezifikationen: o head(x) und tail(r) sind partiell nur für nicht-leere Listen definiert, und head(r) ist das erste Element der Liste c, tail(r) ist die um das erste Element verkürzte Liste r. . mklist(r,x) ist total und liefert die Liste, die durch Voransetzendes Elementsr vor die Liste s entsteht. Die RechenstrukturListe soll nun um die folgendenFunktionen erweitert werden: o length : Liste + Int mit der Spezifikation:length(z) ist total und liefert die Anzahl der Elementein der Liste c. Fortsetzung nächste Seite t Herbst L997 Einzelprüfungsnr. : 56 j_l-0 Seite: 4 o proj : Int x Liste + Float mit der Spezifikation:proj(n,c) ist partiell nur für nicht-leere Listen c sowie für n mit 1 1 n 1 length(x) definiert und liefert das n-te Element der Liste c. o part : Int x Int x Liste + Liste mit der Spezifikation:part(m,n,r) ist partiell nur für nicht-leere.Listenu sowiefür rn und n mit I l m { n <- length(*) definiert und liefert die Teilliste von u vom m-ten bis zum n-ten Element einschließlich. 1' Programmieren Siedie 3 Funktionen length, proj und,parf rekursiv unter Abstützung auf die primitiven Rechenstrukturcn Int und ,Bool sowie auf die oben angegebene RechenstrukturListe. 2' BeweisenSie für das von Ihnen für die Funktion part angegebeneprogramm, (u) daß es für alle zulässigenparameter terminiert und (b) daß es die Spezifikationfür die Funktion part erfüllt. 3. Aufgabe (Endliche Automaten und reguläre Mengen) Gegebensei das Alphabet A: (A,B,C). In A* zeichnen wir die TeilmengeT der Wörter aus, die weder ACC noch BCC als Teilzeichenreiheenthalten. Dabei ist c € A* genau dann eine Teilzeichenreihe von y € A*, wenn es ein y' e A* und ein y,, €.4* gibt, ,o duß y - y'ry" ist. 1' Konstruieren Sie den (bis auf die Bezeichnungender Zustände eindeutigen) minimalen deterministischenendlichenAutomaten A - (5,1.,6,so,]l) mit der Zustandsmenge,S,dem EingabealphabetI - A., der Zustandsübergangsfunktion 6: ,.9x.I -r '9, dem Anfangszustandss und der EndzustandsmengeF, der genau T akzeptiert! Stellen Sie hierzu den Automaten A durch seinenZustandsübergangsgraphen dar. 2' BeweisenSie, daß der von Ihnen in der Antwort zu L angegebeneAutomat A (u) genau T akzeptiert und (b) minimal ist. 3. stellen sie T als eine reguläreMenge über A d,ar.