Datenstrukturen DCG Grammatiken

Tutorial IOperationen auf Datenstrukturen II Bäume DCGs und Semantik II

Tutorial IOperationen auf Datenstrukturen II Bäume DCGs und Semantik II

BäumeRepräsentation von Mengen durch binäre Bäume: Eine häufige Anwendung von Listen ist es Mengen von Objekten zu repräsentieren. Ein Nachteil eine Liste zur Mengenrepräsentation zu benutzen ist, dass das Testen von Mitgliedschaft relativ ineffizient ist.

Prädikat member:

member(X,[X|Rest]) :- !.member(X,[Y|Rest] :- member(X,Rest).

Für lange Listen sehr ineffizient, weil man u.U. erst durch die ganze Liste durch muss.Zur Repräsentation von Mengen gibt es verschiedene Baumrepräsentationen, die effizienteren Zugriff erlauben.

Repräsentation von Mengen durch binäre Bäume: Eine häufige Anwendung von Listen ist es Mengen von Objekten zu repräsentieren. Ein Nachteil eine Liste zur Mengenrepräsentation zu benutzen ist, dass das Testen von Mitgliedschaft relativ ineffizient ist.

Prädikat member:

member(X,[X|Rest]) :- !.member(X,[Y|Rest] :- member(X,Rest).

Für lange Listen sehr ineffizient, weil man u.U. erst durch die ganze Liste durch muss.Zur Repräsentation von Mengen gibt es verschiedene Baumrepräsentationen, die effizienteren Zugriff erlauben.

Bäume

Ein Binärer Baum ist leer oder er besteht aus drei Dingen:root, linker Teilbaum, rechter Teilbaum

Root kann alles sein aber die Teilbäume müssen wieder binäre Bäume sein!

Ein Binärer Baum ist leer oder er besteht aus drei Dingen:root, linker Teilbaum, rechter Teilbaum

Root kann alles sein aber die Teilbäume müssen wieder binäre Bäume sein!

Bäume

Bäume

Eine mögliche Repräsentation eines binären Baumes:

atom nil repräsentiert den leeren Baumfunctor t mit root X, linkem Teilbaum(subtree) L und rechtem Teilbaum R.

t(t(t(nil,1,nil),3,t(nil,4,nil)),5,t(t(nil,6,t(nil,7,nil),8,t(nil,9,nil)))

Eine mögliche Repräsentation eines binären Baumes:

atom nil repräsentiert den leeren Baumfunctor t mit root X, linkem Teilbaum(subtree) L und rechtem Teilbaum R.

t(t(t(nil,1,nil),3,t(nil,4,nil)),5,t(t(nil,6,t(nil,7,nil),8,t(nil,9,nil)))

Bäume

Jetzt Membership Relation in einem Baum T: in(X,T) ist wahr wenn

Wurzel von T ist X oder X ist im linken Subbaum von T oder X ist im rechten Subbaum von T

Jetzt Membership Relation in einem Baum T: in(X,T) ist wahr wenn

Wurzel von T ist X oder X ist im linken Subbaum von T oder X ist im rechten Subbaum von T

Bäume

Die Membership Regeln übersetzen sich direkt in Prolog:

in(X,t(_,X,_)).in(X,t(L,_,_)) :- in(X,L).in(X,t(_,_,R)) :- in(X,R).

Beachte: in(X,nil) ergibt fail für jedes beliebige X.

Die Membership Regeln übersetzen sich direkt in Prolog:

in(X,t(_,X,_)).in(X,t(L,_,_)) :- in(X,L).in(X,t(_,_,R)) :- in(X,R).

Beachte: in(X,nil) ergibt fail für jedes beliebige X.

Bäumein(X,t(_,X,_)).in(X,t(L,_,_)) :- in(X,L).in(X,t(_,_,R)) :- in(X,R).

Betrachten folgenden Baum

in(X,T) ergibt durch backtracking:X = a, X = b, X = c, X = d.

in(X,t(_,X,_)).in(X,t(L,_,_)) :- in(X,L).in(X,t(_,_,R)) :- in(X,R).

Betrachten folgenden Baum

in(X,T) ergibt durch backtracking:X = a, X = b, X = c, X = d.

a

d

cb

Bäume

Effizienz:in(a,T) ist unmittelbar erfolgreichin(d,T) muss mehrmals rekursiv aufgerufen werdenin(e,T) fail, erst nachdem der gesamte Baum traversiert ist!

=> die Baumrepräsentation ist fast genauso ineffizient wie die Implementation mit Listen.

Effizienz:in(a,T) ist unmittelbar erfolgreichin(d,T) muss mehrmals rekursiv aufgerufen werdenin(e,T) fail, erst nachdem der gesamte Baum traversiert ist!

=> die Baumrepräsentation ist fast genauso ineffizient wie die Implementation mit Listen.

BäumeEine Verbesserung ergibt sich durch die Ordnung der Menge

Ein nicht-leerer Baum t(Left,X,Right) ist von links nach rechts geordnet, wenn:

(1) alle Knoten im linken Teilbaum Left sind kleiner X(2) alle Knoten im rechten Teilbaum Right sind grösser X(3) beide Teilbäume sind ebenfalls geordnet

Der Vorteil ist: bei einem Suchaufruf genügt es für jeden Aufruf einen der Teilbäume zu durchsuchen. Der Schlüssel hierzu ist, durch Vergleich mit X kann sofort einer der Teilbäume vernachlässigt werden.

Eine Verbesserung ergibt sich durch die Ordnung der Menge

Ein nicht-leerer Baum t(Left,X,Right) ist von links nach rechts geordnet, wenn:

(1) alle Knoten im linken Teilbaum Left sind kleiner X(2) alle Knoten im rechten Teilbaum Right sind grösser X(3) beide Teilbäume sind ebenfalls geordnet

Der Vorteil ist: bei einem Suchaufruf genügt es für jeden Aufruf einen der Teilbäume zu durchsuchen. Der Schlüssel hierzu ist, durch Vergleich mit X kann sofort einer der Teilbäume vernachlässigt werden.

BäumeSuche nach 6:Suche nach 6:

Bäume

Finde ein Objekt im geordneten Binärbaum:

wenn X der Wurzelknoten(Root) ist: X ist gefundenwenn X kleiner Root: Suche im linken Teilbaumwenn X größer Root: Suche im rechten Teilbaumwenn der Baum leer ist, fail.

Finde ein Objekt im geordneten Binärbaum:

wenn X der Wurzelknoten(Root) ist: X ist gefundenwenn X kleiner Root: Suche im linken Teilbaumwenn X größer Root: Suche im rechten Teilbaumwenn der Baum leer ist, fail.

Bäumein(X,t(_,X,_)).in(X,t(Left,Root,_) :- gt(Root,X), in(X,Left).in(X,t(_,Root,Right) :- gt(X,Root),in(X,Right).

wie gross ist nun die Verbesserung: wenn der Baum balanciert ist, d.h. für jeden Knoten im Baum beherrschen seine Teilbäume in etwa die gleiche Anzahl von untergeordneten Teilbäumen so ist die Surchkomplexität die Höhe des Baumes: log n. Unbalanciert ist sie n, genauso schlecht wie die Liste.

Siehe Bratko in Kapitel 9 zur Ergänzung:

Einfügung und Löschung im sortierten Baum

in(X,t(_,X,_)).in(X,t(Left,Root,_) :- gt(Root,X), in(X,Left).in(X,t(_,Root,Right) :- gt(X,Root),in(X,Right).

wie gross ist nun die Verbesserung: wenn der Baum balanciert ist, d.h. für jeden Knoten im Baum beherrschen seine Teilbäume in etwa die gleiche Anzahl von untergeordneten Teilbäumen so ist die Surchkomplexität die Höhe des Baumes: log n. Unbalanciert ist sie n, genauso schlecht wie die Liste.

Siehe Bratko in Kapitel 9 zur Ergänzung:

Einfügung und Löschung im sortierten Baum

Syntax und SemantikBedeutung natürlicher Sprache."Defining the meaning of natural language is an extremely difficult problem that is the subject of ongoing research. An ultimate solution to the problem of formalizing the complete syntaz and meaning of a language like English is far away" Bratko, 2xxx

=> modelliert werden also zumeist einfache Teilsprachen oder bestimmte Aspekte der Semantik von Sprache, die einer unmittelbaren Anwendung dienen. Jüngeres Beispiel ist die Faktenextraktion, wo natürlichsprachlicher Text geparst, semantisch interpretiert und dann mit einer Ontologie gematcht wird.

Bedeutung natürlicher Sprache."Defining the meaning of natural language is an extremely difficult problem that is the subject of ongoing research. An ultimate solution to the problem of formalizing the complete syntaz and meaning of a language like English is far away" Bratko, 2xxx

=> modelliert werden also zumeist einfache Teilsprachen oder bestimmte Aspekte der Semantik von Sprache, die einer unmittelbaren Anwendung dienen. Jüngeres Beispiel ist die Faktenextraktion, wo natürlichsprachlicher Text geparst, semantisch interpretiert und dann mit einer Ontologie gematcht wird.

Syntax und SemantikDie erste Frage, wenn man die Bedeutung natürlicher Sprache mithilfe eines Computerprogramms verarbeiten will ist: wie wird Bedeutung repräsentiert.

- use case driven: Traditionelles Beispiel ist die Datenbankabfrage und das Datenbankupdate: "natürlichsprachliches Datenbankinterface" Stichwort aus den 80er Jahren- Logik ist als ein guter Kandidat zur Repräsentation der Bedeutung natürlicher Sprache akzeptiert worden - hohe Zahl von aus Anwendungssicht gescheiterten Implementationsversuchen in den 1980er Jahren.

Die erste Frage, wenn man die Bedeutung natürlicher Sprache mithilfe eines Computerprogramms verarbeiten will ist: wie wird Bedeutung repräsentiert.

- use case driven: Traditionelles Beispiel ist die Datenbankabfrage und das Datenbankupdate: "natürlichsprachliches Datenbankinterface" Stichwort aus den 80er Jahren- Logik ist als ein guter Kandidat zur Repräsentation der Bedeutung natürlicher Sprache akzeptiert worden - hohe Zahl von aus Anwendungssicht gescheiterten Implementationsversuchen in den 1980er Jahren.

Syntax und Semantik

Im Folgenden wird gezeigt, wie einfache natürlichsprachliche Sätze in ihrem logischen Gehalt mithilfe einer angereicherten DCG Notation konstruiert werden können.-> logische Interpretationen werden als Prologterme kodiert.

Im Folgenden wird gezeigt, wie einfache natürlichsprachliche Sätze in ihrem logischen Gehalt mithilfe einer angereicherten DCG Notation konstruiert werden können.-> logische Interpretationen werden als Prologterme kodiert.

Syntax und SemantikStartpunkt: wir schauen einige natürlichsprachliche Sätze und Phrasen an und versuchen mithilfe von Logik auszudrücken, was sie bedeuten.

John paints.

Als Prolog Term, ausgedrückt in Prädikatenlogik:

paints(john). paints ist ein intransitives Verb, deshalb hat das entsprechende Prädikat nur ein Argument.

John likes Annie.

likes(john,annie). likes ist ein transitives Verb mit zwei Argumenten

Startpunkt: wir schauen einige natürlichsprachliche Sätze und Phrasen an und versuchen mithilfe von Logik auszudrücken, was sie bedeuten.

John paints.

Als Prolog Term, ausgedrückt in Prädikatenlogik:

paints(john). paints ist ein intransitives Verb, deshalb hat das entsprechende Prädikat nur ein Argument.

John likes Annie.

likes(john,annie). likes ist ein transitives Verb mit zwei Argumenten

Syntax und SemantikEntwickeln jetzt eine DCG Grammatik, welche die Bedeutung dieser einfachen Sätze umfasst.

Zunächst Syntax:

sentence --> np,vp.np --> en.vp --> v_intrans.vp --> v_trans, np.

v_intrans --> [paints].v_trans --> [likes].en --> [john].en --> [annie].

Entwickeln jetzt eine DCG Grammatik, welche die Bedeutung dieser einfachen Sätze umfasst.

Zunächst Syntax:

sentence --> np,vp.np --> en.vp --> v_intrans.vp --> v_trans, np.

v_intrans --> [paints].v_trans --> [likes].en --> [john].en --> [annie].

Syntax und SemantikBedeutung einführen: zuerst einfach, dann komplexere Strukturen. Bottomup-Konstruktion der Semantik. Frege-These: die Bedeutung komplexer Strukturen(Satz) lässt sich aus der Bedeutung einfacherer Strukturen(der Konstituenten) zusammensetzen.

Bedeutung des Eigennamens john: john.

en(john) --> [john].

Die Bedeutung wird einfach als Argument zurückgegeben, wenn man beim Parsen auf ein Terminal trifft - wie beim Syntaxbaum

Bedeutung einführen: zuerst einfach, dann komplexere Strukturen. Bottomup-Konstruktion der Semantik. Frege-These: die Bedeutung komplexer Strukturen(Satz) lässt sich aus der Bedeutung einfacherer Strukturen(der Konstituenten) zusammensetzen.

Bedeutung des Eigennamens john: john.

en(john) --> [john].

Die Bedeutung wird einfach als Argument zurückgegeben, wenn man beim Parsen auf ein Terminal trifft - wie beim Syntaxbaum

Syntax und Semantik

Bedeutung des Eigennahmes john: john.

en(john) --> [john].

Bedeutung des intransitiven Verbs:

paints(X) mit X als Variabler, welche nur mithilfe des Kontexts instantiert werden kann.

v_intrans(paints(X)) --> [paints].

Bedeutung des Eigennahmes john: john.

en(john) --> [john].

Bedeutung des intransitiven Verbs:

paints(X) mit X als Variabler, welche nur mithilfe des Kontexts instantiert werden kann.

v_intrans(paints(X)) --> [paints].

Syntax und SemantikWie kann nun aus diesen Strukturen die Bedeutung des kompletten Satzes: john paints abgeleitet werden?aus john und paints(X) muss also der prädikatenlogische Term paints(john) werden.

Das Argument X in der Bedeutung des intransitiven Verbs (paints(X)) muss mit der Bedeutung seiner zugehörigen np unifizieren.

Propagation der Bedeutung von Phrasen: zuerst np und vp,wie beim Aufbau von Baumstrukturen.

np(NP) --> en(NP).vp(VP) --> v_intrans(VP).

Wie kann nun aus diesen Strukturen die Bedeutung des kompletten Satzes: john paints abgeleitet werden?aus john und paints(X) muss also der prädikatenlogische Term paints(john) werden.

Das Argument X in der Bedeutung des intransitiven Verbs (paints(X)) muss mit der Bedeutung seiner zugehörigen np unifizieren.

Propagation der Bedeutung von Phrasen: zuerst np und vp,wie beim Aufbau von Baumstrukturen.

np(NP) --> en(NP).vp(VP) --> v_intrans(VP).

Syntax und SemantikJetzt bleibt nur übrig, die Bedeutung des ganzen Satzes in der Variable S zusammenzubauen.

sentence(S) --> np(NP),vp(VP), {compose{NP,VP,S}.Das Ziel compose muss die Bedeutungen der np john und der vp paints(X) zusammenführen.

Wir sagen, X ist der Aktor in paints(X).actor(VP,Actor). So dass Actor der Handelnde in der Bedeutung VP der Verbalphrase ist. Eine Klausel der Prozedur actor ist dann z. B.

actor(paints(X),X).

jetzt kann die Komposition definiert werden:

compose(NP,VP,VP) :- actor(VP,NP).

also ist der Handelnde in der VP die Bedeutung der NP und die Bedeutung der instantiierten VP ist die des Gesamtsatzes.

Jetzt bleibt nur übrig, die Bedeutung des ganzen Satzes in der Variable S zusammenzubauen.

sentence(S) --> np(NP),vp(VP), {compose{NP,VP,S}.Das Ziel compose muss die Bedeutungen der np john und der vp paints(X) zusammenführen.

Wir sagen, X ist der Aktor in paints(X).actor(VP,Actor). So dass Actor der Handelnde in der Bedeutung VP der Verbalphrase ist. Eine Klausel der Prozedur actor ist dann z. B.

actor(paints(X),X).

jetzt kann die Komposition definiert werden:

compose(NP,VP,VP) :- actor(VP,NP).

also ist der Handelnde in der VP die Bedeutung der NP und die Bedeutung der instantiierten VP ist die des Gesamtsatzes.

Syntax und Semantik

Kompaktere Methode: Wir vermeiden das actor und das compose Prädikat.

Müssen das Argument X im Term paints(X) von aussen sichtbar machen => zugreifbar für die Instantiierung.Wie machen wir das? X freistellen.

Im Terminal:v_intrans(Actor,paints(Actor)) --> [paints].

Auslieferung an die VP:vp(Actor,VP) --> v_intrans(Actor,VP).

Kompaktere Methode: Wir vermeiden das actor und das compose Prädikat.

Müssen das Argument X im Term paints(X) von aussen sichtbar machen => zugreifbar für die Instantiierung.Wie machen wir das? X freistellen.

Im Terminal:v_intrans(Actor,paints(Actor)) --> [paints].

Auslieferung an die VP:vp(Actor,VP) --> v_intrans(Actor,VP).

Syntax und SemantikDamit kann jetzt Actor über die Unifikation belegt werden =>Belegung auch im Argument für die Satzsemantik der VP

sentence(VP) --> np(Actor), vp(Actor,VP).

Actor Argument der VP Bedeutung wird mit der Bedeutung der NP belegt. Bedeutungsschnipsel werden als Skelette implementiert. Die fehlenden Bedeutungsteille werden durch Unifikation eingebracht.Zuerst werden sichtbare Slots gefüllt, dann die Bedeutung der Phrase selbst.

Damit kann jetzt Actor über die Unifikation belegt werden =>Belegung auch im Argument für die Satzsemantik der VP

sentence(VP) --> np(Actor), vp(Actor,VP).

Actor Argument der VP Bedeutung wird mit der Bedeutung der NP belegt. Bedeutungsschnipsel werden als Skelette implementiert. Die fehlenden Bedeutungsteille werden durch Unifikation eingebracht.Zuerst werden sichtbare Slots gefüllt, dann die Bedeutung der Phrase selbst.

Syntax und SemantikAnwendung der Technik auf transitive Verben:

Bedeutung des Verbs likes: likes(Somebody,Something), mit Somebody und Something als Bedeutungsslots, die von aussen, Subjekt_np und Objekt_np belegt werden müssen.

v_trans(Somebody,Something,likes(Somebody,Something) --> [likes].

Die Verbphrase enthält nun eine Objekt_np, die den Wert für Something bereitstellt. vp(Somebody,VP) --> v_trans(Somebody,Something,VP), np(Something).

Anwendung der Technik auf transitive Verben:

Bedeutung des Verbs likes: likes(Somebody,Something), mit Somebody und Something als Bedeutungsslots, die von aussen, Subjekt_np und Objekt_np belegt werden müssen.

v_trans(Somebody,Something,likes(Somebody,Something) --> [likes].

Die Verbphrase enthält nun eine Objekt_np, die den Wert für Something bereitstellt. vp(Somebody,VP) --> v_trans(Somebody,Something,VP), np(Something).

Syntax und SemantikKomplizierter sind Phrasen, die Determinatoren enthalten (nicht umsonst vorher np--> en, die einfachste np).

Im Folgenden, Bedeutung von a und every

Beispiel: a man paints.Ein grober Fehler wäre es zu denken, der Satz bedeutet paints(man).Der Satz bedeutet:

There exists an X such that X is a man and X paints.

Komplizierter sind Phrasen, die Determinatoren enthalten (nicht umsonst vorher np--> en, die einfachste np).

Im Folgenden, Bedeutung von a und every

Beispiel: a man paints.Ein grober Fehler wäre es zu denken, der Satz bedeutet paints(man).Der Satz bedeutet:

There exists an X such that X is a man and X paints.

Syntax und SemantikIn der Logik sagt man, die Variable X sei existenzquantifiziert (there exists).In Prolog könnte man wie folgt repräsentieren:

exists(X, man(X) and paints(X)).

Im ersten Argument des Terms befindet sich ein X das existenzquantifiziert werden soll. 'and' wird als Infix Operator definiert:

:- op(100,xfy, and).

Die syntaktische Entität, die diese logische Interpretation transportiert ist der Determinator 'a'. Man kann sagen, 'a' dominiert den gesamten Satz.

In der Logik sagt man, die Variable X sei existenzquantifiziert (there exists).In Prolog könnte man wie folgt repräsentieren:

exists(X, man(X) and paints(X)).

Im ersten Argument des Terms befindet sich ein X das existenzquantifiziert werden soll. 'and' wird als Infix Operator definiert:

:- op(100,xfy, and).

Die syntaktische Entität, die diese logische Interpretation transportiert ist der Determinator 'a'. Man kann sagen, 'a' dominiert den gesamten Satz.

Syntax und SemantikEinfacheres Beispiel zum Verständnis des Determinators:a man: die Bedeutung ist Es existiert ein X so dass X ein Mann ist.In Sätzen in denen die Phrase 'a man' erscheint, wollen wir immer zusätzlich etwas über diesen Mann aussagen, nicht nur dass er existiert, sonder auch dass er z.B. malt. Damit ergibt sich als Form zum Transport der Bedeutung:

exists(X, man(X) and Assertion).wobei Assertion irgendeine Aussage über X ist. Diese Aussage hängt am Kontext => an der vp welche der np 'a man' folgt. Die Variable Assertion wird erst dann instantiert, wenn der Kontext in welchem sie erscheint bekannt ist.

Einfacheres Beispiel zum Verständnis des Determinators:a man: die Bedeutung ist Es existiert ein X so dass X ein Mann ist.In Sätzen in denen die Phrase 'a man' erscheint, wollen wir immer zusätzlich etwas über diesen Mann aussagen, nicht nur dass er existiert, sonder auch dass er z.B. malt. Damit ergibt sich als Form zum Transport der Bedeutung:

exists(X, man(X) and Assertion).wobei Assertion irgendeine Aussage über X ist. Diese Aussage hängt am Kontext => an der vp welche der np 'a man' folgt. Die Variable Assertion wird erst dann instantiert, wenn der Kontext in welchem sie erscheint bekannt ist.

Syntax und SemantikJetzt Bedeutung des Determinators a:

Es existiert ein X, so dass X eine bestimmte Eigenschaft hat ( z.B. man(X)) und eine weitere Zusicherung (Assertion) zu X besteht (z.B. paints(X)).

In Prolog:exists(X,Property and Assertion).

Die beiden Variablen, Property und Assertion sind Slots für die Bedeutung die aus dem Kontext eingebracht werden. Damit müssen wieder bestimmte Teile der Bedeutung von 'a' sichtbar gemacht werden.

determiner(X,Prop,Assn,exists(X,Prop and Assn)) --> [a].

Jetzt Bedeutung des Determinators a:

Es existiert ein X, so dass X eine bestimmte Eigenschaft hat ( z.B. man(X)) und eine weitere Zusicherung (Assertion) zu X besteht (z.B. paints(X)).

In Prolog:exists(X,Property and Assertion).

Die beiden Variablen, Property und Assertion sind Slots für die Bedeutung die aus dem Kontext eingebracht werden. Damit müssen wieder bestimmte Teile der Bedeutung von 'a' sichtbar gemacht werden.

determiner(X,Prop,Assn,exists(X,Prop and Assn)) --> [a].

Syntax und Semantik

Definition des Determinators every in ähnlicher Weise. 'Every woman dances' mit der logischen Interpretation:

für alle X,wenn X eine Frau ist, dann tanzt X.

Wir repräsentieren dies mit dem folgenden Prologterm:

all(X,woman(X) => dances(X)).

wobei => ein Infix Operator ist, der die logische Implikation bezeichnet.

Definition des Determinators every in ähnlicher Weise. 'Every woman dances' mit der logischen Interpretation:

für alle X,wenn X eine Frau ist, dann tanzt X.

Wir repräsentieren dies mit dem folgenden Prologterm:

all(X,woman(X) => dances(X)).

wobei => ein Infix Operator ist, der die logische Implikation bezeichnet.

Syntax und Semantik

Skelett eines Determinators mit der Bedeutung von every:

all(X,Property => Assertion).

DCG Regel für every mit sichtbaren Slots.

determiner(X,Prop,Assn,all(X,Prop=>Assn)) --> [every].

Skelett eines Determinators mit der Bedeutung von every:

all(X,Property => Assertion).

DCG Regel für every mit sichtbaren Slots.

determiner(X,Prop,Assn,all(X,Prop=>Assn)) --> [every].

Syntax und SemantikJetzt zusammenbau eines Satzes mit Determinator:

Beginnen mit dem Satz, a man paints.Bedeutung: exists(X,man(X) and paints(X)), wobei die Bedeutung von 'a' bereits als, exists(X,Prop,Assn) definiert wurde.

=> die Struktur der Satzbedeutung ist bereits durch den Determinator festgelegt.

Die Komposition der Satzbedeutung startet mit dem Determinator 'a', exists(X,Prop,Assn); dann wird Prop mit der Bedeutung des Nomens und Assn mit der Bedeutung der VP instantiiert.

Jetzt zusammenbau eines Satzes mit Determinator:

Beginnen mit dem Satz, a man paints.Bedeutung: exists(X,man(X) and paints(X)), wobei die Bedeutung von 'a' bereits als, exists(X,Prop,Assn) definiert wurde.

=> die Struktur der Satzbedeutung ist bereits durch den Determinator festgelegt.

Die Komposition der Satzbedeutung startet mit dem Determinator 'a', exists(X,Prop,Assn); dann wird Prop mit der Bedeutung des Nomens und Assn mit der Bedeutung der VP instantiiert.

Syntax und SemantikDie Satzbedeutung wird nun in der np zusammengebaut, nicht wie vorher in der vp.sentence(S) --> np(X,Assn,S), vp(X,Assn).np(X,Assn,S) --> det(X,Prop,Assn,S), n(X,Prop).vp(X,Assn) --> v_intr(X,Assn).v_intr(X,paints(X)) --> [paints].det(X,Prop,Assn,exists(X,Prop and Assn)) --> [a].n(X,man(X)) --> [man].

?- sentence(S,[a,man,paints],[]).S = exists(X,man(X) and paints(X)).

Die Satzbedeutung wird nun in der np zusammengebaut, nicht wie vorher in der vp.sentence(S) --> np(X,Assn,S), vp(X,Assn).np(X,Assn,S) --> det(X,Prop,Assn,S), n(X,Prop).vp(X,Assn) --> v_intr(X,Assn).v_intr(X,paints(X)) --> [paints].det(X,Prop,Assn,exists(X,Prop and Assn)) --> [a].n(X,man(X)) --> [man].

?- sentence(S,[a,man,paints],[]).S = exists(X,man(X) and paints(X)).

Syntax + SemantikErste Grammatik hatte Sätze wie john paints behandelt. Nachdem wir jetzt unsere Grammatik geändert haben müssen wir sicherstellen, dass auch diese Sätze funktionieren.

Bedeutung der Eigennamen muss in die neue np eingepasst werden.

en(john) --> [john].np(X,Assn,Assn) --> en(X).

Die letzte Regel stellt sicher, dass für diese Art von NP die Bedeutung der gesamten NP dieselbe ist wie diejenige im zweiten Slot Assn, die von der VP kommt.

Erste Grammatik hatte Sätze wie john paints behandelt. Nachdem wir jetzt unsere Grammatik geändert haben müssen wir sicherstellen, dass auch diese Sätze funktionieren.

Bedeutung der Eigennamen muss in die neue np eingepasst werden.

en(john) --> [john].np(X,Assn,Assn) --> en(X).

Die letzte Regel stellt sicher, dass für diese Art von NP die Bedeutung der gesamten NP dieselbe ist wie diejenige im zweiten Slot Assn, die von der VP kommt.

Hausaufgabe + nächstes MalVersuchen Zusammenbau der Semantik bis zu diesem Punkt zu Verstehen.Klausuren der vergangenen Jahre anschauen. Fragen stellen.

24.01.Tutorial II.Graphen.Semantik und Syntay als Abschluss Relativsätze.31.01.Bemerkungen zu Bratko Kapitel 10Tutorial III.Eliza Implementierung.

Versuchen Zusammenbau der Semantik bis zu diesem Punkt zu Verstehen.Klausuren der vergangenen Jahre anschauen. Fragen stellen.

24.01.Tutorial II.Graphen.Semantik und Syntay als Abschluss Relativsätze.31.01.Bemerkungen zu Bratko Kapitel 10Tutorial III.Eliza Implementierung.

Folie 1Folie 2Folie 3Folie 4Folie 5Folie 6Folie 7Folie 8Folie 9Folie 10Folie 11Folie 12Folie 13Folie 14Folie 15Folie 16Folie 17Folie 18Folie 19Folie 20Folie 21Folie 22Folie 23Folie 24Folie 25Folie 26Folie 27Folie 28Folie 29Folie 30Folie 31Folie 32Folie 33Folie 34Folie 35