Ein System von L-system oder Lindenmayer ist ein paralleles Neuschreiben-System, nämlich eine Variante einer formellen Grammatik, am berühmtesten verwendet, um die Wachstumsprozesse der Pflanzenentwicklung, sondern auch fähig zu modellieren, die Morphologie einer Vielfalt von Organismen zu modellieren. Ein L-System besteht aus einem Alphabet von Symbolen, die verwendet werden können, um Schnuren, eine Sammlung von Produktionsregeln zu machen, die jedes Symbol in eine größere Reihe von Symbolen, eine anfängliche "Axiom"-Schnur ausbreiten, von der man Aufbau und einen Mechanismus beginnt, für die erzeugten Schnuren in geometrische Strukturen zu übersetzen. L-Systeme können auch verwendet werden, um selbstähnlichen fractals wie wiederholte Funktionssysteme zu erzeugen. L-Systeme wurden eingeführt und 1968 vom ungarischen theoretischen Biologen und Botaniker von der Universität Utrechts, Aristid Lindenmayer (1925-1989) entwickelt.

Ursprünge

Als ein Biologe hat Lindenmayer mit der Hefe und den filamentous Fungi gearbeitet und hat die Wachstumsmuster von verschiedenen Typen von Algen wie die blauen/grünen Bakterien Anabaena catenula studiert. Ursprünglich wurden die L-Systeme ausgedacht, um eine formelle Beschreibung der Entwicklung solcher einfachen Mehrzellorganismen zur Verfügung zu stellen, und die Nachbarschaft-Beziehungen zwischen Pflanzenzellen zu illustrieren. Später wurde dieses System erweitert, um höhere Werke und komplizierte sich verzweigende Strukturen zu beschreiben.

L-Systemaufbau

Die rekursive Natur der L-Systemregeln führt zu Selbstähnlichkeit, und dadurch sind fractal ähnliche Formen leicht, mit einem L-System zu beschreiben. Pflanzenmodelle und natürlich aussehende organische Formen sind leicht, als durch die Erhöhung des recursion Niveaus zu definieren, das die Form langsam 'anbaut' und komplizierter wird. Systeme von Lindenmayer sind auch in der Generation des künstlichen Lebens populär.

L-Systemgrammatiken sind der semi-Thue Grammatik sehr ähnlich (sieh Hierarchie von Chomsky). L-Systeme sind jetzt als parametrische L Systeme allgemein bekannt, die als ein Tupel definiert sind

:G = (V, ω, P),

wo

• V (das Alphabet) ist eine Reihe von Symbolen, die Elemente enthält, die (Variablen) ersetzt werden können
• ω (Anfang, Axiom oder Initiator) ist eine Reihe von Symbolen vom V Definieren des anfänglichen Staates des Systems
• P ist eine Reihe von Produktionsregeln oder Produktion, die die Weise definiert, wie Variablen durch Kombinationen von Konstanten und anderen Variablen ersetzt werden können. Eine Produktion besteht aus zwei Schnuren, dem Vorgänger und dem Nachfolger. Für jedes Symbol in V, der linker Hand Seite einer Produktion in P, der Identitätsproduktion nicht erscheint, wird Ein  A angenommen; diese Symbole werden Konstanten oder Terminals genannt.

Die Regeln der L-Systemgrammatik werden wiederholend angewandt, vom anfänglichen Staat anfangend. So viele Regeln werden wie möglich gleichzeitig pro Wiederholung angewandt; das ist das Unterscheidungsmerkmal zwischen einem L-System und der formellen durch eine formelle Grammatik erzeugten Sprache. Wenn die Produktionsregeln nur einer nach dem anderen angewandt werden sollten, würde man ganz einfach eine Sprache, aber nicht ein L-System erzeugen. So sind L-Systeme strenge Teilmengen von Sprachen.

Ein L-System ist ohne Zusammenhänge, wenn sich jede Produktionsregel nur auf ein individuelles Symbol und nicht auf seine Nachbarn bezieht. L-Systeme ohne Zusammenhänge werden so entweder durch eine Präfix-Grammatik oder durch eine regelmäßige Grammatik angegeben. Wenn eine Regel nicht nur von einem einzelnen Symbol sondern auch von seinen Nachbarn abhängt, wird sie ein mit dem Zusammenhang empfindliches L-System genannt.

