a) For the following lambda expressions, indicate which occurrences of the variable are free or not. are bound. Give the binding -abstraction in each case. (1) (a.(b.(c.a) b) c) d (2) a.(b.((c.a c) c) ((a.c a) a) b) a b b) State whether the following expression is a valid -conversion and justify your answer. a.b.(a.a) b w.y.(a.w) y c) Show that the following lambda expressions are equivalent by giving the corresponding named conversion steps: (1) (a.a a) (b.b) (c.c) d.d (2) (c.(b.(a.a b c))) b a c c a b

a) Geben Sie fr die folgenden Lambda-Ausdrcke an, welche Auftreten der Variablen frei bzw. gebunden sind. Geben Sie jeweils die bindende -Abstraktion an. (1) (aa.(26.(Ac.a) b) c) d (2) la.(16.((Ac.a c) c) ((a.ca) a) b) a b b) Geben Sie an, ob es sich in dem folgenden Ausdruck um eine gltige a-Konversion handelt und begrnden Sie Ihre Antwort. la.Ab.(ta.a) blw.Ay.Xa.w) y a c) Zeigen Sie durch Angabe der entsprechenden benannten Konversionsschritte, dass die fol- genden Lambda-Ausdrcke quivalent sind: (1) (Aa.a a) (16.b) (Ac.c) - Xd.d (2) (Ac. (16.(Aa.a bc))) baccab )) 1/2