Springe zum Inhalt oder Footer
SerloDie freie Lernplattform

L-Systeme

Bild

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 XaXa\text X \rightarrow \text{aXa} auf das Wort XYYX\text {XYYX} anwendest, ersetzt du ein Vorkommen von X\text X durch aXa\text {aXa} und erhältst zum Beispiel XYYXaX\text {XYYXaX}.

  • Bei einem L-System dagegen wendest du alle Produktionen gleichzeitig an allen Stellen an. Du ersetzt alle Vorkommen von X\text X durch aXa\text {aXa} und erhältst aXaYYaXa\text {aXaYYaXa}. Wenn es außerdem noch die Produktion YYb\text Y \rightarrow \text {Yb} gibt, ersetzt du auch noch alle Vorkommen von Y\text Y durch Yb\text {Yb} und erhältst aXaYbYbaXa\text {aXaYbYbaXa}. 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 AA,

  • einer Abbildung P:AAP: A \rightarrow A^*

  • einem Startwort ss

Ein solches L-System hat große Ähnlichkeit mit einer kontextfreien Grammatik. Ähnlich wie die Produktionen einer kontextfreien Grammatik besteht die Abbildung PP aus Paaren (a,w)(a, w), wobei aa ein Zeichen des Alphabets AA ist und ww ein Wort aus AA^*. Ein solches Paar wird als awa \rightarrow w geschrieben, es stellt eine Ersetzungsregel dar.

Das Startwort ss 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:

A={X,Y,F,+,}A = \{\text X, \text Y,\text F,+,-\}

P:X+YF–XFX-FY+P : \text X \rightarrow \text{+YF--XFX-FY+}

   Y–XF+YFY+FX–~~~\text Y \rightarrow \text{--XF+YFY+FX--}

s=Xs = \text X

Die erste Generation, indem du zunächst X\text X durch +YF–XFX–FY+\text{+YF--XFX--FY+} ersetzt, entspricht einer U-förmigen Kurve. Die zweite Generation, indem du alle X\text X durch +YF–XFX–FY+\text {+YF--XFX--FY+} und alle Y\text Y durch –XF+YFY+FX–\text{--XF+YFY+FX--} ersetzt, entspricht einer U-förmigen Kurve mit U-förmigen Einbuchtungen.

Bild

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.

A={F,G,+,}A = \{\text F,\text G,+,-\}

P:FF+GP : \text F \rightarrow \text{F+G}

   GF–G~~~\text G \rightarrow \text{F--G}

s=Fs = \text F

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°.

A={X,F,+,,[,]}A = \{\text X,\text F,+,-,[,]\}

P:XF+[[X]–X]–F[–FX]+XP : \text X \rightarrow \text {F+[[X]–X]–F[–FX]+X}

    FFF~~~~\text F \rightarrow \text {FF}

s=Xs = \text X


Dieses Werk steht unter der freien Lizenz
CC BY-SA 4.0Was bedeutet das?