Lindenmayer-System

Was ist ein Lindenmayer-System?

Ein Lindenmayer-System besteht aus einem Alphabet A, Ersetzungsregeln E und einem Startwort w.

Durch Anwendung der Ersetzungsregeln auf das Startwort kann eine neues Wort erzeugt werden. Auf dieses werden die selben Regeln erneut angewandt. Mit Hilfe der Ersetzungsregeln und des Startwortes können somit beliebig lange Worte erzeugt werden. Ein Beispiel soll dies verdeutlichen:

Beispiel
A: {a, b}
E: a -> ab und b -> a
angewandt auf
w: b ergibt b -> a -> ab -> aba -> abaab ...

Erstaunlich ist, dass dieser doch sehr mathematisch wirkende Ersetzungsvorgang eine biologische Interpretation hat. Wenn man b als ein altes und a als ein junges Kaninchenpaar annimmt, so erhält man eine Simulation einer Kaninchenpopulation. Dieses Beispiel verdeutlicht, dass mit Lindenmayer-Systemen sehr gut biologische Vorgänge simuliert werden können. Ebenfalls wird ersichtlich, dass solche Art von Simulationen, die durch wiederholte Ersetzungen nach bestimmten Regeln durchgeführt werden, sehr gut mit dem Computer realisierbar sind.

Eine weitere Andwendung von Lindenmayer-Systemen aus der Biologie ist die Modellierung von Pflanzen. Diese soll im folgenden betrachtet werden.

Es stellt sich als zweckmäßig heraus die bildliche Darstellung mittels Turtle-Grafik (Turtle: eng. Schildkröte) vorzunehmen.

Zentraler Bestandteil dieses Visualisierungsmodells ist das Turtle-Objekt, mit dem alle Linien gezeichnet werden. Sein aktueller Zustand ist durch die folgenden Größen charakterisiert:

  • Position (x, y) in der Ebene
  • aktuelle Richtung (phi)
Darüberhinaus kann das Turtle-Objekt Kopien des aktuellen Zustandes auf einem Stack (Stapel) speichern und später wiederherstellen.

Folgende Operationen werden vom Tutle verstanden:

  • F: das Turtle bewegt sich in der aktuellen Richtung um eine festgelegte Länge l und zeichnet dabei eine Linie
  • f: das Turtle bewegt sich, jedoch ohne dabei zu zeichnen
  • +: Verdrehung des Turtle im Gegenuhrzeigersinn um einen festgelegten Drehwinkel
  • -: Verdrehung im Uhrzeigersinn
  • [: aktueller Zustand des Turtles wird auf dem Stack gespeichert
  • ]: letzter gespeicherter Zustand wird wiederhergestellt
Alphabet, Ersetzungsregeln und Startwort eines Lindenmayer-Systemes können nun so gewählt werden, daß das resultierende Wort eine Folge von Turtle-Operationen darstellt. Dieses Wort kann mit Tutle-Grafik direkt in eine Zeichnung umgesetzt werden.

Applets


Edge Rewriting

EdgeRewrite.png
Titel EdgeRewrite
Kurzbeschreibung

Jede Kante wird ersetzt durch Produktionsregel.

-> Edge Rewriting Applet

Node Rewriting

NodeRewrite.png
Titel NodeRewrite
Kurzbeschreibung

Jeder Knoten wird ersetzt durch Produktionsregel.

-> Node Rewriting Applet