Wenn es genau eine Produktion für jedes Symbol gibt, dann, wie man sagt, ist das L-System deterministisch (ein deterministisches L-System ohne Zusammenhänge wird ein D0L-System populär genannt). Wenn es mehrere gibt, und jeder mit einer bestimmten Wahrscheinlichkeit während jeder Wiederholung gewählt wird, dann ist es ein stochastisches L-System.

Das Verwenden von L-Systemen, um grafische Images zu erzeugen, verlangt, dass sich die Symbole im Modell auf Elemente eines Stützens auf den Computerschirm beziehen. Zum Beispiel verwendet das Programm Fractint Schildkröte-Grafik (ähnlich denjenigen auf der Firmenzeichen-Programmiersprache), um Schirm-Images zu erzeugen. Es interpretiert jede Konstante in einem L-Systemmodell als ein Schildkröte-Befehl.

Beispiele von L-Systemen

Beispiel 1: Algen

Das ursprüngliche L-System von Lindenmayer, für das Wachstum von Algen zu modellieren.

:variables: Ein B

:constants: niemand

:start: Ein

:rules: (Ein  AB), (B )

der erzeugt:

: n = 0: Ein

: n = 1: AB

: n = 2: ABA

: n = 3: ABAAB

: n = 4: ABAABABA

: n = 5: ABAABABAABAAB

: n = 6: ABAABABAABAABABAABABA

: n = 7: ABAABABAABAABABAABABAABAABABAABAAB

Beispiel 1: Algen, hat erklärt

n=0: Ein Anfang (Axiom/Initiator)

/ \

n=1: Ein B die anfängliche Single Ein erzeugter in AB durch die Regel (Ein  AB), Regel (B  A) konnte nicht angewandt werden

/ | \

n=2: Ein B Eine ehemalige Schnur, die AB mit allen Regeln, Ein erzeugter in AB wieder, ehemaliger B angewandt hat, hat sich In einen verwandelt

/ | | | \

n=3: Ein B bemerkt Ein B das Produzieren ganzen A eine Kopie von sich an erster Stelle, dann ein B, der sich dreht...

/ | | | \| \\

n=4: Ein B Ein B Ein B A... in eine Generation später, anfangend, dann zu laichen zu/wiederholen/wiederzuverfluchen

Wenn wir die Länge jeder Schnur aufzählen, erhalten wir die berühmte Folge von Fibonacci von Zahlen (den ersten 1, wegen unserer Wahl des Axioms auslassend):

: 1 2 3 5 8 13 21 34 55 89...

Für jede Schnur, wenn wir die k-th Position vom linken Ende der Schnur aufzählen, wird der Wert dadurch bestimmt, ob ein Vielfache der goldenen Mitte innerhalb des Zwischenraums fällt. Das Verhältnis zu B läuft ebenfalls zur goldenen Mitte zusammen.

Dieses Beispiel gibt dasselbe Ergebnis nach (in Bezug auf die Länge jeder Schnur, nicht die Folge Als und Bakkalaureus der Naturwissenschaften), wenn die Regel (Ein  AB) dadurch ersetzt wird (Ein  BA), außer dass die Schnuren widergespiegelt werden.

Diese Folge ist lokal catenative Folge, weil, wo die n-te Generation ist.

Beispiel 2

• Variablen: 0, 1
• Konstanten:
• Axiom: 0
• Regeln: (1  11), (0  1 [0] 0)

Die Gestalt wird durch die rekursive Fütterung des Axioms durch die Produktionsregeln gebaut. Jeder Charakter der Eingangsschnur wird gegen die Regel-Liste überprüft, um zu bestimmen, den Charakter oder Schnur, um es durch in der Produktion zu ersetzen, spannen. In diesem Beispiel, '1' in der Eingangsschnur wird '11' in der Produktionsschnur, während '' dasselbe bleibt. Das auf das Axiom '0' anwendend, kommen wir:

Wir können sehen, dass diese Schnur schnell in der Größe und Kompliziertheit wächst. Diese Schnur kann als ein Image durch das Verwenden der Schildkröte-Grafik gezogen werden, wo jedes Symbol eine grafische Operation wegen der Schildkröte zugeteilt wird, um zu leisten. Zum Beispiel, in der Probe oben, können der Schildkröte den folgenden Weisungen erteilt werden:

• 0: ziehen Sie ein Liniensegment, das in einem Blatt endet
• 1: ziehen Sie ein Liniensegment
• : stoßen Sie Position und Winkel, werden Sie link 45 Grade
• : Knall-Position und Winkel, biegen Sie 45 Grade nach rechts ab

