Lambda-Kalkül < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:20 Do 04.06.2009 | | Autor: | LiN24 |
| Aufgabe | Reduzieren Sie folgende Lambda-Ausdrücke zu ihrer einfachsten Form:
a) [mm] (((\lambda x.(\lambda [/mm] y.(power x y)))3)4)
b) [mm] (\lambda [/mm] x.(times x(times x [mm] x)))(\lambda [/mm] x. [mm] \lambda [/mm] y.(plus x y)) 2 3)
Reduktion in Normalordnung und applikativer Ordnung
c) [mm] (((\lambda [/mm] x. [mm] \lambda [/mm] y. [mm] \lambda [/mm] z. x y [mm] z)(\lambda [/mm] x. [mm] \lambda [/mm] y.power x y)) 2 3)
d) [mm] (\lambda y.(\lambda [/mm] x. [mm] \lambda [/mm] y. x y) [mm] (\lambda [/mm] x.power x y))
times steht für Multiplikation und power für Exponentation |
hi,
ich komme mit dem Thema Lambda-Kalkül überhaupt nicht klar:
bei c) würde ich sogar sagen, dass es nicht geht, da ich nur 2 Parameterwerte habe, aber 3 Variablen,
aber das dürfte wohl falsch sein
bei a) habe ich (power 3 4)
aber ansonsten weiß ich nicht, was ich machen soll und wo der Unterschied zwischen Normalordnung und applikativer Ordnung ist
würde mich freuen, wenn mir jemand erklären könnte, wie ich an die Aufgaben rangehen muss
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:22 Fr 05.06.2009 | | Autor: | fabba |
Ich verwende der Übersichtlichkeit halber mal verschiedene Klammertypen.
a) Stimme Dir zu
[mm] ((<\lambda [/mm] x. [mm] [\lambda [/mm] y. (power x y)]> 3) 4)
= [mm] ([\lambda [/mm] y. (power 3 y)] 4)
= power 3 4
= 81
b)
[mm] (<\lambda [/mm] x . [times x (times x [mm] x)]><[\lambda [/mm] x. [mm] \lambda [/mm] y. (plus x y)] 2 3>)
= [mm] (<\lambda [/mm] x . [times x (times x [mm] x)]><[\lambda [/mm] y. (plus 2 y)] 3>)
= [mm] (<\lambda [/mm] x . [times x (times x x)]> <plus 2 3>)
= (times <plus 2 3> (times <plus 2 3> <plus 2 3>))
= 125
Wäre meine Idee. Das mit der Ordnung sollte was mit der Reihenfolge der Auswertung zu tun haben, kann ich aber aus dem Kopf nicht sagen.
c)
[mm] ([<\lambda [/mm] x. [mm] \lambda [/mm] y. [mm] \lambda [/mm] z. x y [mm] z><\lambda [/mm] x. [mm] \lambda [/mm] y. power x y>] 2 3)
Zuerst das eine Argument, das da steht (Lambda-Ausdruck) für x einsetzen. Dazu müssen wir die gebundenen Variablen umbenennen, weils sonst Probleme gibt (gibt auch ne ausführliche Schreibweise dazu, ich mach das jetz in einem Schritt)
= [mm] ([<\lambda [/mm] x. [mm] \lambda [/mm] y. [mm] \lambda [/mm] z. x y [mm] z><\lambda [/mm] s. [mm] \lambda [/mm] t. power s t>] 2 3)
= [mm] (<\lambda [/mm] y. [mm] \lambda [/mm] z. [mm] <\lambda [/mm] s. [mm] \lambda [/mm] t. power s t> y z> 2 3)
Jetz kann man die anderen beiden Argumente einsetzen
= [mm] (<\lambda [/mm] z. [mm] <\lambda [/mm] s. [mm] \lambda [/mm] t. power s t> 2 z> 3)
= [mm] (<\lambda [/mm] s. [mm] \lambda [/mm] t. power s t> 2 3)
... und jetzt weiter auflösen (man hätte auch innen anfangen können und dann die äußeren Elemente einsetzen)
= [mm] (<\lambda [/mm] t. power 2 t> 3)
= (power 2 3)
= 8
Übrigens: selbst wenn es Du ein Argument zu wenig oder zu viel hast, kannst Du in gewissem Maße vereinfachen. Dann kommt halt ne Funktion als Ergebnis raus (zB [mm] [\lambda [/mm] x. power x 2]) oder es bleibt was zusätzliches stehen (power 2 3 4)
d)
[mm] (\lambda [/mm] y. [mm] <\lambda [/mm] x. [mm] \lambda [/mm] y. x y> [mm] <\lambda [/mm] x. power x y>)
Find ich schon unschön aufgebaut, hier sollte man zur Klarheit sofort eine Umbenennung durchführen.
= [mm] (\lambda [/mm] y. [mm] <\lambda [/mm] s. [mm] \lambda [/mm] t. s t> [mm] [\lambda [/mm] x. power x y])
Für s wird der Lambda-Ausdruck eingesetzt
= [mm] (\lambda [/mm] y. [mm] <\lambda [/mm] t. [mm] [\lambda [/mm] x. power x y] t>)
= [mm] (\lambda [/mm] y. [mm] <\lambda [/mm] t. [power t y]>)
Schluss mit Auflösen, bleibt ne Funktion stehen. Hier bin ich aber unsicher, vielleicht ist das mit der doppelten Verwendung von y auch anders gemeint.
PS: Sorry, die Lesbarkeit leidet anscheinend an meinem Unwillen, mich mit diesem TeX-Unsinn zu beschäftigen
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:49 Fr 05.06.2009 | | Autor: | LiN24 |
trotzdem danke für die Hilfe, ich konnte mit den Aufgaben nicht wirklich was anfangen...
werd dann nochmal den Prof fragen und hoffen, dass es nicht in der Prüfung rankommt ^^
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:20 Mi 10.06.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
