L-System - Définition

Exemples et notations de L-Systems simples

Exemple 1 : l'algue de Lindenmayer

Voici le premier L-System d'Aristid Lindenmayer qui servait à décrire le développement d'une algue :

• Alphabet : V = {A, B}
• Constantes : S = {}
• Axiome de départ : w = A
• Régles : (A → AB) ∧ (B → A)

Notation :

Algue
{
Axiom A
A=AB
B=A
}

Algue est le nom du L-System. En premier on a l'axiome ω, puis chaque règle de P est à la ligne l'une de l'autre. A=AB est à comprendre comme tout symbole A devient un « mot » AB à la génération suivante.

Voici le résultat sur six générations :

• n=0, A
• n=1, AB
• n=2, AB A
• n=3, AB A AB
• n=4, AB A AB AB A
• n=5, AB A AB AB A AB A AB
• n=6, AB A AB AB A AB A AB AB A AB AB A

Exemple 2 : la suite de Fibonacci

• Alphabet : V = {A, B}
• Constantes : S = {}
• Axiome de départ : w = A
• Régles : (A → B) ∧ (B → AB)

Notation :

Algue
{
Axiom A
A=B
B=AB
}

Voici le résultat sur six générations :

• n=0, A
• n=1, B
• n=2, AB
• n=3, B AB
• n=4, AB B AB
• n=5, B AB AB B AB
• n=6, AB B AB B AB AB B AB

Si on compte le nombre de symboles à chaque génération, on obtient la suite de Fibonacci :

• n=0, 1 symbole
• n=1, 1 symbole
• n=2, 2 symboles
• n=3, 3 symboles
• n=4, 5 symboles
• n=5, 8 symboles
• n=6, 13 symboles

SOL-System ou Stochastic O-context System

Comme son nom l'indique, ce système fait appel aux probabilités, il est aussi appelé système non-déterministe. Contrairement au DOL-System, il est possible de déterminer plusieurs transformations pour un symbole. Chaque possibilité sera pondérée pour pouvoir donner priorité à certaines transformations par rapport à d'autres.

Exemple de SOL-System

On pourrait étoffer l'exemple du DOL-System, on s'en contentera pour rester sur quelque chose de simple, même si ça n'aurait que peu d'intérêt graphiquement :

• Variable : V = {F, X}
• Constantes : S = {+, −, [, ]}
• Axiome : w = X
• Règles : (X → F[+X]F[−X]+X) ^ (F → FF)

Plante_Stochastique
{
angle 20
axiom X
X=(0.2)F[++X]F[−X]+X
X=(0.8)F[+X]F[−X]+X
F=(1.0)FF
}

Voici un résultat possible sur deux générations :

• n=0, X
• n=1, F[++X]F[−X]+X
• n=2, FF[++F[+X]F[−X]+X]FF[−F[+X]F[−X]+X]+F[+X]F[−X]+X

Voici un autre résultat possible sur deux générations :

• n=0, X
• n=1, F[+X]F[−X]+X
• n=2, F[+F[++X]F[−X]+X]F[−F[++X]F[−X]+X]+F[++X]F[−X]+X

Il y a 2²=4 possibilités possibles sur deux générations.

(0.2), (0.8) et (1.0) représentent les poids de chaque transformation possible de X et de F.

DOL-System ou Determinist O-context System

Ce système est déterministe, i.e. qu'il n'offre qu'une seule évolution possible depuis l'axiome à la énième génération. Une cause engendre un effet, ce qui se traduit par : une variable ne peut subir qu'un seul type de transformation, toujours identique, donc une seule règle par variable. L'exemple ci-dessus était un DOL-System, il s'agit de la forme la plus simple de L-System.

Exemple de DOL-System

• Variable : V = {F, X}
• Constantes : S = {+, −, [, ]}
• Axiome : w = X
• Règles : (X → F[+X]F[−X]+X) ^ (F → FF)

Plante
{
angle 20
axiom X
X=F[+X]F[−X]+X
F=FF
}

angle 20 détermine de quel angle on tourne avec les symboles + et -.

Voici le résultat sur deux générations :

• n=0, X
• n=1, F[+X]F[−X]+X
• n=2, FF[+F[+X]F[−X]+X]FF[−F[+X]F[−X]+X]+F[+X]F[−X]+X