Der Stoß und Knall beziehen sich auf einen LIFO-Stapel (mehr technische Grammatik würde getrennte Symbole für die "Stoß-Position" haben und "nach links biegen"). Wenn sich die Schildkröte-Interpretation begegnet'' werden die aktuelle Position und der Winkel gespart, und werden dann wieder hergestellt, wenn sich die Interpretation '' begegnet. Wenn vielfache Werte," dann "gestoßen worden sind, stellt ein "Knall" die am meisten kürzlich gesparten Werte wieder her. Das Anwenden der grafischen Regeln hat oben zu früher recursion Schlagseite gehabt, wir kommen:

Beispiel 3: Kantor-Staub

: Variablen: Ein B

: Konstanten: niemand

: Anfang: {Anfangszeichen-Schnur }\

: Regeln: (Ein  ABA), (B  BBB)

Lassen Sie Einen bösartigen "vorwärts ziehen", und bösartige B "kommen voran".

Das erzeugt den Fractal-Satz des berühmten Kantoren auf einer echten Gerade R.

Beispiel 4: Kurve von Koch

Eine Variante der Kurve von Koch, die nur richtige Winkel verwendet.

: Variablen: F

: Konstanten: +

−

: Anfang: F

: Regeln: (F  F+F−F−F+F)

Hier bedeutet F "ziehen vorwärts", + bedeutet, dass "Umdrehung 90 °", und &minus verlassen hat; bedeutet "biegen 90 ° nach rechts ab" (sieh Schildkröte-Grafik).

: n = 0:

:: F

::

: n = 1:

::

F+F−F−F+F ::

: n = 2:

:: F+F−F−F+F + F+F−F−F+F − F+F−F−F+F − F+F−F−F+F +

F+F−F−F+F ::

: n = 3:

:: F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F +

::F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

−

:: F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F

− :: F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F +

::

F+F−F−F+F+F+F−F−F+F−F+F−F−F+F−F+F−F−F+F+F+F−F−F+F ::

Beispiel 5: Penrose tilings

Die folgenden Images wurden durch ein L-System erzeugt. Sie sind verbunden und sehr ähnlich Penrose tilings, erfunden von Roger Penrose.

Als ein L-System werden diese tilings die Rhomben von Penrose und die Ziegel von Penrose genannt. Die obengenannten Bilder wurden für n = 6 als ein L-System erzeugt. Wenn wir richtig Ziegel von Penrose als ein L-System superauferlegen, bekommen wir folgend mit Ziegeln zu decken:

sonst bekommen wir Muster, die keine unendliche Oberfläche völlig bedecken:

Beispiel 6: Dreieck von Sierpinski

Das gezogene Dreieck von Sierpinski mit einem L-System.

: Variablen: Ein B

: Konstanten: +

−

: Anfang: Ein

: Regeln: (Ein  B−A−B), (B  A+B+A)

: Winkel: 60°

Hier ziehen A und B sowohl bösartig "vorwärts", + bedeutet "biegen durch den Winkel", als auch &minus nach links; bedeutet "biegen durch den Winkel nach rechts ab" (sieh Schildkröte-Grafik). Der Winkel ändert Zeichen bei jeder Wiederholung, so dass die Basis der Dreiecksgestalten immer im Boden ist (sie würden in der Spitze und dem Boden, wechselweise, sonst sein).

Es gibt eine andere Weise, das Dreieck von Sierpinski mit einem L-System zu ziehen.

: Variablen: F G

: Konstanten: + −

: Anfang:

F−G−G

: Regeln: (F  F−G+F+G−F), (G  GG)

: Winkel: 120°

Hier ziehen F und G sowohl bösartig "vorwärts", + bedeutet "biegen durch den Winkel", als auch &minus nach links; bedeutet "biegen durch den Winkel nach rechts ab".

Beispiel 7: Drache-Kurve

Die gezogene Drache-Kurve mit einem L-System.

: Variablen: X Y

: Konstanten: F +

−

: Anfang: FX

: Regeln: (X  X+YF), (Y  FX-Y)

: Winkel: 90°

Hier bedeutet F "ziehen vorwärts", - bedeutet, dass "Umdrehung 90 ° verlassen hat", und + bedeutet, "biegen 90 ° nach rechts ab". X und Y entsprechen keiner Zeichnungshandlung und werden nur verwendet, um die Evolution der Kurve zu kontrollieren.

Beispiel 8: Werk von Fractal

: Variablen: X F

: Konstanten: + −

: Anfang: X

