Le jardinier numérique (1/4): systèmes de Lindenmayer
Suite à ma lecture de The Algorithmic Beauty of Plants de Przemysław Prusinkiewicz et Aristid Lindenmayer, j'ai voulu essayer de reproduire les plantes des premiers chapitres, mais aussi en créer de nouvelles.
Systèmes de Lindenmayer
Un système de Lindenmayer ou L-système est une grammaire formelle inventée par Aristid Lindenmayer en 1968 pour décrire le processus de croissance des végétaux. Pour cela, l'idée est de remplacer successivement des parties d'un objet initial simple en utilisant un jeu de règles de réécriture (ou productions). Un exemple courant d'objet graphique défini à l'aide de règles de réécriture est le flocon de neige de Koch. Pour commencer à le dessiner, on choisit deux formes: un initiateur et un générateur (voir ci-dessous). À chaque étape de la construction, on remplace les segments non brisés (de l'initiateur puis des formes obtenues) par un exemplaire du générateur que l'on réduit et que l'on réarrange de façon à ce qu'il ait les mêmes points de départ et d'arrivée que le segment remplacé.
Générateur
Initiateur
Itération 1
Itération 2
Itération 3
Le concept clé d'un L-système est la réécriture. La réécriture est une technique qui permet de définir des objets complexes en remplaçant successivement des parties d'un objet initial simple. Les systèmes de réécriture les plus étudiés sont ceux qui agissent sur des chaînes de caractère. Bien que la première définition formelle d'un tel système ait été donnée au début du 20e siècle, ce n'est qu'à la fin des années 50 que les travaux de Chomsky sur les grammaires formelles suscitent un regain d'intérêt pour ces systèmes.
La différence principale entre les grammaires de Chomsky et les L-systèmes réside dans la méthode d'appliquer les productions (ou règles de réécriture). Dans les grammaires de Chomsky, elles sont appliquées séquentiellement, alors que dans les L-systèmes elles sont appliquées en parallèle et simultanément pour toutes les lettres d'un mot. Cette simultanéité donne un caractère biologique au L-système et lui permet d'imiter les divisions cellulaires qui peuvent s'opérer au même moment dans les organismes multicellulaires.