L-Système

En informatique théorique, un L-système ou système de Lindenmayer est un système de réécriture ou grammaire formelle, inventé en 1968 par le biologiste hongrois Aristid Lindenmayer. Un L-système modélise le processus de développement et de prolifération de plantes ou de bactéries.

C'est une forme de grammaire générative. Ces grammaires ont été mises en œuvre graphiquement par de nombreux auteurs, menant à de spectaculaires images. Une étude systématique d'une certaine formulation a été entreprise par Przemysław Prusinkiewicz (en) dans les années 1980. Une étude mathématique, débutée dès l'introduction des systèmes par Lindenmayer, a débouché sur une théorie élaborée dont une première synthèse a été faite, en 1980 déjà, par Rozenberg et Salomaa^[1].

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.

Formellement, 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.

Système de réécriture

Un L-système est un système de réécriture qui comprend :

Un alphabet $V$ : l'ensemble des variables du L-système. On note $V^{*}$ 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 ;
Un ensemble de valeur constantes $S$ . Certains de ces symboles sont communs à tous les L-systèmes (voir plus bas la Turtle interpretation) ;
Un axiome de départ $w$ de $V^{+}$ , vu comme l'état initial ;
Un ensemble de règles réécriture, noté $P$ , de reproduction des symboles de $V$ .

Un L-système est noté $\{V,S,w,P\}$ . La différence avec une grammaire formelle est dans l'application des règles : dans un L-système, à chaque étape toutes les variables sont substituées, alors que dans une grammaire, une seule variable est remplacée.

Exemple et notations de L-systèmes simples

Voici « l'algue de Lindenmayer », un 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 abrégée : Algue { Axiom A ; A=AB, B=A}

Une équation comme 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

Si on compte le nombre de symboles à chaque itération, on obtient la suite de Fibonacci, aux deux premiers termes près.

Interprétation en tortue

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 en anglais 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

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:

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

Tortue en trois dimensions

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 ». Trois vecteurs liés à la tortue permettent de spécifier son prochain changement d'orientation :

${\vec {H}}$ , ${\vec {L}}$ , ${\vec {U}}$ tels que ${\vec {H}}\times {\vec {L}}={\vec {U}}$ (produit vectoriel)

${\vec {H}}$ pour turtle heading. Il s'agit du regard de la tortue.
${\vec {U}}$ pour up. Le « haut » de la tortue. C'est la direction qui sort de la tortue par son dos (i.e. par le côté bombé de sa carapace).
${\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}}]R$ où R est une matrice 3×3.

Les rotations d'un angle α autour des axes ${\vec {U}}$ , ${\vec {L}}$ ou ${\vec {H}}$ sont respectivement 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 α, autour de l'axe ${\vec {U}}$ , i.e. en utilisant la matrice de rotation RU(α) ;
− : tourner à droite d'un angle α, autour de l'axe ${\vec {U}}$ , i.e. en utilisant la matrice de rotation RU(−α) ;
& : pivoter vers le bas d'un angle α, autour de l'axe ${\vec {L}}$ , i.e. en utilisant la matrice de rotation RL(α) ;
∧ : pivoter vers le haut d'un angle α, autour de l'axe ${\vec {L}}$ , i.e. en utilisant la matrice de rotation RL(−α) ;
/ : basculer à droite d'un angle α, autour de l'axe ${\vec {H}}$ , i.e. en utilisant la matrice de rotation RH(α) ;
\ : basculer à gauche d'un angle α, autour de l'axe ${\vec {H}}$ , i.e. en utilisant la matrice de rotation RH(−α) ;
| : tourner autour d'elle-même de 180°, i.e. faire demi-tour, en utilisant la matrice de rotation RU(180◦).

D0L-système ou Deterministic 0-context System

Les abréviations « D » pour « déterministe » et « 0 » pour « indépendant du contexte » servent à désigner une catégorie particulière de -système. Un système est déterministe lorsqu'il n'offre qu'une seule évolution possible depuis l'axiome à chaque 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. De plus, cette évolution est indépendante du contexte. L'exemple initial est un D0L-système, il s'agit de la forme la plus simple de L-système.

Exemple d'un D0L-système

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

Notation symbolique : 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

Un tel système fait appel aux probabilités. Contrairement au D0L-système, un choix peut être opéré entre plusieurs transformations pour un symbole. Chaque choix est pondéré par une certaine probabilité.

Exemple de S0L-système

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