: Regeln: (X  F-[X] +X] +F [+FX]-X), (F  FF)

: Winkel: 25°

Hier bedeutet F "ziehen vorwärts", - bedeutet, dass "Umdrehung 25 ° verlassen hat", und + bedeutet, "biegen 25 ° nach rechts ab". X entspricht keiner Zeichnungshandlung und wird verwendet, um die Evolution der Kurve zu kontrollieren. [entspricht dem Sparen der aktuellen Werte für die Position und den Winkel, die wieder hergestellt werden, wenn das Entsprechen] durchgeführt wird.

Beispiel 9: Modifiziertes L-System von Koch

Ein fractal glaubt, dass das gezogene Einführen einer periodischen Änderung des Winkelzeichens in der Wiederholung des üblichen Kochs L-System biegt.

Schwankungen

Mehrere Weiterentwicklungen auf dieser grundlegenden L-Systemtechnik sind entwickelt worden, der in Verbindung mit einander verwendet werden kann. Unter diesen, sind Zusammenhang empfindliche und parametrische Grammatiken stochastisch.

Stochastische Grammatiken

Das Grammatik-Modell, das wir so weit besprochen haben, ist deterministisch gewesen — d. h. hat jedes Symbol im Alphabet der Grammatik gegeben, es hat genau eine Produktionsregel gegeben, die immer gewählt wird, und immer dieselbe Konvertierung durchführt. Eine Alternative soll mehr als eine Produktionsregel für ein Symbol angeben, jedem eine Wahrscheinlichkeit des Auftretens gebend. Zum Beispiel, in der Grammatik des Beispiels 2, konnten wir die Regel ändern, um "0" umzuschreiben, von:

:0  1 [0] 0

zu einer Probabilistic-Regel:

:0 (0.5)  1 [0] 0

:0 (0.5)  0

Unter dieser Produktion, wann auch immer "0" während des Schnur-Neuschreibens gestoßen wird, würde es eine 50-%-Chance geben es, würde sich wie vorher beschrieben, und eine 50-%-Chance benehmen, die es während der Produktion nicht ändern würde. Wenn eine stochastische Grammatik in einem Entwicklungszusammenhang verwendet wird, ist es ratsam, einen zufälligen Samen in den Genotypen zu vereinigen, so dass die stochastischen Eigenschaften des Images unveränderlich zwischen Generationen bleiben.

Zusammenhang empfindliche Grammatiken

Empfindliche Produktionsregel eines Zusammenhangs schaut nicht nur auf das Symbol, das sie modifiziert, aber die Symbole auf der Schnur, die vorher und danach erscheint. Zum Beispiel, die Produktionsregel:

:b

gestaltet "a" in "aa" um, aber nur Wenn ein Vorkommen zwischen einem "b" und einem "c" im Eingang spannt:

: … bac …

Als mit der stochastischen Produktion gibt es vielfache Produktion, um Symbole in verschiedenen Zusammenhängen zu behandeln. Wenn keine Produktionsregel für einen gegebenen Zusammenhang gefunden werden kann, wird die Identitätsproduktion angenommen, und das Symbol ändert sich auf der Transformation nicht. Wenn mit dem Zusammenhang empfindliche und Produktion ohne Zusammenhänge beide innerhalb derselben Grammatik besteht, wie man annimmt, hat die mit dem Zusammenhang empfindliche Produktion den Vortritt, wenn es anwendbar ist.

Parametrische Grammatiken

In einer parametrischen Grammatik hat jedes Symbol im Alphabet eine damit vereinigte Parameter-Liste. Ein mit seiner Parameter-Liste verbundenes Symbol wird ein Modul genannt, und eine Schnur in einer parametrischen Grammatik ist eine Reihe von Modulen. Eine Beispiel-Schnur könnte sein:

:a (0,1) [b (0,0)] (1,2)

Die Rahmen können durch die Zeichnungsfunktionen, und auch durch die Produktionsregeln verwendet werden. Die Produktionsregeln können die Rahmen auf zwei Weisen verwenden: Erstens in einer bedingten Behauptung, die bestimmt, ob die Regel, und zweitens gelten wird, kann die Produktionsregel die wirklichen Rahmen modifizieren. Schauen Sie zum Beispiel auf:

:a (x, y): x = 0  (1, y+1) b (2,3)

Das Modul (x, y) erlebt Transformation laut dieser Produktionsregel, wenn der bedingte x=0 entsprochen wird. Zum Beispiel, (0,2) würde Transformation erleben, und (1,2) würde nicht.

