Um alle Funktionen dieser Seite zu nutzen, aktivieren Sie bitte die Cookies in Ihrem Browser.
my.bionity.com
Mit einem my.bionity.com-Account haben Sie immer alles im Überblick - und können sich Ihre eigene Website und Ihren individuellen Newsletter konfigurieren.
- Meine Merkliste
- Meine gespeicherte Suche
- Meine gespeicherten Themen
- Meine Newsletter
Lindenmayer-SystemBei den Lindenmayer- oder L-Systemen handelt es sich um einen mathematischen Formalismus, der 1968 von dem ungarischen theoretischen Biologen Aristid Lindenmayer als Grundlage einer axiomatischen Theorie biologischer Entwicklung vorgeschlagen wurde. In jüngerer Zeit fanden L-Systeme Anwendung in der Computergraphik bei der Erzeugung von Fraktalen und in der realitätsnahen Modellierung von Pflanzen. Das wesentliche Prinzip von L-Systemen besteht in der sukzessiven Ersetzung von Einzelteilen eines einfachen Objektes mittels so genannter Produktionsregeln. Diese Ersetzungen können rekursiv durchgeführt werden. Damit gehören L-Systeme zu den sogenannten Ersetzungssystemen. Die bekanntesten Ersetzungssysteme sind solche, die auf Zeichenketten basieren. Besonders Noam Chomskys Arbeiten aus den 1950ern über formale Grammatiken stießen auf großes Interesse und befruchteten die Forschung in der theoretischen Informatik. Im Gegensatz zu den sequentiellen Ersetzungsregeln in Chomskys Grammatiken finden Ersetzungen in L-Systemen parallel statt, analog zu den gleichzeitig stattfindenden Zellteilungen in mehrzelligen Organismen, die der Anstoß zur Entwicklung der L-Systeme waren. L-Systeme sind hervorragend geeignet, Darstellungen von Fraktalen zu erzeugen. Dazu werden die in den Rekursionen des L-Systems erzeugten Zeichenketten in direkt ausführbare Befehle eines Systems, welches die Turtle-Grafik realisiert, umgesetzt, z. B. die Programmiersprache LOGO. Weiteres empfehlenswertes Fachwissen
Struktur eines L-SystemsEin L-System ist ein Quadrupel G = (V, S, ω, P), wobei
Kontextfreie L-SystemeUm ein L-System zu realisieren, wird eine Tiefe n festgelegt und ein Ersetzungsschritt endlich oft wiederholt. Im Ersetzungsschritt wird das aktuelle Wort ω Zeichen für Zeichen abgearbeitet und jedes Zeichen durch das neue, in den Ersetzungsregeln festgelegte Wort ersetzt. Kontext-freie L-Systeme (auch 0L-Systeme genannt) enthalten Produktionen p, die auf ein Anfangswort ω (auch Axiom genannt) n-mal angewendet werden. Die Produktionen ordnen dabei maximal einem Zeichen ohne Beachtung des Kontextes ein Wort zu. Wird für ein Zeichen keine Regel angegeben, wird im Allgemeinen die Identität als triviale Ersetzung des Zeichens durch sich selbst angenommen. Beispiel für Systeme ohne SpeicherViele der bekannteren Fraktale, wie das Sierpinski-Dreieck oder die Koch-Kurve, können mittels L-Systemen über dem Alphabet V={F}, S={+,-} dargestellt werden. Es gibt nur eine einzige Ersetzungsregel für das Symbol F. Im Artikel Fraktal sind einige Beispiele aufgelistet. So hat das Kochsche Schneeflockenfraktal das Startwort ω=F--F--F und die Ersetzungsregel P={(F → F+F--F+F)}. Zur Interpretation eines solchen L-Systems mittels Turtle-Grafik benötigt man einen Stauchungsfaktor s<1 und einen Winkel a. Mittels des Stauchungsfaktors wird die Weglänge bei Rekursionstiefe n als sn bestimmt. Die Schildkröte besitzt keinen Speicher und führt die Symbole des Alphabets als folgende Kommandos sofort aus
Der Winkel a und der Faktor s sollten so abgestimmt sein, dass F mit Streckenlänge 1 und das Ersetzungswort von F zur Streckenlänge s bei gleichem Ausgangspunkt ebenfalls einen gemeinsamen Endpunkt haben. Einige Fraktale wie die Drachenkurve benötigen zwei Ersetzungsregeln, als variablen Teil des Alphabets wählt man z. B. V={R,L} und legt für dieses Beispiel ω=R und P={(R → +R--L+), (L → -R++L-)} fest. Beide Symbole werden in der Darstellung wie F behandelt, d. h. als zeichnenden Schritt nach vorn. Man kann diese Art der Hinzunahme von Ersetzungsregeln beliebig steigern, oder auch weitere Symbole mit anderen Aktionen definieren:
Beispiel für Systeme mit SpeicherEs wird ein LIFO-Stack für Koordinatensysteme eingeführt. Jede Koordinatentransformation besteht aus einer Drehung, die durch einen Winkel parametrisiert werden kann, und einer Verschiebung. Das Alphabet wird um die konstanten Symbole [ und ] erweitert, welche folgende Bedeutung haben:
Innerhalb eines Klammerpaars kann also ein im Leeren endender Zweig gezeichnet werden. Diese Möglichkeit wurde zur Darstellung fraktaler Bäume eingeführt. Kontext-sensitive L-SystemeIm Unterschied zu kontext-freien L-Systemen werden bei den Produktionen auch die Zeichen oder Zeichenfolgen vor oder nach dem zu ersetzenden Zeichen betrachtet. Dabei werden die Kontextbedingungen üblicherweise so notiert, dass der linke Kontext durch < vom zu ersetzenden Zeichen abgetrennt wird, und der rechte Kontext entsprechend durch >. Beispiel : Zeichensatz = { a, b }; Produktionen = { b < a → b, b > b → a }; ω = {baaa}
etc. Parametrische L-SystemeIm Rahmen der parametrischen L-Systeme werden zusätzlich zu einzelnen Zeichen auch den Zeichen zugeordnete Ziffern betrachtet. Diese Parameter lassen sich nicht nur explizit in den Produktionsregeln verändern, sondern man kann auch konditionale Produktionen erstellen, die nur greifen, wenn bestimmte Bedingungen erfüllt sind, ähnlich den kontext-sensitiven L-Systemen. Beispiel: Sei F(l) ein Ast der Länge l. Die Produktionen F(l) : l<10 -> f(l+1) und F(l) : l≥ 10 → F(i+1)F(1) lassen den Ast nun wachsen und ab einer bestimmten Länge (l=10) neue Äste entstehen. Literatur
Siehe auch
|
|
Dieser Artikel basiert auf dem Artikel Lindenmayer-System aus der freien Enzyklopädie Wikipedia und steht unter der GNU-Lizenz für freie Dokumentation. In der Wikipedia ist eine Liste der Autoren verfügbar. |