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}\to \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}\to \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\to A^{\ast }$

• 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^{\ast }$. Ein solches Paar wird als $a\to 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}\to \text{+YF–XFX-FY+}$

$\text{Y}\to \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}\to \text{F+G}$

$\text{G}\to \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}\to \text{F+[[X]–X]–F[–FX]+X}$

$\text{F}\to \text{FF}$

$s=\text{X}$

Ausprobieren