imported>Docosanus: /* Literatur */ + 2 Links: Heinz-Otto Peitgen, Dietmar Saupe

2025-05-19T14:07:06Z

Literatur: + 2 Links: Heinz-Otto Peitgen, Dietmar Saupe

Neue Seite

[[Datei:Fractal weeds.jpg|mini|Künstliche Pflanzen, die durch 3D-L-Systeme generiert wurden]]

Bei den '''Lindenmayer-''' oder '''L-Systemen''' handelt es sich um einen [[Mathematik|mathematischen]] [[Formalisierte Theorie|Formalismus]], der 1968 von dem ungarischen [[Theoretische Biologie|theoretischen]] [[Biologe]]n [[Aristid Lindenmayer]] als Grundlage einer [[axiom]]atischen [[Theorie]] [[Ontogenese|biologischer Entwicklung]] vorgeschlagen wurde. In jüngerer Zeit fanden L-Systeme Anwendung in der [[Computergrafik]] bei der Erzeugung von [[Fraktal]]en 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 sogenannter [[Produktionsregel]]n. Diese Ersetzungen können [[rekursiv]] durchgeführt werden. Damit gehören L-Systeme zu den sogenannten [[Ersetzungssystem]]en.

Die bekanntesten Ersetzungssysteme sind solche, die auf Zeichenketten basieren. Besonders [[Noam Chomsky]]s Arbeiten aus den 1950ern über [[formale Grammatik]]en stießen auf großes Interesse und befruchteten die Forschung in der [[Theoretische Informatik|theoretischen Informatik]]. Im Gegensatz zu den sequentiellen Ersetzungsregeln in Chomskys Grammatiken finden Ersetzungen in L-Systemen parallel statt, analog zu den gleichzeitig stattfindenden [[Zellteilung]]en in [[Vielzeller|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 (Programmiersprache)|Logo]].

== Struktur eines L-Systems ==

Ein L-System ist ein [[Tupel|Quadrupel]] <math>G = \left(V, S, \omega, P\right)</math>, wobei

* V die Zeichen enthält, die als Variable angesehen werden sollen.
* S die Zeichen enthält, die als Konstanten angesehen werden sollen. Die Zeichen aus V und S bilden das Alphabet des L-Systems.
* ω ein Wort über dem Alphabet ist, welches als Startwort oder Axiom des L-Systems bezeichnet wird.
* P eine Menge von geordneten Paaren aus Wörtern über dem Alphabet ist, welche Ersetzungsregeln definieren. Ist das erste Wort eines jeden Paares ein einzelner Buchstabe aus V, und zu jeder Variablen eine Ersetzungsregel bekannt, so spricht man von einem kontextfreien L-System, sonst von einem [[Kontextsensitive Grammatik|kontextsensitiven]].

== Kontextfreie L-Systeme ==

Um ein L-System zu erzeugen, wird eine Tiefe n festgelegt, d. h., es werden Ersetzungsschritte wiederholt. In jedem Ersetzungsschritt wird das aktuelle Wort ω Zeichen für Zeichen abgearbeitet und jedes Zeichen durch das neue, in den Ersetzungsregeln festgelegte Wort ersetzt. Hierbei ist zu beachten, dass Zeichen, für die keine Ersetzungsregel definiert ist, nicht ersetzt werden.

Kontextfreie L-Systeme (auch 0L-Systeme genannt) enthalten Produktionen p, die auf ein Anfangswort ω (auch Axiom genannt) n-mal angewandt 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 Speicher ===
[[Datei:Koch Snowflake 7th iteration.svg|mini|Kochsche Schneeflocke]]
[[Datei:11_Order_Dragon_Curve.svg|mini|[[Drachenkurve]]]]

Viele der bekannteren Fraktale, wie das [[Sierpinski-Dreieck]] oder die [[Koch-Kurve]], können mittels L-Systemen über dem Alphabet <math>V={F}, S={+,-}</math> dargestellt werden. Es gibt nur eine einzige Ersetzungsregel für das Symbol <math>F</math>. Im Artikel [[Fraktal]] sind einige Beispiele aufgelistet. So hat das Kochsche Schneeflockenfraktal das Startwort <math>\omega=F--F--F</math> und die Ersetzungsregel <math>F \to F+F--F+F</math>.

Zur Interpretation eines solchen L-Systems mittels Turtle-Grafik benötigt man einen Stauchungsfaktor <math>s<1</math> und einen Winkel <math>a</math>. Mittels des Stauchungsfaktors wird die Weglänge bei Rekursionstiefe <math>n</math> als <math>s^n</math> bestimmt. Die Schildkröte besitzt keinen Speicher und führt die Symbole des Alphabets als folgende Kommandos sofort aus

*<math>F</math> : Bewegung nach vorn um Länge <math>s^n</math> und Zeichnung
* <math>+</math> : Drehung nach links, gegen Uhrzeigersinn, um den Winkel <math>a</math>
* <math>-</math> : Drehung nach rechts, im Uhrzeigersinn, um den Winkel <math>a</math>

Der Winkel <math>a</math> und der Faktor <math>s</math> sollten so abgestimmt sein, dass <math>F</math> mit Streckenlänge <math>1</math> und das Ersetzungswort von <math>F</math> zur Streckenlänge <math>s</math> 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. <math>V=\left\{R,L\right\}</math> und legt für dieses Beispiel <math>\omega=R</math> und <math>P=\left\{(R \to +R--L+), (L \to -R++L-)\right\}</math> fest. Beide Symbole werden in der Darstellung wie <math>F</math> 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:

* <math>f</math> : Bewegung nach vorn um Länge <math>s^n</math> ohne Zeichnung, variables Symbol,
* <math>|</math> : Drehung um 180 Grad, konstantes Symbol

