L-Système

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un L-Système ou système de Lindenmayer est une grammaire formelle, inventée en 1968 par le biologiste hongrois Aristid Lindenmayer, qui consiste à modéliser le processus de développement et de prolifération de plantes ou de bactéries.

C'est une forme de grammaire générative. Cette grammaire a été mise en œuvre graphiquement par de nombreux auteurs, menant à de spectaculaires images. Une étude systématique d'une certaine formulation a été entreprise par Przemyslaw Prusinkiewicz dans les années 1980.

Au départ, Lindenmayer conçoit sa formalisation comme un modèle de langages formels qui permet de décrire le développement d'organismes multicellulaires simples. À cette époque il travaille sur les levures, les champignons et des algues. Mais sous l'influence des théoriciens et des praticiens de l'informatique, ce système a conduit à des familles de langages formels et aussi à des méthodes pour générer graphiquement des plantes idéalisées très complexes.

Un L-système est un ensemble de règles et de symboles qui modélisent un processus de croissance d'êtres vivants comme des plantes ou des cellules. Le concept central des L-systèmes est la notion de réécriture. La réécriture est une technique pour construire des objets complexes en remplaçant des parties d'un objet initial simple en utilisant des règles de réécriture.

Dans l'interprétation biologique, les cellules sont modélisées à l'aide de symboles. À chaque génération, les cellules se divisent, ce qui est modélisé par l'opération consistant à remplacer un symbole par un ou plusieurs autres symboles consécutifs.

Mauvaises herbes, générées par un programme de L-systèmes en trois dimensions.

Grammaire formelle[modifier | modifier le code]

Un L-système est une grammaire formelle qui comprend :

  1. Un alphabet V : l'ensemble des variables du L-système. V^* est l'ensemble des « mots » que l'on peut construire avec les symboles de V, et V^+ l'ensemble des mots contenant au moins un symbole.
  2. Un ensemble de valeur constantes S. Certains de ces symboles sont communs à tous les L-système (voir plus bas la Turtle interpretation).
  3. Un axiome de départ \omega choisi parmi V^+, c'est-à-dire l'état initial.
  4. Un ensemble de règles, noté P, de reproduction des symboles de V.

Un L-système est noté \{V, S, \omega, P\}.

Exemples et notations de L-systèmes simples[modifier | modifier le code]

Arbre fractal

Exemple 1 : l'algue de Lindenmayer[modifier | modifier le code]

Voici le premier L-système 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-système. 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[modifier | modifier le code]

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

Notation :