Im Transformationsteil der Produktionsregel können die Rahmen sowie kompletten Module betroffen werden. Im obengenannten Beispiel wird das Modul b (x, y) zur Schnur, mit anfänglichen Rahmen (2,3) hinzugefügt. Außerdem werden die Rahmen des bereits vorhandenen Moduls umgestaltet. Laut der obengenannten Produktionsregel,

:a (0,2)

Wird

:a (1,3) b (2,3)

weil der "x" Parameter (x, y) in "1" und der "y" Parameter ausführlich umgestaltet wird, erhöht von einem zu sein.

Parametrische Grammatiken erlauben Linienlängen und sich verzweigenden Winkeln, durch die Grammatik, aber nicht die Schildkröte-Interpretationsmethoden bestimmt zu werden. Außerdem, wenn Alter als ein Parameter für ein Modul gegeben wird, können sich Regeln abhängig vom Alter eines Pflanzensegmentes ändern, Zeichentrickfilme des kompletten Lebenszyklus des Baums erlaubend, geschaffen zu werden.

Offene Probleme

Es gibt viele offene Probleme, die Studien von L-Systemen einschließen. Zum Beispiel:

• Die Charakterisierung aller deterministischen L-Systeme ohne Zusammenhänge, die lokal catenative sind. (Eine vollständige Lösung ist nur im Fall bekannt, wo es nur zwei Variablen gibt).
• In Anbetracht einer Struktur, finden Sie ein L-System, das diese Struktur erzeugen kann.

Typen von L-Systemen

L-Systeme auf der echten Linie R:

• Prouhet-Thue-Morse System

Wohl bekannte L-Systeme auf einem Flugzeug R sind:

• raumfüllende Kurven (Kurve von Hilbert, die Kurven von Peano, die Kirche von Dekking, kolams),
• raumfüllende Mittelkurven (Lévy C Kurve, Harter-Heighway Drache-Kurve, Davis-Knuth terdragon),
• tilings (Sphinx mit Ziegeln deckend, Penrose, der mit Ziegeln deckt),
• Bäume, Werke, und ähnlich.

Bücher

• Przemyslaw Prusinkiewicz, Aristid Lindenmayer - Die Algorithmische Schönheit von Werken PDF Version verfügbar hier für freien
• Grzegorz Rozenberg, Arto Salomaa - Lindenmayer Systeme: Einflüsse auf Theoretische Informatik, Computergrafik und internationale Entwicklungsbiologie-Standardbuchnummer 978-3-540-55320-5
• D.S. Ebert, F.K. Musgrave, u. a. - Texturing und Modeling: Eine Verfahrensannäherung, internationale Standardbuchnummer 0-12-228730-4

Siehe auch

• Digitaler morphogenesis
• Fractal
• Wiederholtes Funktionssystem
• Hilbert biegen
• Stochastische Grammatik ohne Zusammenhänge

Zeichen

Links

• Algorithmische Botanik an der Universität Calgarys
• Das Ausbreiten: TreeA L-Systemjava applet und sein Quellcode (öffnen Quelle), der botanischen Baumwachstumssimulation mit dem L-System.
• Fractint L-System wahrer Fractals
• "Kraftwerk" eine Landschaft-Modellieren-Software der offenen Quelle
• Fractint Hausseite
• Ein einfacher L-Systemgenerator (Windows)
• Lyndyhop: ein anderer einfacher L-Systemgenerator (Windows & Mac)
• Ein EntwicklungsL-Systemgenerator (anyos *)
• "LsystemComposition". Seite an Pawfal ("arme Künstler, die für ein Leben arbeiten") über das Verwenden von L-Systemen und genetischen Algorithmen, um Musik zu erzeugen.
• verlängerte L-Systeme (XL), Verwandtschaftswachstumsgrammatiken und Softwareplattform der offenen Quelle GroIMP.
• JAVA applet mit vielen durch L-Systeme erzeugten Fractal-Zahlen.
• MusikL-Systeme: Theorie und Anwendungen über das Verwenden von L-Systemen, um Musikstrukturen von Wellenformen bis Makroformen zu erzeugen.
• Online-Experimente mit L-Systemen mit JSXGraph (JavaScript)
• Floh Eine Rubinrote Durchführung von LSYSTEM, mit einem Gebiet Spezifische Sprache statt des knappen Generators befiehlt
• Lindenmayer treiben Ein Werk und fractal Generator-Verwenden-L-Systeme (JavaScript) an