Rekursiver Aufbau/Schachtel/Verschachtelung/Aufgabe
Eine Geschenkfabrik verfügt über leere, offene Schachteln (unterschiedlicher Größe) und über Maschinen, die die beiden folgenden Abläufe durchführen können.
- Eine offene Schachtel schließen.
- Eine geschlossene Schachtel in eine größere offene Schachtel (in der schon andere Schachteln liegen dürfen) hineinlegen.
Ein Produkt der Fabrik ist das Ergebnis aus diesen (beliebig verschachtelten) Abläufen.
- Definiere (induktiv) die Schachtelanzahl eines Produkts der Fabrik.
- Definiere die Verschachtelungstiefe eines Produkts der Fabrik.
- Definiere die Arbeitsschrittanzahl eines Produkts der Fabrik.
- Bestimme die Schachtelanzahl, die Verschachtelungstiefe und die Arbeitsschrittanzahl des gezeigten Produkts (die Schachteln seien geschlossen).
- Zeige, dass jedes Produkt der Fabrik nur maximal eine offene Schachtel enthält.
- Welche Gleichheitsbegriffe sind für die Produkte der Firma sinnvoll? Welche Produkte lassen sich auf unterschiedliche Arten generieren? Sind die unter (1), (2), (3) definierten Begriffe wohldefiniert, also unabhängig vom Generierungsprozess?