Geben Sie diese Hausaufgabe bis 7. Mai 2015 ab. Entweder bis 16:00 per Email an Tillmann Rendel
AlumniTillmann Rendel (schreiben Sie “pl2” in den Betreff!) oder zu Beginn der Vorlesung auf Papier.

Gruppen

Sie können in Gruppen von bis zu 3 Personen arbeiten. Schreiben Sie in jedem Fall die Namen und Matrikelnummern aller Gruppenmitglieder mit auf die Hausaufgabe / in die Email. Wenn Sie in einer Gruppe arbeiten, achten Sie darauf, daß alle Mitglieder der Gruppe den Stoff verstehen. Nur dann sind die Hausaufgaben eine gute Vorbereitung auf die Prüfung.

Punkte

Sie können für die Aufgaben dieser Woche jeweils zwischen 0 und 3 Punkten bekommen. Insgesamt also zwischen 0 und 6 Punkten. Sie bekommen für die Aufgaben jeweils:

• 1 Punkt, wenn Ihre Abgabe zeigt, daß Sie sich mit der Aufgabe ernsthaft beschäftigt haben.

• 2 Punkte, wenn Sie die Aufgabe weitgehend korrekt gelöst haben.

• 3 Punkte, wenn Sie die Aufgabe vollständig korrekt gelöst und Ihre Lösung gut verständlich dargestellt haben.

Die Punktevergabe für die weiteren Hausaufgaben im Semester wird ähnlich sein.

Aufgabe 3

Diese Aufgabe bezieht sich auf die Sprache mit Wahrheitswerten aus der Vorlesung. In der Vorlesung wurde folgende Eigenschaft benutzt, um die Terminierung der Multi-step Reduktion zu zeigen:

• aus t → t′ folgt size(t) > size(t′)

Beweisen Sie diese Eigenschaft.

Aufgabe 4

Diese Aufgabe bezieht sich auf die Sprache mit Wahrheitswerten und Zahlen aus der Vorlesung. Gegeben seien folgende Terme:

t₁ = if (iszero (pred (succ zero))) (succ zero) zero
t₂ = succ (if (iszero zero) (succ zero) true)
t₃ = if (iszero (succ true)) (succ zero) zero

1. Ist der Term t₁ stuck? Geben Sie entweder einen Ableitungsbaum von t₁ → t₁′ für ein t₁′ an, oder begründen Sie, wieso es keinen solchen Ableitungsbaum geben kann.

2. Ist der Term t₁ wohlgetypt? Geben Sie entweder einen Ableitungsbaum von t₁ : T₁ für ein T₁ an, oder begründen Sie, wieso es keinen solchen Ableitungsbaum geben kann.

3. Ist der Term t₂ stuck? Geben Sie entweder einen Ableitungsbaum von t₂ → t₂′ für ein t₂′ an, oder begründen Sie, wieso es keinen solchen Ableitungsbaum geben kann.

4. Ist der Term t₂ wohlgetypt? Geben Sie entweder einen Ableitungsbaum von t₂ : T₂ für ein T₂ an, oder begründen Sie, wieso es keinen solchen Ableitungsbaum geben kann.

5. Ist der Term t₃ stuck? Geben Sie entweder einen Ableitungsbaum von t₃ → t₃′ für ein t₃′ an, oder begründen Sie, wieso es keinen solchen Ableitungsbaum geben kann.

6. Ist der Term t₃ wohlgetypt? Geben Sie entweder einen Ableitungsbaum von t₃ : T₃ für ein T₃ an, oder begründen Sie, wieso es keinen solchen Ableitungsbaum geben kann.