Les règles X → F[++X]F[−X]+X et X → F[+X]F[−X]+X sont appliquées avec une probabilité 0,2 et 0,8 respectivement.

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, avec des probabilités différentes.

Systèmes sensible au contexte

Les deux systèmes précédents (des 0L-systèmes) ne peuvent simuler l'effet de l'interaction de parties d'une plante car ils sont non contextuels (en anglais : context-free), i.e. chaque partie se développe indépendamment des autres parties. Un L-système sensible au contexte (« context-sensitive » en anglais) prend en compte ce qui précède ou succède au symbole à remplacer. Un tel système est aussi appelé IL-système ou encore (k, l)-système, lorsque le contexte de gauche est un mot de longueur k et celui de droite un mot de longueur l. Lorsque le contexte est favorable, la substitution se fait selon la règle, dans le cas contraire il n'y a pas de substitution. Voici deux exemples :

Exemple 1 : signal acropète

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)

Le symbole < de la règle s'interprète comme suit : si un symbole A est précédé d'un symbole B, alors ce A devient un B à la génération suivante, sinon il reste inchangé. Dans cette évaluation, les constantes sont ignorées.

Voici la propagation du signal sur trois générations; les signes + et - sont 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 chaque branche est progressivement atteinte par le signal acropète qui permet aux fleurs les plus hautes de s'ouvrir. À 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

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 chaque branche est progressivement atteinte par le signal basipète qui permet aux fleurs à l'inflorescence en ombrelle ou en capitule de fleurir de manière centrifuge.

L'écriture éventuelle d'une règle de la forme (B < A < B → B) 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.

Sur les autres projets Wikimedia :

L-Système, sur Wikimedia Commons

Annexes

Notes et références

↑ Rozenberg et Salomaa 1980.

Bibliographie

Livres

Grzegorz Rozenberg et Arto Salomaa, The Mathematical Theory of L-Systems, Academic Press, 1980
(en) « The Algorithmic beauty of plants » de Przemyslaw Prusinkiewicz et Aristid Lindenmayer, 1990
Grzegorz Rozenberg et Arto Salomaa, The Book of L, Springer-Verlag, 2012 (réimpression de la première édition de 1986), 492 p. (ISBN 978-3-642-95488-7)
(en) Przemyslaw Prusinkiewicz et James Hanan, Lindenmayer Systems, Fractals, and Plants, 1992

Articles

Karel Klouda et Štěpán Starosta, « Characterization of circular D0L-systems », Theoretical Computer Science, vol. 790,‎ 2019, p. 131–137 (DOI 10.1016/j.tcs.2019.04.021).

Galerie et logiciels

Charlie Chernohorsky, Galerie de fractales, 2004.
(en) Interprétation graphique et musicale des L-systems. (Application Java)
LOGO et les L-systèmes

Liens externes

(en) Publications du Biological Modeling and Visualization research group
(en) Department Ecoinformatics, Biometrics and Forest Growth at the Georg-August University of Göttingen Growth grammars

Voir aussi

[1] Rozenberg et Salomaa 1980.

[1]

v · m Fractales
Caractéristiques	Dimensions fractales Assouad Minkowski-Bouligand Hausdorff Récursivité Autosimilarité
Système de fonctions itérées	Fougère de Barnsley Ensemble de Cantor Flocon de Koch Éponge de Menger Arbre de Pythagore Tapis de Sierpiński Triangle de Sierpiński Fractale de Vicsek Courbes Blanc-manger Cesàro De Rahm Dragon Dragon d'or Gosper Hilbert Koch Lebesgue Lévy Courbe remplissante courbe de Peano remplissant le flocon de Koch Sierpiński
Attracteur étrange	Multifractale
L-Système	Canopée fractale Courbe remplissante Arbre en H
Création	Burning ship Julia Dendrite Lapin de Douady Liapounov Mandelbrot Multibrot Newton Tricorne (en) Mandelbox Mandelbulb
Techniques de rendu photoréaliste	Buddhabrot Piège orbital (en) Trognon de Pickover (en)
Fractales aléatoires	Mouvement brownien Terrain fractal Théorie de la percolation Chemin auto-évitant
Personnalités	Georg Cantor Felix Hausdorff Gaston Julia Helge von Koch Paul Lévy Alexandre Liapounov Benoît Mandelbrot Lewis Fry Richardson Wacław Sierpiński
Liste de fractales par dimension de Hausdorff Art fractal La Théorie du chaos (livre)