Programming Languages

Hausaufgabe 2

Geben Sie diese Hausaufgabe bis 7. Mai 2015 ab. Entweder bis 16:00 per Email an Tillmann Rendel
Alumni
Tillmann 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:

t1 = if (iszero (pred (succ zero))) (succ zero) zero
t2 = succ (if (iszero zero) (succ zero) true)
t3 = if (iszero (succ true)) (succ zero) zero

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

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

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

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

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

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