Lindenmayer-Systeme
Bei den Lindenmayer- oder L-Systemen handelt es sich um einen mathematischen Formalismus, der 1968 von dem 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.
In der grafischen Programmierung werden L-Systeme sehr oft durch die sogenannte TURTLE-Interpretation eingesetzt.
| Inhaltsverzeichnis |
Struktur eines L-Systems
Ein L-System ist ein Quadrupel G = {V, S, ω, P}, 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 kontext-sensitiven.
Kontext-freie L-Systeme
Um 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.
Kontext-sensitive L-Systeme
Im 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 ein der linke Kontext durch < vom zu ersetzenden Zeuchen 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 → abaa
- n=2 → aaba
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 Prduktionsregeln 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.
Siehe auch
formale Sprachen, Selbstorganisation, Selbstähnlichkeit, Musterbildung, Fraktale
Weblinks
- http://www.biologie.uni-hamburg.de/b-online/e28_3/lsys.html An Introduction to Lindenmayer Systems (auf Englisch)