Das Lindenmayer-System als eine formale Grammatik zur Beschreibung von Fraktalen

Das Lindenmayer-System wurde ursprünglich von Aristid Lindenmayer zum Zwecke der entwicklungstheoretischen Beschreibung von Organismen entwickelt. Als einfaches Beispiel kann man sich eine mehrzellige Alge vorstellen. Möge das Symbol "F" eine Zelle dieser Alge repräsentieren. Dann kann man eine Zellteilung durch den "Übergang" von F zu FF repräsentieren. Dies kann man symbolisch durch F -> FF ausdrücken.
Für die beiden vorhandenen Zellen "FF" kann man nun abermals eine parallele Ersetzung F ->  FF vornehmen. Man erhält FFFF. Im nächsten Schritt erhält man  FFFFFFFF usw. Ist F..F eine Sequenz so ist klar wie man mit der vorgegebenen Regel F -> FF die nächste Sequenz erzeugt wird. In diesem Sinne ist das hier gezeigte Wachstumsmodell deterministisch.

(Labeled[, "Bsp. einfaches Wachstumsmodell einer Alge"])

Durch die Einführung weiterer Symbole ist es nun möglich kompliziertere Strukturen zu bilden. Um diese Ideen auf eine stabilere Grundlage zu stellen, werden zunächst einige Definitionen benötigt.

Definition
Sei 𝒜 eine nichtleere Menge von Symbolen, dann heißt 𝒜 Alphabet.

Beispiele:
a) 𝒜 = {a,b,c,d,e}
b) ℬ = {[,k,l,³,ι,n,e,]}

Definition
Mit (SuperStar[𝒜]) = (⋃_(n=0)^∞) (𝒜^n) wird die Menge aller Wörter bezeichnet aus dem Alphabet 𝒜 beizeichnet. ϵ ∈ (𝒜^0) ist das leere Wort. Des Weiteren ist (SuperPlus[𝒜]) := (SuperStar[𝒜])\{ϵ }. Anstatt ((Subscript[x, 1]),(Subscript[x, 2]),...,(Subscript[x, n])) ∈ (SuperStar[𝒜]) mit (Subscript[x, i])∈ 𝒜 schreibt man 
einfach (Subscript[x, 1])(Subscript[x, 2])...(Subscript[x, n]).  
Seien  a = (Subscript[a, 1])(Subscript[a, 2])(Subscript[a, 3])...(Subscript[a, k]) mit a∈ (𝒜^k) und b = (Subscript[b, 1])(Subscript[b, 2])(Subscript[b, 3])...(Subscript[b, j]) mit b ∈ (𝒜^j), dann ist die Multiplikation · durch (𝒜^(k+j)) ∋ a· b = ab = (Subscript[a, 1])(Subscript[a, 2])(Subscript[a, 3])...(Subscript[a, k])(Subscript[b, 1])(Subscript[b, 2])(Subscript[b, 3])...(Subscript[b, j]) definiert.

Beispiele:
a) 𝒶 = ab ∈ (SuperStar[𝒜]), 𝒷 = acccde ∈ (SuperStar[𝒜]) , 𝒶𝒷  =  abaccde 
b) [e³] ∈ (SuperStar[ℬ]), ιn ∈ (SuperStar[ℬ])

Definition
Unter einem deterministischen 0L-System (D0L-System) S versteht man ein Tripel (𝒜,P,ω). 𝒜 ist ein Alphabet.  P ⊂ 𝒜×(SuperStar[𝒜]) ist eine Funktion von 𝒜 nach (SuperStar[𝒜]) und wird als Menge aller Produktionsregeln 
bezeichnet. Für (a,α) ∈ P schreibt man a -> α. Schließlich ist ω ∈ 𝒜 das Startwort. Seien a = (Subscript[a, 1])(Subscript[a, 2])..(Subscript[a, n]) mit (Subscript[a, i]) ∈ 𝒜 und b = (Subscript[b, 1])(Subscript[b, 2])...(Subscript[b, k]) mit (Subscript[b, i]) ∈ 𝒜 Wörter aus 𝒜 dann sagt man b werde (im Sinne von S) aus 
a erzeugt falls gilt: b = (Subscript[α, 1])(Subscript[α, 2])...(Subscript[α, i]) mit ((Subscript[a, i]),(Subscript[α, i]))∈P. Hierfür schreiben wir einfach a (Underscript[\[Implies], G]) b oder a \[Implies] b wenn klar ist welches D0L-System gemeint ist.

