Die Grammatik des Grashalms
Eine spezielle Variante von Grammatiken sind Lindenmayer-Systeme oder kurz L-Systeme. Während bei einer Standard-Grammatik immer nur eine Produktion zur Zeit angewendet wird, werden bei einem L-System immer alle Produktionen gleichzeitig angewendet. Der Biologe A. Lindenmayer hat die später nach ihm benannten L-Systeme ursprünglich entwickelt, um das Wachstum von Pflanzen zu modellieren. Folgerichtig werden L-Systeme heute in der Computergrafik verwendet, um virtuelle Pflanzen zu generieren.
Prinzip
Bei einer Standard-Grammatik wendest du eine Produktion immer nur an einer Stelle zur Zeit an. Wenn du bei einer Standard-Grammatik also die Produktion auf das Wort anwendest, ersetzt du ein Vorkommen von durch und erhältst zum Beispiel .
Bei einem L-System dagegen wendest du alle Produktionen gleichzeitig an allen Stellen an. Du ersetzt alle Vorkommen von durch und erhältst . Wenn es außerdem noch die Produktion gibt, ersetzt du auch noch alle Vorkommen von durch und erhältst . Dieses Wort wird als nächste Generation nach Durchführung dieser Ersetzungen bezeichnet.
Formale Definition
In der einfachsten Form besteht ein L-System aus
einem Alphabet ,
einer Abbildung
einem Startwort
Ein solches L-System hat große Ähnlichkeit mit einer kontextfreien Grammatik. Ähnlich wie die Produktionen einer kontextfreien Grammatik besteht die Abbildung aus Paaren , wobei ein Zeichen des Alphabets ist und ein Wort aus . Ein solches Paar wird als geschrieben, es stellt eine Ersetzungsregel dar.
Das Startwort ist die nullte Generation. Indem du die Ersetzungsregeln auf das Startwort anwendest, erhältst du die erste Generation.
Turtle-Grafik
Um Grafiken zu erzeugen, verwendest du Grafik-Operationen als Alphabetzeichen des L-Systems. Die einfachsten Grafik-Operationen findest du in der Turtle-Grafik: Eine Schildkröte (turtle) krabbelt auf dem Papier herum und führt folgende Aktionen aus:
F oder G Vorwärtsschritt
+ Wendung nach rechts
- Wendung nach links
Zusätzlich gibt es noch die Zeichen [ und ], mit denen du die momentane Position der Turtle speichern und später wieder abrufen kannst, entsprechend den Stack-Operationen push und pop.
Weitere zusätzliche Alphabetzeichen benutzt du, um den Ersetzungsvorgang geeignet zu steuern.
Beispiel: Hilbert-Kurve
Das folgende L-System erzeugt eine raumfüllende Kurve, die Hilbert-Kurve:
Die erste Generation, indem du zunächst durch ersetzt, entspricht einer U-förmigen Kurve. Die zweite Generation, indem du alle durch und alle durch ersetzt, entspricht einer U-förmigen Kurve mit U-förmigen Einbuchtungen.
Die weiteren Generationen verursachen weitere U-förmige Einbuchtungen. Hierdurch entstehen Kurven, die nach und nach die Ebene beliebig dicht ausfüllen.
Beispiel: Drachen-Kurve
Das folgende erstaunlich einfache L-System erzeugt eine erstaunlich komplexe fraktale (selbstähnliche) Kurve, die Drachen-Kurve.
Beispiel: Grashalm
Einen Grashalm kannst du nicht in einem Zug zeichnen, ohne den Stift abzusetzen. Hier werden nun die Turtle-Operationen [ und ] gebraucht. Bei einer öffnenden eckigen Klammer wird die aktuelle Position und die aktuelle Richtung der Turtle auf einem Stack gespeichert und bei der zugehörigen schließenden eckigen Klammer wiederhergestellt. Die Operationen + und – entsprechen hier Rechts- und Linkswendungen um 25°.