Prüfirngsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr Kennwort: 2000 66112 Arbeitsplatz-Nr.: Erste Staatsprüfungfür ein Lehramt an öffentlichen Schulen PrüfungsaufgabenFach: Informatik (vertieft studiert) Einzelprüfung: Automatentheorie,Komplexität,Algorith. Anzahlder gestelltenThemen(Aufgaben): 2 Anzahlder Druckseiten dieserVorlage: 7 Bitte wenden! Fnihjahr 2000 Einzelpnifungsnumm er: 66I 12 Seite:2 Thema Nr. 1 Sämtliche Teilaufgaben sind zu bearbeiten! VerwendenSie zur Beschreibungvon Algorithmen bzw. Datentypeneine imperativeProgrammiersprachewie PASCAL oder MODULA odereinenentsprechenden Alle anzugeben"Pseudocode". den Algorithmen, Programme,Grammatitenoder Automatenmüssendurch Kommentareerläutert werden. Die Qualität der Erläuterungenträgt wesentlichzur Bewertungbei. Einführung: ' Die folgendenAufgabensindunabh?lngig voneinander und sollenalle gelöstwerden.Sie beziehen sich auf einenDokumenttypnamensBericht, der wie folgt definiert ist: . Ein Beicht bestehtaus folgendenKomponentenin der gegebenenReihenfolge: - einemTitel. - einerAutorenliste (die aberoptional ist, also auchentfallenkarur), - einerZsammenfasyung, - einer nichtleerenund endlichenFolge von Kapiteln, c Eine Autorenüsreist eine nichtleereund endlicheFolge ton Namen. . Eine Zuammenfassungbestehtaus genaueinemAbsatz. t En Kapitel bestehtaus folgendenKomponentenin der gegebenenReihenfolge: - einemTitel, - einer nichtleerenund endlichenFolge von Absötzen. Das folgeirdeDokument ist vom Typ Bericht. Die Aufgaben2 und 5 beziehensich auf diesesBei soiel. Dokurnent Dokumentstruktur Bericht Autorenliste Name ffi Zusarnrnenfassung Absatz TiteI Kapitel Tsatz itel Kapitel atz atz -| -| --+ -+ -) -> -) The Computer in two Chapters Anton Ackermann Berta Bloch This report expiainsthe essentialsof computers. Hardware You might get it into your pocket. Software You might get it into your head. Can be pretty hard, too. Fortsetzuns nächsteSeite! Frühjahr2000 Einzelprüfungsnumm er: 66L12 Seite:3 Auf welche Weiseein Teiltext einesDokumentsvom übrigenText abgegrenztund eindeutigals eine der Dokumentkomponenten 7itel, Name oderAbsatzklassifiziert werdenkann, und welcheninneren Aufbau er dazuhabenmuss, spielt im Folgendenkeine Rolle. Die Aufgabenbehandelnnicht das Dokument, sonderndie Dokumentstruktur,die aufden Dokumentkomponenten Titel, Name und, Absatz atfbaut. Ab sofort werdendiesedrei Dokumentkomponenten mit t, n, a abgekirzt. Auf dieserBeschreibungsebene wird dasobige Dokumentdurchdie KomponentenfolgeTitet Name NameAbsatz Titel AbsatzTitel AbsatzAbsatzrepräsentiert,abgektirzttnnatataa. Also isr tnnatataaeine zulässigeKomponentenfolgefür Dokumentevom Typ Bericht. Dagegenist die Komponentenfolge nnntataafrir DokumentevomTyp Beicht nicht zulässig,da einBericht nach der obigenDefinitionmit einemZlrelbeginnenmuss. Aufgabe 1 GebenSie eineGrammatikG, in ErweiterterBackus-Naur-Form (EBNF) an, die genaudie zulässigen Komponentenfolgenfür Dokumentevom Typ Bericht erzetgt. Die Grammatiksoll so weit wie möglichder verbalenDefinitiondesDokumenttyps Berichtn der Einführungentsprechen. VerwendenSiedazudie Terminalsymb olet, n, a und die folgendenNichtterminalsymbole: ' Beicht, Autormliste, Zusammmfassung, Kapitel GebenSie särntlicheBestandteile der GrammatikG, vollständisan. Aufgabe 2 2.1 GebenSieeineGrammatikG, vom Typ 3 (regulär)an, die genaudie zulässigen Komponentenfolgen für Dokumentevom Typ Bericht ene:ugt. VerwenderiSie dazu die Terminalsymbole t, n, a. GebenSie sämtlicheBestandteile der GrammatikG, vollständigan. 2.2 Zeigen Sie, dassdie Komponentenfolgetnnantaa desBeispieldokuments in der Einführungvon der Grammatik G, erzeugtwird. Aufgabe 3 GebenSie einennichtdeterministischenendlichenAutomaten,{ an, der genaudie zulässigenKomponentenfolgenfür Dokumentevom Typ Bericht akzeptien. VerwendenSie dazudie Terminalsymbole t, n, a. 3.1 DefinierenSiedenendlichenAutomatenz4in Form einesDiagramms. 3.2 DefinierenSieden endlichenAutomatenin der Form,4 : 8, r,6, 2", El. GebenSiejedender Bestandteile Z, 2,6, zound E desAutomaten?4vollständigan und nennen Siejeweils seineBedeutung. FortsetzunsnächsteSeite! Frtihjahr2000 Einzelpnifungsnummer : 66ILz Seite:4 Aufgabe 4 Der Dokumenttyperweiterter-Berichlseidefiniertwie Bericht, aberzusätzlichkommtunmittelbar nach derZusammenfassung noch einInhaltsverzeichnis. Diesesbestehtausder Folge der Titel der KaptteldesDokuments.Das folgendeDokumentist vom Typ erweiterter-Bericht. Dokurnent Dokumentstruktur 'i,teI Bericht Autorenliste Name -f --> ffi Zusarnmenfassung Absatz + Inhaltsuerzeichnr,s Kapitel Kapitel itel TiteI M rlftel ffi satz -+ ---+ -) --> The Computer in two Chapters Anton Ackermann Berta Bloch This report explains the essentialsof computers. Hardware Software Ilardware You might get it into your pocket. Software You might get it into your head. Can be pretty hard, too. Die KomponentenfolgetnnatttataadiesesDokumentsist aiso zulässigfür Dokumentevom Typ erweiterter-Bericht. Allerdings hätteein Dokument, dessenInhaltsveneichnisdie Titel in einer anderen Reihenfolgeenthält,die gleicheKomponentenfolge. Auf der Beschreibungsebene der Komponentenfolgen ist dieserUnterschied nicht darstellbar.Die Komponentenfolge tnnaxataaist dagegen nicht zulässig,da darin zwei / vorkor nen, die an Kapitelngehören,abernur ein r, das zum Ingehörenkann.Die beidenAnzahlenmüsstenabergleich.sein. haltsverzeichnis Komponentenfolgen 4.1 BeweisenSie, dassdie Mengealler zulässigen für Dokumentevom Typ erweiterter-Beicftl nicht durch eine Grammatikvom Typ 3 (regulär) erzeugtwerden karur. FormulierenSie die Säueaus.die Ihr Beweisverwendet. 4.2 GebenSie eine Gramrratik vom Typ 2 (kontextfrei) an, die genaudie Menge aller zulässigen Komponentenfolgenfür Dokumentevom Typ erweiterter-Berichterueugt. Aufgabe 5 Es steheein DatentypKomponenternit folgendenOperationenzur Verfügung: liefert TRUE gdw. k ein Titel ist. istTitel(k:Komponente): BOOLEAN liefert TRUE gdw. k ein Nameist. istNameft:Komponente):BoolEAN istAbsatz(k:Komponente):BoolEAN liefert TRUE gdw. k ein Absatzist. Weiter steheein DatentypKomponentenfolgemit folgendenOperationenzur Verfügung: liefert TRUE gdw. f die leereKomponentenleer(f:Komponentenfolge):BOOlEAN folge ist. komponente1(f:Komponentenfolge):Komponente liefert die ersteKomponentein f; undefiniert falls f leer ist. liefert die Teilfolgevon fab der zweiten rest(f:Komponentenfolge):Komponentenfolge Komponente;undefiniert falls f leer ist. FortsetzunsnächsteSeiteI Frühjahr2000 Einzelpnifungsnumm er: 66L12 Seite:5 5- 1 Definieren Sie eine FunktionsprozeduranzahlTitelrek(f:Komponentenfolge):INTEcER,die die Anzahl der Titel in f rekursiv berechnet. 5.2 Definieren Sie eine Funktionsprozedurar:zahlTitel_iter (f : Komponentenfolge): INTEGER, die die Anzahl der Titel in f iterativ berechnet. 5 . 3 Elementedes DatentypsKomponentenfolgesollen als einseitigverketteteListen mit Verbunden und Verbundzeigernrepräsentiertwerden. GebenSie eine Definition des DatentypsKomponentenfolgefrir dieseRepräsentation an. DefinierenSie dazupassende Funktionsprozeduren für die angegebenendrei Operationenauf dem DatentypKomponentenfolge. 5 . 4 Unabhängigvon den obigen Vorgaben seienDatentypenTitel, Name und Abs atz gegeben,mit denen die entsprechendenKomponenteneines Dokumentsrepräsentiertwerden können. Definieren Sie einen DatentypBericht und alle weiterenbenötigtenDatentypen,um die gesamte Dokumentstruktur von Dokumentenvom Typ Bericht repräsentierenzu können. Die Definitionen sollen so weit wie möglich der verbalenDefinition des DokumentfypsBericht in der Einftihrung entsprechen.Halten Sie sich an die Konvention, dassBezeichnervon Typen mit Großbuchstabenanfangenund andereBezeichnermit Kleinbuchstaben. Sei bericht eine Variable des von Ihnen definierten DatentypsBericht, deren Wert die Strukrur des Beispieldokumentsin der Einflihrung repräsentiert.GebenSie einenAusdruck an, mit dem auf den erstenAbsatz des zweitenKapitelszugegriffenwird. 6 - Frtihjahr2000 Einzelpnifungsnumm er: 66L12 Seite:6 Thema Nr. 2 Sämtliche Teilaufgaben sind zu bearbeiten! 1. a) zeigen Sie,,dassdie folgendeSpracheL nicht regulär ist: L - { a n b a ' b a n * ' l n , * >1 } . b) Definieren Sie formal den Begriff einesKellerautomatens. c) BeschreibenSie einen KellerautomatenM, der die Sprache L - { a"ba'ban+mln,* > 1} akzeptiert. 2. Sei L die Sprache L - {* . {0,1}* | der Teilstring011 ist nicht in w enthalten}. a) Geben Sie das Zustandsdiagramman für einen endlichenAutomaten, der L akzeptiert. b) GebenSie eine reguläreGrammatikG an, die L erzeugt. c) Geben Sie einen regulärenAusdruck für die SpracheL an. 3. Sei G - (V,I,R,S) eine kontextfreieGrammatik,wobei V - {A,S}, I : {a,b} und R die Menge der Regeln oder Produktionen S -> A -+ aASla SbA I SSlba. Geben Sie einen Parsebaumund eine Linksableituns an für das Wort aabbaa. FortsetzungnächsteSeite! Frühjahr2000 Einzelpnifungsnummer : 66I12 Seite:7 4. BetrachtenSie die durch folgende Produktionendefinierte kontextfreie Grammatik G mit den Regeln: S A A B B C -> aAB + aBBC - + a -+ bCC - + b -+ c. '' GebenSie einenregulärenAusdruckfür die SpracheL(G) - {* e {a,b,c}* S = | o w} an; d.h. L(G) ist die Menge aller Wörter, die nur aus Terminalsymbolenbestehenund die von der Grammatik abgeleitetwerden können. 5- a) GebenSie eine genaueFormulierung des Pumping Lemmas für kontextfreie Sprachenan. b) Zeigen Sie mit dem Pumping Lemma, dassdie folgendeSprachenichr kontextfrei ist: { uu' l i , j € N , j : i t } . 6. Ist die folgendeFunktionF : {0,1,...,9}{<-> {0,1} rekursiv?Die Eingabex wird als Dezimalzahl interpretiert. Es ist f(x) - 1 genaudann, wenn es in der Dezimaldarstellungvon x einen geschlossenen Block von mindestensx Siebenengibt. BeweisenSie Ihre Antwort. 7 . a) Definieren Sie den Begriff einer kontextsensitiven Grammatik. b) Sei L - { anb*cnln,m2O,rnsn}. GebenSie einekontextsensitive Grammatikfür L an. c) GebenSie eine Ableitung des Worts a3b'c'mittels Ihrer Grammatikan.