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

• Bei einem L-System dagegen wendest du alle Produktionen gleichzeitig an allen Stellen an. Du ersetzt alle Vorkommen von $\text{X}\backslash text\; X$ durch $\text{aXa}\backslash text\; \{aXa\}$ und erhältst $\text{aXaYYaXa}\backslash text\; \{aXaYYaXa\}$. Wenn es außerdem noch die Produktion $\text{Y}\to \text{Yb}\backslash text\; Y\; \backslash rightarrow\; \backslash text\; \{Yb\}$ gibt, ersetzt du auch noch alle Vorkommen von $\text{Y}\backslash text\; Y$ durch $\text{Yb}\backslash text\; \{Yb\}$ und erhältst $\text{aXaYbYbaXa}\backslash 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:A\to A^{\ast }P:\; A\; \backslash 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 $A^{\ast }A^*$. Ein solches Paar wird als $a\to wa\; \backslash 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=\{\text{X},\text{Y},\text{F},+,-\}A\; =\; \backslash \{\backslash text\; X,\; \backslash text\; Y,\backslash text\; F,+,-\backslash \}$

$P:\text{X}\to \text{+YF–XFX-FY+}P\; :\; \backslash text\; X\; \backslash rightarrow\; \backslash text\{+YF--XFX-FY+\}$

$\text{ Y}\to \text{–XF+YFY+FX–}~~~\backslash text\; Y\; \backslash rightarrow\; \backslash text\{--XF+YFY+FX--\}$

$s=\text{X}s\; =\; \backslash text\; X$

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

$P:\text{F}\to \text{F+G}P\; :\; \backslash text\; F\; \backslash rightarrow\; \backslash text\{F+G\}$

$\text{ G}\to \text{F–G}~~~\backslash text\; G\; \backslash rightarrow\; \backslash text\{F--G\}$

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

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

$\text{ F}\to \text{FF}~~~~\backslash text\; F\; \backslash rightarrow\; \backslash text\; \{FF\}$

$s=\text{X}s\; =\; \backslash text\; X$

Ausprobieren