OSA Baden-Württemberg
BW Quadrat Logo
× Die Beispielaufgaben sollten an einem PC bearbeitet werden.

Theoretische Informatik – Aufgaben

Das Quellen- und Literaturverzeichnis zu dieser Seite finden Sie hier.

Aufgabe 1 von 3

Herr Chomsky, Chefkoch im „Hilbert Gold“, einem exclusiven Hotel mit internationaler Küche, bereitet sich auf die nächste Grillsaison vor. Als Spezialität sollen diesmal Schaschlik-Spieße serviert werden, mit Fleisch, Zwiebeln, Paprika und Pilzen. Die von unserem Chefkoch erstellten Spieße (die er gerne „Chomsky-Spieße“ nennt) zeichnen sich dabei aber durch eine ganz bestimmte Reihenfolge der Zutaten aus. Chefkoch Chomsky beschreibt dies wie folgt:

„Chomksy-Spieße gibt es in einfachen und komplexen Varianten. Bereits ein einzelnes Stück Fleisch auf einem Spieß ist ein Chomsky-Spieß (der Genuss beruht hier auf der richtigen Wahl der Marinade). Nimmt man einen Chomsky-Spieß und erweitert ihn auf beiden Seiten mit einem Stück Zwiebel, erhält man wieder einen Chomsky-Spieß. Genauso kann man einen Chomsky-Spieß auch um einen Pilz auf der einen Seite und ein Stück Paprika auf der anderen Seite erweitern, um wieder einen Chomsky-Spieß zu erhalten. Oder man nimmt den kompletten Inhalt eines Chomsky-Spießes und fügt ihn, unter Beibehaltung der Reihenfolge, einem anderen Chomsky-Spieß hinzu. Was nicht durch diese Regeln aufgespießt werden kann, ist auch kein Chomsky-Spieß und hat in meiner Küche nichts verloren.“

Identifizieren Sie die korrekten Chomsky-Spieße. Wählen Sie eine oder mehrere Antworten.

Bitte
auswählen
Abb. 1
Abb. 2
Abb. 3
Abb. 4
Abb. 5
Abb. 6
Abb. 7

Analysiert man die Anleitung oben, gibt es nur drei Schritte, mit denen ein Chomsky-Spieß sukzessive aufgebaut werden kann. Versucht man, bei einem gegebenen Spieß diese Schritte nachzuvollziehen, kommt man entweder auf die verwendeten Schritte oder trifft auf eine Stelle, an der keine Regel mehr angewandt werden kann.