=== Beispiel für Systeme mit Speicher ===

Es wird ein [[Last In – First Out|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:

* ''['' : Lege das aktuelle Koordinatensystem auf dem Stack ab
* '']'' : Stelle das oberste Koordinatensystem des Stacks als aktuelles wieder her.

Innerhalb eines Klammerpaars kann also ein im Leeren endender Zweig gezeichnet werden. Diese Möglichkeit wurde zur Darstellung fraktaler Bäume eingeführt.

== Kontextsensitive L-Systeme ==
Im Unterschied zu kontextfreien 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} (ist also links von a ein b, wird das a durch b ersetzt. Analog wird ein b zu a, wenn rechts davon ein b steht.)

: n=0 → baaa
: n=1 → bbaa
: n=2 → abba
: etc.

== Parametrische L-Systeme ==
Im 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 kontextsensitiven L-Systemen.
Beispiel: Sei <math>F(l)</math> ein Ast der Länge <math>l</math>. Die Produktionen <math>F(l) : l<10 \to F(l+1)</math> und <math>F(l) : l \ge 10 \to F(l+1)F(1)</math> lassen den Ast nun wachsen und ab einer bestimmten Länge (l=10) neue Äste entstehen.

== Pseudocode ==
Sei <math>L=(\Sigma,R,w_0)</math>. Dann beschreibt folgender Pseudocode das Vorgehen des L-Systems.

: 1. Setze aktuelle Zeichenkette auf <math>w_0</math>
: 2. Wiederhole unendlich oft:
: 2.1 Gib aktuelle Zeichenkette aus
: 2.2 Setze neue Zeichenkette auf <math>\varepsilon</math>
: 2.3 Wiederhole für jedes Zeichen <math>c</math> in der aktuellen Zeichenkette von links nach rechts:
: - Wenn möglich, wähle eine Regel <math>r \in R</math>, deren linke Seite <math>c</math> matcht.
: - Wenn ein solches <math>r</math> existiert, dann hänge die rechte Seite von <math>r</math> ans Ende der neuen Zeichenkette an.
: - Wenn ein solches <math>r</math> nicht existiert, dann hänge <math>c</math> an das Ende der neuen Zeichenkette an.
: 2.4 Mache die neue Zeichenkette zur aktuellen Zeichenkette.

* Zwei hintereinanderfolgende Ausgaben des Pseudocodes <math>w_i</math> und <math>w_{i+1}</math> schreibt man als <math>w_i</math> → <math>w_{i+1}</math>.
* Existiert ein <math>w_n</math>, so dass <math>w_0</math> → ... → <math>w_n</math> gilt, so nennt man <math>w_n</math> ''ableitbar''.
* Existiert ein ableitbares <math>w_n</math>, so dass für '''alle''' Regeln aus <math>R</math> gilt: <math>w_0</math> → ... → <math>w_n</math> → <math>w_n</math> → <math>w_n</math> → ... → <math>w_n</math>, so sagt man, <math>L</math> ''konvergiert'' gegen <math>w_n</math>.

== Siehe auch ==
* [[Formale Sprache]]n
* [[Selbstorganisation]]
* [[Selbstähnlichkeit]]
* [[Musterbildung]]
* [[L-System-Invertierungs-Problem]]

== Literatur ==
* Henning Fernau: ''Iterierte Funktionen, Sprachen und Fraktale''. B. I. Wissenschaftsverlag, Mannheim u. a. 1994, ISBN 3-411-17011-5, (''Aspekte komplexer Systeme'' 2).
* Grzegorz Rozenberg, Arto Salomaa: ''The Mathematical Theory of L-Systems''. Academic Press, New York NY u. a. 1980, ISBN 0-12-597140-0, (''Pure and Applied Mathematics'' 90).
* [[Przemysław Prusinkiewicz]], [[Aristid Lindenmayer]]: ''The Algorithmic Beauty of Plants''. Springer Verlag, New York NY u. a. 1990, ISBN 3-540-97297-8, (''The virtual Laboratory'').
* Elaine Rich: ''Automata, Computability and Complexity: Theory and Applications.'' Prentice Hall, Upper Saddle River (NJ) u. a. 2008, ISBN 978-0-13-228806-4.
* [[Heinz-Otto Peitgen]], Hartmut Jürgens, [[Dietmar Saupe]]: ''Chaos, Bausteine der Ordnung''. Springer, Berlin u. a. 1994, ISBN 978-3608954357.

== Weblinks ==
{{Commons|L-system|L-System}}
* [http://www.matheprisma.de/Module/Lmayer/index.htm Matheprisma – Lindenmayersysteme] (»Iterationen in Ersetzungssystemen oder: wie Kröten Pflanzen zeichnen«)
* [http://olli.informatik.uni-oldenburg.de/lily/LP/start.html Lily: Eine interaktive Lernumgebung zum Thema]
* [http://www.kevs3d.co.uk/dev/lsystems/ Demo in HTML5 zum Generieren von Lindenmayer-Systemen] (englisch)
* [http://weitz.de/lindenmayer/ Lindenmayer systems] (Programm zum Erzeugen, Bearbeiten und Visualisieren von Lindenmayer-Systemen)
*[https://www.p-roocks.de/lsystem/ lsystem] (Interaktiver Generator für Lindenmayer-Systeme, Open Source, verfügbar für Linux und Windows, englisch)

{{Normdaten|TYP=s|GND=4074246-5|LCCN=sh/85/073593}}

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Fraktale Geometrie]]

Lindenmayer-System - Versionsgeschichte

imported>Docosanus: /* Literatur */ + 2 Links: Heinz-Otto Peitgen, Dietmar Saupe