L-Systeme

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

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

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

• einem Startwort $s$

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

Das Startwort $s$ 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 = \{\text X, \text Y,\text F,+,-\}$

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

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

$s = \text X$

Die erste Generation, indem du zunächst $\text X$ durch $\text{+YF--XFX--FY+}$ ersetzt, entspricht einer U-förmigen Kurve. Die zweite Generation, indem du alle $\text X$ durch $\text {+YF--XFX--FY+}$ und alle $\text Y$ durch $\text{--XF+YFY+FX--}$ 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.

Ausprobieren

Beispiel: Drachen-Kurve

Das folgende erstaunlich einfache L-System erzeugt eine erstaunlich komplexe fraktale (selbstähnliche) Kurve, die Drachen-Kurve.

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

$P : \text F \rightarrow \text{F+G}$

$~~~\text G \rightarrow \text{F--G}$

$s = \text F$

Ausprobieren

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 = \{\text X,\text F,+,-,[,]\}$

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

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

$s = \text X$

Ausprobieren