Page principale

L-Systèmes, génération de fractales, et courbe de Hilbert

L-Systèmes : définition et exemples

Les L-Systèmes sont des cas très particuliers de systèmes de réécriture, initialement introduits par le biologiste Aristid Lindenmayer, dans le but modéliser le développement d'organismes biologiques. Nous allons les définir et donner des exemples après quelques définitions préliminaires.
On appelle alphabet un ensemble fini, dont les éléments sont appelés lettres.
Par exemple, V={A,B,C}, est un alphabet.
On appelle mot sur un alphabet V une séquence (éventuellement vide) de lettres de V.
Par exemple, ABABC est un mot (de longueur 5) sur l'alphabet défini ci-dessus.
Un L-Sytème (déterministe) est la donnée:
Un tel L-Système engendre récursivement une suite de mots (m0,m1,m2,...) définie de la façon suivante:

Quelques exemples

Un L-Système très simple pour se chauffer

On vérifie facilement que ce L-Système engendre la suite de mots suivante:
(A, AB, ABB, ABBB, ABBBB, ...)

L'algue de Lindenmayer

Il s'agit du L-Système défini par S'il n'y avait que la première règle de réécriture, on serait dans le cas précédent - que l'on peut interpréter comme la croissance d'une structure biologique linéaire ABB....B.
La deuxième règle indique que les B sont alors des points de départ de nouvelles structures linéaires, qui vont elle-même brancher, etc. Voir ci-dessous pour une interprétation graphique.

Le début de la suite engendrée est
(A, AB, ABA, ABAAB, ABAABABA, ...)
Il s'agit en fait (à renommage près des lettres) du début de la suite de mots de Fibonacci, très étudiée dans la théorie des langages formels.

Construction de fractales

Les L-Systèmes permettent de construire assez facilement des fractalesNotion délicate à définir de façon générale ! On parle de fractale pour une structure ayant une certaine invariance par changement d'échelle. - c'est d'ailleurs leur intérêt de départ, certaines structures biologiques se modélisant bien de cette façon (on pense immédiatement - en 3D - au Chou romanesco).
L'idée est de faire intervenir dans l'un et/ou l'autre des alphabets des symboles particuliers ayant une interprétation graphique (de type tortue graphique): on imagine un traceur dans le plan, qui va se déplacer tout en laissant une trace. On se donne ici les symboles suivants:

Le formulaire ci-dessous permet tester tout cela pour des L-systèmes (avec au plus 4 variables en plus de F et G). Cliquer sur les boutons pour obtenir des L-systèmes correspondant à quelques fractales classiques.



   


Mot:

Courbe de Hilbert

La courbe de Hilbert a été inventée par Hilbert en 1891. Il s'agit d'une courbe mathématiquement importante, puisqu'elle correspond à une application continue et surjective de [0,1] dans [0,1]2 - en d'autres termes, il s'agit d'une courbe qui remplit entièrement le carré [0,1]2.
Elle est construite comme courbe limite d'une famille de courbes, qui peuvent être construites via le L-Système suivant: où les symboles F, + et - sont interprétés comme expliqué ci-dessus, et L et R sont omis dans les tracés. L'angle choisi pour les rotation est π/2.

Voici les premiers mots engendrés par ce L-Système, ainsi que les courbes correspondantes.
Et les courbes obtenues jusqu'au 8ème mot de la séquence.

Pour finir, et pour le plaisir des yeux, sur une idée puisée dans Jeux finis et infinis de Jean-Paul Delahaye, un exemple d'image dont les pixels se déplacent en suivant une courbe de Hilbert (la dernière représentée ci-dessus). Le pixel «sortant» est renvoyé au début de la courbe.
Un parcours complet, et donc un retour à l'image d'origine se produit toutes les 16384 itérations, c'est-à-dire toutes les demi-heures environ selon la puissance de votre machine.