P1-WS04-MusterLoesung02.txt
Zur Navigation springen
Zur Suche springen
Musterlösung Blatt 2 (P1, [[WiSe]] 04/05) Özgür Özcep Aufgabe 1 --------- Ad a) und c) <tag> ::= ( [('0'|'1'|'2')]('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9') ) | '3'('0'|'1') <monat>::= (['0']('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | '1'('0|'1'|'2'|) <jahr>::= (('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'){('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')}) <datum> ::= <tag> '.'<monat>'.'<jahr> In einer einzigen Regel formuliert: <datum>::= ( (['0']('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | (('1'|'2')('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | '3'('0'|'1'))'.' ((['0']('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')) | '1'('0|'1'|'2'|))'.' (('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9'){('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')}) Anmerkung: Mit der angegebenen EBNF für Datumsangaben werden auch faktisch nicht mögliche Termine wie "31.04.2004" erzeugt. (--> Korrektheit nicht erfüllt!?) Ebenfalls unbedacht sind die Schaltjahre. Nicht erfasst werden: 1. Datumsangaben in anderen natürlichen Sprachen wie z.B. im Englischen; 2. "unvollständige" bzw. "grobe" Datumsangaben wie "Im Jahre 1992". (--> Vollständigkeit nicht erfüllt!); 3. Datumsangaben des Typs "12. Dezember 1999" mit einer natürlichsprachlichen Monatsangabe. Ausgeschlossen wird eine Datumsangabe der Form "Der 35. Mai" (Titel eines Erich Kästners Buches), obwohl dieses als eine Datumsangabe verstanden werden könnte. (Probleme bereitet dann allerdings die Semantik dieses Ausdrucks, ähnlich der Problematik für Eigennamen von fiktiven Gegenständen: "Pegasus","Die Büchse der Pandorra" etc.) Ad b) gsed 's/\(\([012]\?[0-9]\|3[01]\)\.\(0\?[1-9]\|1[012]\)\.[0-9]\+\)/<date> \1 <\/date>/g' spenden.txt > spenden.anno Aufgabe 2 (Rekursive Einbettung) -------------------------------- Ad a) [1] <atomares element> ::= (<alphanum. Zeichen>){<alphanum. Zeichen>} [2] <alphanum. Zeichen> := <Buchstabe>|<Ziffer> [3] <Buchstabe>::= 'A' | 'B' | 'C' | .... 'Z' | 'a' | ... | 'z' [4] <Ziffer> ::= '0' | '1' | ... | '9' [5] <einfache Menge> ::= '{' {<atomares Element>', '} <atomares Element> '}' | '{ }' "Testen" der Vollstndigkeit und Korrektheit: - Ableitung der leeren Menge: Regel 5 - Ableitung für { a,b,c }: <einfache Menge> -->[5] '{' {<atomares Element>}, } <atomares Element>'}' -->[Def. Wdh.] {<atomares Element>, <atomares Element>, <atomares Element>} --> 3 mal [1] {<alphanum. Zeichen>, <alphanum. Zeichen>, <alphanum. Zeichen>} --> 3 mal [2] {<Buchstabe>, <Buchstabe>, <Buchstabe>} --> 3 mal [3] {a, b, c} Legende: uxw -->[R] uyw bedeutet: Die rechte Seite entsteht aus einer Anwendung der Regel mit der Regelnummer R auf x (mit y als Ergebnis). Ad b) Füge zu obigen Regeln hinzu: [6] <Menge> ::= '{' {(<Menge>|<atomares Element>)', '} (<atomares Element>|<Menge>) ' }' | '{ }' - Ableitung für {{a,b}, c, d} <Menge> -->[6] '{' {(<Menge>|<atomares Element>), } (<atomares Element>|<Menge>) ' }' -->[Def. Wdh.] '{'(<Menge>|<atomares Element>), (<Menge>|<atomares Element>), (<Menge>|<atomares Element>)'}' -->[Def. Alternative] '{'<Menge>, <atomares Element>, <atomares Element>'}' -->[6] '{''{' {(<Menge>|<atomares Element>), } (<atomares Element>|<Menge>) ' }' , <atomares element>, <atomares Element>} --> [Def. Wdh.] '{''{'(<Menge>|<atomares Element>), (<Menge>|<atomares Element>)'}',<atomares element>, <atomares Element>'}' -->[Def. Alternative] '{''{'<atomares Element>, <atomares Element>'}', <atomares Element>, <atomares Element>'}' --> 4 mal [1],[2] und Def. der Alternative {{a, b}, c, d} Aufgabe 3 (Prologanfragen) -------------------------- ad a) und b) Script started on Mon Oct 25 13:56:30 2004 [wsv9:Aufgaben[[/Blatt02/Vorlagen_Blatt02]]] oessi% swipl Welcome to SWI-Prolog (Multi-threaded, Version 5.2.0) Copyright (c) 1990-2003 University of Amsterdam. SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http://www.swi-prolog.org for details. For help, use ?- help(Topic). or ?- apropos(Word). ?- consult(familie). % familie compiled 0.00 sec, 2,204 bytes Yes ?- listing(vater_von)UTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENTUTF8_REPLACEMENT. :- dynamic vater_von/2. vater_von(otto, hans). vater_von(otto, helga). vater_von(gerd, otto). vater_von(johannes, klaus). vater_von(johannes, andrea). vater_von(walter, barbara). vater_von(walter, magdalena). Yes ?- listing(mutter_von)?- listing(mutter_von). :- dynamic mutter_von/2. mutter_von(marie, hans). mutter_von(marie, helga). mutter_von(julia, otto). mutter_von(barbara, klaus). mutter_von(barbara, andrea). mutter_von(charlotte, barbara). mutter_von(charlotte, magdalena). Yes ?- mutter_von(barbara,klaus) % Ist Barbara die Mutter von Klaus? Yes ?- vater_von(otto,gerd). % Ist Otto der Vater von Gerd? No ?- vater_von(X,andrea). % Wer ist der Vater von Andrea? X = johannes ; No % Andrea hat keinen weiteren Vater ?- mutter_von(X,marie). %Wer ist die Mutter von Marie? No ?- vater_von(otto,X). % Welche Kinder hat Otto? Hier wird vorausgesetzt, % dass Otto nicht Mutter sein kann; % ansonsten hätte man % zu fragen: % ?-vater_von(otto,X);mutter_von(otto,X). X = hans ; X = helga ; No % Wer hat welche Kinder: ?- vater_von(X,Y). X = otto Y = hans ; X = otto Y = helga ; X = gerd Y = otto ; X = johannes Y = klaus ; X = johannes Y = andrea ; X = walter Y = barbara ; X = walter Y = magdalena ; No ?- mutter_von(X,Y). X = marie Y = hans ; X = marie Y = helga ; X = julia Y = otto ; X = barbara Y = klaus ; X = barbara Y = andrea ; X = charlotte Y = barbara ; X = charlotte Y = magdalena ; No % Alternativ hätte man eine einzige Anfrage mithilfe % von ';' stellen koennen: % ?- vater_von(X,Y);mutter_von(X,Y). % Ad c)?- assert(vater_von(bert,lisa)). Yes?- asserta(mutter_von(lisa,anna)). Yes ?- assertz(mutter_von(lisa,moritz)). Yes ?- listing. % Was hat sich in der Datenbasis getan? % Foreign: rl_read_init_file/1 :- dynamic vater_von/2. vater_von(otto, hans). vater_von(otto, helga). vater_von(gerd, otto). vater_von(johannes, klaus). vater_von(johannes, andrea). vater_von(walter, barbara). vater_von(walter, magdalena). vater_von(bert, lisa). % Foreign: rl_add_history/1 :- dynamic mutter_von/2. mutter_von(lisa, anna). mutter_von(marie, hans). mutter_von(marie, helga). mutter_von(julia, otto). mutter_von(barbara, klaus). mutter_von(barbara, andrea). mutter_von(charlotte, barbara). mutter_von(charlotte, magdalena). mutter_von(lisa, moritz). Yes ?- halt. [wsv9:Aufgaben[[/Blatt02/Vorlagen_Blatt02]]] oessi% exit exit Script done on Mon Oct 25 14:00:56 2004 ad c) Die Fakten werden der Datenbasis hinzugefügt. asserta fügt das Faktum an den Anfang und assertz ans Ende der Datenbasis an. assert ist ein Alias auf assertz. Aufgabe 4) (Dirk Knoblauch) --------------------------- Beispiel: Übungsgruppen Ein Beispiel sind die Informationen zu den Übungsgruppen P1 letzten Jahres: uebungsgruppe(di,12,14,d125a,chen). uebungsgruppe(di,12,14,f132,wiegreffe). uebungsgruppe(di,14,16,d125a,koethe). uebungsgruppe(di,14,16,f132,wiegreffe). uebungsgruppe(fr,10,12,f132,dreschler). uebungsgruppe(fr,12,14,f132,stelldinger). uebungsgruppe(mi,8,10,f132,knoblauch). uebungsgruppe(mi,10,12,f132,knoblauch). uebungsgruppe(mi,12,14,d129,finck). uebungsgruppe(mi,12,14,f132,chen). uebungsgruppe(mi,14,16,f535,schmidtke). uebungsgruppe(mi,16,18,f535,obendorf). uebungsgruppe(fr,10,12,d125a,foth). Beispielanfragen: 1. Welche Übungsgruppen gibt es? 1 ?- uebungsgruppe(Tag,Anfang,Ende,Raum,Leitung). Tag = di Anfang = 12 Ende = 14 Raum = d125a Leitung = chen ; Tag = di Anfang = 12 Ende = 14 Raum = f132 Leitung = wiegreffe ; Tag = di Anfang = 14 Ende = 16 Raum = d125a Leitung = koethe ; Tag = di Anfang = 14 Ende = 16 Raum = f132 Leitung = wiegreffe ; Tag = fr Anfang = 10 Ende = 12 Raum = f132 Leitung = dreschler ; Tag = fr Anfang = 12 Ende = 14 Raum = f132 Leitung = stelldinger ; Tag = mi Anfang = 8 Ende = 10 Raum = f132 Leitung = knoblauch ; Tag = mi Anfang = 10 Ende = 12 Raum = f132 Leitung = knoblauch ; Tag = mi Anfang = 12 Ende = 14 Raum = d129 Leitung = finck ; Tag = mi Anfang = 12 Ende = 14 Raum = f132 Leitung = chen ; Tag = mi Anfang = 14 Ende = 16 Raum = f535 Leitung = schmidtke ; Tag = mi Anfang = 16 Ende = 18 Raum = f535 Leitung = obendorf ; Tag = fr Anfang = 10 Ende = 12 Raum = d125a Leitung = foth ; No 2. Welche finden in d129 statt? 1 ?- uebungsgruppe(Tag,Anfang,Ende,d129,Leitung). Tag = mi Anfang = 12 Ende = 14 Leitung = finck ; No 3. Welche Übungen führt Herr Knoblauch durch? 1 ?- uebungsgruppe(Tag,Anfang,Ende,Raum,knoblauch). Tag = mi Anfang = 8 Ende = 10 Raum = f132 ; Tag = mi Anfang = 10 Ende = 12 Raum = f132 ; No 4. Gibt es am Mittwoch eine Übungsgruppe von Herrn Obendorf? 1 ?- uebungsgruppe(mi,Anfang,Ende,Raum,obendorf). Anfang = 16 Ende = 18 Raum = f535 ; No