Beispiele für D0L - Systeme

Das zu Anfang beschriebene Beispiel lässt sich nun mit dem folgenden D0L-System identifizieren:

  (Subscript[S, 0]) = ({F},{F-> FF}, {F})
   
Die einzelnen Wörter (Subscript[ω, i]) des iten Iterationsschrittes wurden im Beispiel jeweils aus dem Vorgänger erzeugt, wobei das Startwort F der Ausgang war. Es gilt:
ω = (Subscript[ω, 0]) = F
(Subscript[ω, 1]) = FF              mit (Subscript[ω, 0])=> (Subscript[ω, 1]) 
(Subscript[ω, 2]) = FFFF          mit (Subscript[ω, 1])=> (Subscript[ω, 2]) 
(Subscript[ω, 3]) = FFFFFFFF  mit (Subscript[ω, 2])=> (Subscript[ω, 3])
usw.   
Die Zuordnung, im Sinne der Erzeugung, des jeweils nachfolgenden Elementes aus dem Vorgänger ist aufgrund des Determinismus (P ist als Funktion definiert) immer eindeutig.

Die Kochsche Schneeflockenkurve

Die Kochsche Schneeflockenkurve kann durch das folgende D0L - System dargestellt werden.

   (Subscript[S, 1]) = ( {F,-,+}, {F -> F+F--F+F, + -> +, - -> -}, {F})
   
Um das zu sehen, interpretiert man die durch S generierten Wörter als Zeichenanweisungen (einer Turtle-Grafik ) wie folgt: Bezüglich eines "Blatt Papieres" hat man ein zweites frei bewegliches "Referenzsystem" (das ist die Schildkröte). Zu Beginn wählt man den Ursprung und die Orientierung des Referenzsystems. 

1. F bedeutet: Zeichne im Referenzsystem einen Strich in x-Richtung. Falls nichts anderes vereinbart ist, ist die Länge (Größe legt man vorher fest) aller Striche konstant.
2. - bedeutet: Drehe Referenzsystem bezüglich des äußeren Blattes um einen bestimmten Winkel (die Größe des Winkels legt man vorher fest; konstant falls nicht anders vereinbart) in mathematisch negativer Richtung. Im Fall der Kochschen Schneeflockenkurve beträgt unser Winkelinkrement immer 60°C.
3. + bedeutet: Drehe Referenzsystem bezüglich des äußeren Blattes in mathematisch positiver Richtung um das Winkelinkrement. 

Wendet man auf das Startwort F die Produktionsregel iterativ an, so erhält man im Falle des Systems (Subscript[S, 1]) folgende Wörter:

ω = (Subscript[ω, 0])= F
(Subscript[ω, 1])= F+F--F+F
(Subscript[ω, 2])= F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+F
(Subscript[ω, 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
(Subscript[ω, 4])= 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+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--F+F+F+F--F+F
usw.

Wie damit die Kochsche Schneeflockenkurve codiert wird, zeigt das folgende Programm. 
Man sieht wie die Zeichenkette interpretiert wird, wenn man sie von Anfang an bis zu einer gewissen Länge zeichnet. Schwarze Linien kennzeichnen "bereits gezeichnete" Linien. Die rote Linie zeigt an welche Linie man erhält, wenn man die Anweisung "F" noch ausführen würde.

wird noch ev. ergänzt...