Fibonacci
{
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

Interprétation en tortue[modifier | modifier le code]

La chaîne de caractères obtenue a une interprétation graphique, en deux ou trois dimensions. En deux dimensions, on imagine qu'une main tient un crayon qui se déplace sur la feuille selon des instructions  : "monte d’un cran, puis tourne de 20° à gauche, déplace-toi deux fois de un cran, mémorise ta position et avance encore d’un cran, lève-toi puis repose-toi sur la position mémorisée" et ainsi de suite... On introduit donc des symboles variants ∈ V, ou constants ∈ S, pour permettre de guider la main. Plusieurs d'entre eux ont été normalisés, ils font partie de ce qu'on appelle la "Turtle interpretation". Ce nom vient de la "tortue" du langage de programmation Logo qui fonctionne sur le même principe. En fait, c'est cette tortue qui est la main qui tient le crayon. Les signes couramment utilisés sont les suivants  :

  • F : Se déplacer d’un pas unitaire (∈ V)
  • + : Tourner à gauche d’angle α (∈ S)
  • - : Tourner à droite d’un angle α (∈ S)
  • & : Pivoter vers le bas d’un angle α (∈ S)
  • ^ : Pivoter vers le haut d’un angle α (∈ S)
  • < : Roulez vers la gauche d’un angle α (∈ S)
  • > : Roulez vers la droite d’un angle α (∈ S)
  • | : Tourner sur soi-même de 180 ° (∈ S)
  • [ : Sauvegarder la position courante (∈ S)
  • ] : Restaurer la dernière position sauvée (∈ S)

Pour être plus concret, les symboles appartenant à V sont des parties d'une plante, comme une branche ou une portion de branche tout simplement. Les symboles appartenant à S sont des ordres que l'on donne à notre main virtuelle qui dessine la plante, ils servent à déterminer une direction à prendre, tandis que les symboles de V dessinent dans cette direction.

Remarque  : les deux derniers symboles rappellent les fonctions pushMatrix() et popMatrix() d'OpenGl, ainsi on devine que c'est un environnement graphique qui se prêtera très bien au L-système. De plus la programmation orientée objet avec les pointeurs, tel que dans le langage C++, semble indiquée pour la modélisation d'une "chaîne cellulaire" qui évolue.

Exemple de la courbe de Koch[modifier | modifier le code]

  • Variable : v = {F}
  • Constantes : S = {+, −}
  • Axiome : w = F
  • Règle : (F → F+F−F−F+F)

Courbe_de_Koch
{
angle 90
axiom F
F=F+F−F−F+F
}

angle 90 détermine que l'on tourne de 90 ° avec les symboles + et -.

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

  • n=0: Koch Square - 0 iterations

F

  • n=1: Koch Square - 1 iterations

F+F-F-F+F

  • n=2: Koch Square - 2 iterations

F+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: Koch Square - 3 iterations

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F +

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F - F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F - F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F +

F+F-F-F+F+F+F-F-F+F-F+F-F-F+F-F+F-F-F+F+F+F-F-F+F

Tortue en trois dimensions[modifier | modifier le code]

Cette « turtle interpretation » peut être exploitée en trois dimensions grâce aux idées de Harold Abeson et Andrea diSessa dans leur ouvrage commun, « Turtle geometry : the computer as a medium for exploring mathematic ». L'orientation est représentée par trois vecteurs :
\vec H, \vec L, \vec U tels que \vec H \times \vec L = \vec U

  • \vec H pour turtle heading. Il s'agit du regard de la tortue.
  • \vec U pour up. Il s'agit de la direction vers laquelle se dirige la tortue.
  • \vec L pour left. Il s'agit de la gauche de cette tortue.

La rotation de la tortue se note alors :
 [ \vec H' \vec l'\vec U' ] = [\vec H \vec L \vec U]RR est une matrice 3×3. Les rotations d'un angle α autour des axes \vec U, \vec L ou \vec H sont représentées par les matrices :

RU(\alpha) = 
\begin{pmatrix}
\cos(\alpha) & \sin(\alpha) & 0 \\
-\sin(\alpha) & \cos(\alpha) & 0 \\
0 & 0 & 1
\end{pmatrix}


RL(\alpha) = \begin{pmatrix} 
\cos(\alpha) & 0 & -\sin(\alpha) \\
0 & 1 & 0 \\
\sin(\alpha) & 0 & \cos(\alpha)
\end{pmatrix}


RH(\alpha) =\begin{pmatrix}
1 & 0 & 0 \\
0 & \cos(\alpha) & -\sin(\alpha) \\
0 & \sin(\alpha) & \cos(\alpha)
\end{pmatrix}

Les symboles prennent maintenant la signification suivante :

  • + Tourner à gauche d'un angle α, en utilisant la matrice de rotation RU(α).
  • − Tourner à droite d'un angle α, en utilisant la matrice de rotation RU(−α).
  • & Pivoter vers le bas d'un angle α, en utilisant la matrice de rotation RL(α).
  • ∧ Pivoter vers le haut d'un angle α, en utilisant la matrice de rotation RL(−α).
  • \ Rouler à droite d'un angle α, en utilisant la matrice de rotation RH(α).
  • / Rouler à gauche d'un angle α, en utilisant la matrice de rotation RH(−α).
  • | Tourner autour de lui-même de 180 °, en utilisant la matrice de rotation RU(180◦).

DOL-système ou Deterministic 0-context System[modifier | modifier le code]

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-système, il s'agit de la forme la plus simple de L-système.

Exemple de DOL-système[modifier | modifier le code]

  • 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

S0L-système ou Stochastic 0-context System[modifier | modifier le code]

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-système, 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-système[modifier | modifier le code]

On pourrait étoffer l'exemple du DOL-système, 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.

Context-Sensitive[modifier | modifier le code]

Les deux systèmes précédents (des OL-systèmes) ne peuvent pas simuler l'interaction de parties d'une plante car ils sont context-free, i.e. chaque partie se développe indépendamment des autres parties. Un L-système context-sensitive résout ce problème en prenant en compte ce qui précède ou succède à une partie, c’est-à-dire un symbole. Un tel système est appelé IL-système ou encore (k, l)-système, le contexte de gauche est un "mot" de longueur k et celui de droite un "mot" de longueur l. Pour expliquer la manière dont se lisent les regles voici deux exemples :

Exemple 1 : signal acropète[modifier | modifier le code]

Ce L-système simule la propagation d'un signal acropète dans une structure de branches qui ne se développe pas.

  • Variable : V = {A, B}
  • Constantes : S = {+, −, [, ], <}
  • Axiome : w = B[+A]A[−A]A[+A]A
  • Règles : (B < A → B)

A est une branche qui n'a pas encore reçu le signal, et B en est une qui l'a reçu. La règle se comprend ainsi : si un symbole A est précédé d'un symbole B, alors ce A devient un B à la génération suivante.

Voici la propagation du signal sur trois générations, sachant que les signes + et - seront ignorés dans la prise en compte des règles :

  • n=0, B[+A]A[−A]A[+A]A
  • n=1, B[+B]B[−A]A[+A]A
  • n=2, B[+B]B[−B]B[+A]A
  • n=3, B[+B]B[−B]B[+B]B

On constate que peu à peu, chaque branche est atteinte par le signal acropète qui permet aux fleurs les plus hautes de s'ouvrir. Remarquez bien qu'à chaque génération, deux nouvelles branches reçoivent le signal, en effet, puisque l'on sauvegarde la position, que l'on dessine A puis qu'on restitue la position et que l'on redessine un A, cela signifie que ces deux A ont la même base, donc la même branche précède les deux.

Exemple 2 : signal basipète[modifier | modifier le code]

Ce L-système simule la propagation d'un signal basipète dans une structure de branches qui ne se développe pas.

  • Variable : V = {A, B}
  • Constantes : S = {+, −, [, ], <}
  • Axiome : w = A[+A]A[−A]A[+A]B
  • Règles : (A > B → B)

A est une branche qui n'a pas encore reçu le signal, et B en est une qui l'a reçu. La règle se comprend ainsi : si un symbole A est suivi d'un symbole B, alors ce A devient un B à la génération suivante.

Voici la propagation du signal sur trois générations, sachant que les signes + et - seront ignorés dans la prise en compte des règles :

  • n=0, A[+A]A[−A]A[+A]B
  • n=1, A[+A]A[−A]B[+B]B
  • n=2, A[+A]B[−B]B[+B]B
  • n=3, B[+B]B[−B]B[+B]B

On constate que peu à peu, chaque branche est atteinte par le signal basipète qui permet aux fleurs à l'inflorescence en ombrelle ou en capitule de fleurir de manière centrifuge.

Remarque : il est bien sûr possible d'écrire une règle dans le genre (B < A < B → B), ce qui signifie que si une branche A est entourée par des branches B alors elle deviendra une branche B à la prochaine génération. Il est aussi possible d'écrire plusieurs règles, pour plusieurs situations.

Bibliographie[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]