Computerlinguistik II, WS 2007/08                  Aufgabenblatt 7
------------------------------------------------------------------
Ausgabe: Do, 17.1.08                           Abgabe: Do, 24.1.07

Aufgabe 11 (Formaler Umgang mit Lambda-Termen. Dabei seien 
----------  a,b,c Konstante, x,y,z Variable, paarweise verschieden)

a) Rechnen Sie nach der formalen Definition von t[x/s] (Folie S.119)
   schrittweise die folgenden Ersetzungen aus: 

   1. lambda x (y * (x * a)) [y/(y * lambda z (z * y))]   Punkte 1
   2. lambda x (y * (x * a)) [x/(y * lambda z (z * b))]   Punkge 1
   3. lambda x (y * (x * a)) [y/(x * lambda z (z * y))]   Punkte 1
   4. lambda x (y * (x * lambda y (y * x))) [y/(x * lambda z (z * y))]
                                                          Punkte 2
   5. (x * lambda x (y * x)) [x/(y*x)]                    Punkte 1
     
b) Vereinfachen Sie die folgenden Lambda-Terme schrittweise nach den
Reduktionsregeln (S. 121 ff.). Zeigen Sie die nötigen Beta-Reduktions-
schritte, aber schreiben Sie bei den Umbenennungen (Alpha-Reduktionen) 
einfach das Ergebnis hin. 

   1. lam(X, lam(Y,Y*X)) * X                             Punkte 1
   2. lam(X, lam(Y,Y*X)) * Y                             Punkte 1
   3. lam(X, lam(Y,Y*X)) * Z                             Punkte 1
   4. ((lam(X, lam(Y,Y*X)) * U) * V) * W                 Punkte 2
   5. (lam(X, lam(Y, Y*X)) * a) * lam(X, X*b)            Punkte 3
   6. lam(X,(lam(X, lam(Y, Y*X)) * X) * a)               Punkte 3
   7. lam(X,X*lam(Y,X*(Y*a))) * lam(Z,(b*X)*(Z*Y))       Punkte 4

Aufgabe 12
----------
a) Schreibe ein Prolog-Programm, freevars(+LamTerm,-VarList), das zu
   jedem LambdaTerm LamTerm die Menge der darin frei vorkommenden
   Variablen berechnet und als Liste VarList (in irgend einer Ordnung) 
   ausgibt. D.h. implementiere die Definition von free(t) aus
   den Folien. ['freevars', da Prolog schon ein 'free' hat]  Punkte 3

b) Auf den Folien steht keine Definition fuer die in einem Lambda-Term
   t gebunden vorkommenden Variablen. Gib eine (mathematische)
   Definition

     geb(t)

   für die Menge der in t gebundenen Variablen an. Wir haben ja schon
   oefter intuitiv benutzt, dass jedes lam(X,T) alle freien Vorkommen 
   von X in T 'bindet'. Mache die Definition so, dass auch das
   gezeigte Vorkommen von X in lam(X,_) als gebunden gilt.   Punkte 2

c) Schreibe ein Prolog-Programm gebvars(+LamTerm,-VarList), das zu
   jedem Lambda-Term eine Liste aller darin gebunden vorkommenden
   Variablen ausgibt.                                        Punkte 2

Hinweis: Benutze beim Vergleichen von Variablen nicht die Unifikation 
         (X = Y), sondern den Symbolvergleich (X == Y) von Prolog!

Aufgabe 13
----------
Nochmal zur Semantik: Wir wollen die PL-Formel zu einer einfachen 
NL-Aussage so berechnen: 

1. eine Nominalphrase wird aus der NL-Aussage entnommen, an ihrer
   Stelle durch eine Individuenvariable ersetzt:

      (... NP ...) |->  (... X ...)

2. Aus der Formel (... X ...) machen wir ein Prädikat:

      (... X ...) |->  lam(X,(... X ...))

3. Die NP-Bedeutung SemNP wird auf dieses Prädikat angewendet
   (nicht umgekehrt!):

      SemNP * lam(X, (... X ...))

4. Dazu muß die NP-Bedeutung ein Lambda-Term der Form 

      SemNP := lam(P, (....P*Y....))

   werden, die aus Prädikaten P mit Hilfe der Anwendung P*Y auf
   Individuen eine PL-Formel erzeugt.

Auf den Folien ist die Semantik von NP's so definiert, daß wir erhalten:

        NP                        SemNP
     ----------------------------------------------------------
4.'  Kepler              |->  lam(P,P*kepler)
     der Uranus          |->  lam(P,P*uranus)
     der Astronom Kepler |->  lam(P,astronom(kepler) & P*kepler)
   
Führen Sie 1.-3. mit einem intransitiven Verb an den Beispielen 

a) Kepler arbeitet.
b) der Astronom Kepler arbeitet.

unter Verwendung von 4.' durch und vereinfachen Sie den entstehenden 
Ausdruck (von Hand).                                   Punkte 4

(Na ja, in 1. schreiben Sie statt (X arbeitet) besser arbeitet(X).)