Monika macht Matrosenketten mit weiß-roten Wellenperlen und einfarbigen blauen Perlen.
Sie beginnt immer mit einer Wellenperle links und einer blauen Perle rechts:
Dann verlängert sie die Matrosenkette mehrmals. Jedesmal fügt sie
Welche dieser Ketten ist keine von Monikas Matrosenketten?
Im Bild oben ist dargestellt durch welche Regeln welche Kugeln hinzugefügt wurden.
Man kann diese Aufgabe aber durch folgende Überlegung auch einfacher lösen:
Die Kette startet mit einer ungeraden Anzahl von blauen Kugeln.
Regel A fügt 2 blaue Kugeln hinzu, dadurch bleibt die Anzahl ungerade.
Regel A fügt keine blauen Kugeln hinzu, dadurch bleibt die Anzahl auch ungerade.
Mit diesen Regeln kann keine Kette mit einer geraden Anzahl von Kugeln produziert werden.
Da C eine gerade Anzahl von Kugeln hat, kann C nicht produziert werden.
Durch wiederholte Anwendung der zwei Regeln in beliebiger Reihenfolge konnte Monika bestimmte Ketten herstellen, während andere Ketten nicht möglich waren.
Eine Menge von Symbolen und Regeln, die bestimmen, wie man die Symbole zu größeren Einheiten zusammensetzen darf, findet man in der Informatik sehr häufig. So wie wir in der Aufgabe feststellen konnten, welche Ketten gültig sind und welche nicht, können wir auf diese Art die Gültigkeit von ganz verschiedenen Elementen überprüfen: Computerprogramme, Botschaften und Nachrichten, Sätze in Deutsch oder einer anderen Sprache, … . Mit genügend geeigneten Regeln könnte man also sogar eine einfache Rechtschreibprüfung erstellen (natürliche Sprachen sind zu kompliziert um einen vollständigen Satz an Regeln angeben zu können).
"Gültig" heißt in diesem Zusammenhang "gültig in Bezug auf einen bestimmten Satz von Regeln". Wenn man zum Beispiel einen deutschen Satz überprüfen möchte, braucht man einen anderen Satz von Regeln als für einen englischen Satz. Manche Regeln werden aber sehr ähnlich sein.
Ein großer Vorteil an dieser Vorgangsweise ist, dass ein Computer mithilfe solcher Regeln all diese Prüfungen automatisch durchführen kann.
In der Informatik nennt man so ein System eine "formale Grammatik".