Copyright David G. Green 1993. This preprint may be copied an used provided that this notice and the authorship remains attached.

L-SYSTEMES et ARBRES

Introduction

De nombreux organismes croissent suivant un mode fractal, comme par exemple les voies pumonaires ou les branches d'un arbre. L'auto-similarité à différentes échelles nait de la répétition d'un meme processus (p.e. la bifurcation).Ces exemples de processus répétés peuvent etre souvent définis de façon concise par des règles de réécriture. Les systèmes L sont des ensembles de règles et de symboles(autrement dit des "grammaires formelles") qui modèlisent des phénomènes de croissance. Le L est mis en hommage à Aristid Lindenmayer qui fut le premier à utiliser des méthodes syntaxiques en modélisation de croissance.

Un système L simple contient 4 types d'éléments" :

des VARIABLES qui sont des symboles dénotant les éléménts à remplacer.
des CONSTANTES qui sont des symboles dénotant des éléments fixes.
p.e. L'expression
est constiuée de variables grammaticales. Chaque variable peut etre remplacée par une constante (mots ou phrases) pour produire une phrase, comme "Le chat mange la souris" or "Le système est stable".
des REGLESS ("la syntaxe") qui définissent comment les variables doivent etre remplacées par des constantes ou d'autres variables. p.e. dans l'exemple précédent serait une des règles.
un DEPART ou mot de départ qui définit le démarrage du système. p.e. dans l'exemple précédent, le point de départ pourrait etre la seule variable

Exemple - les nombres de Fibonacci

Considérons la grammaire (simple), définie par

     variables  :   A  B
     constantes :   (aucune)
     règles     :   A -> B
                    B -> AB
     départ     :   A

Ce système L produit les chaines suivantes :

Stade 0 : A Stade 1 : B Stade 2 : AB Stade 3 : BAB Stade 4 : ABBAB Stade 5 : BABABBAB Stade 6 : ABBABBABABBAB Stade 7 : BABABBABABBABBABABBAB

Si on compte la longueur de chaque chaine, on obtient les nombres de Fibonacci :

     1  1  2  3  5  8  13  21  34 ....

Applications

The power of L-systems comes when we assign meaning to the symbols and rules. For instance the symbols might represent branches of a growing tree and the rules denote the

Example - Algal growth

The power of L-systems comes when we assign meaning to the symbols and rules. The figure shows the pattern of cell lineages found in the alga Chaetomorpha linum. To describe this pattern, we must let the symbols denote cells in different states, rather than different structures. This growth process can be generated from an axiom A and growth rules

     A -> DB
     B -> C
     C -> D
     D -> E
     E -> A

Here is the pattern generated by this model. It matches the arrangement of cells in the original alga.

     Stage  0 :                      A
     Stage  1 :             D                B
     Stage  2 :             E                C
     Stage  3 :             A                D
     Stage  4 :         D        B           E
     Stage  5 :         E        C           A
     Stage  6 :         A        D       D       B
     Stage  7 :      D     B     E       E       C
     Stage  8 :      E     C     A       A       D
     Stage  9 :      A     D   D   B   D   B     E
     Stage 10 :    D   B   E   E   C   E   C     A
     Stage 11 :    E   C   A   A   D   A   D   D   B

Turtle graphics

To use L-systems for generating graphical images requires that the symbols in the model refer to elements of a drawing on the computer screen. For example, the program FRACTINT uses "Turtle Graphics" to produce screen images. It interprets each constant in an L-system model as a turtle command.

Turtle geometry, invented by Seymour Papert, deals with patterns produced by the path of an imaginary turtle moving around on a plane. The path of a turtle can be described by a sequence of symbols representing the moves that the turtle makes as it moves around. These sequences form words in a formal language, defined by a grammar such as the following:

     Constants    = {nF, nB, aR, aL, Stop },
     Variables    = {, , , ...},
     Start        =

where

     nF  denotes  "n steps Forward"
     nB  denotes  "n steps Back"
     aR  denotes  "Turn a degrees Right"
     aL  denotes  "Turn a degrees Left"

and the basic production rules are:

<Path> -> nF <Path> <Path> -> nF aR <Path> <Path> -> nF nB <Path> <Path> -> nF aL <Path> <Path> -> nF STOP

In this grammar, the variable Path denotes the (as yet) unspecified part of the turtle's trail. The transitions represent moves made by the turtle. At any time, the completed portion of the turtle's path is specified by a sequence of individual movements, such as

     "4F  90R  F  90R  F  90R  "

Turtle geometry is frequently used in computer graphics. Models that form complex patterns are obtained by augmenting the above grammar with new variables to denote particular pattern elements, and with new rules governing the structure of those patterns elements, hence the list of variables in the above definition is left open ended. For example, the following rules use the variables Design, Arm, etc to describe the formation of the simple design shown in the Figure (a). Part (b) of the figure shows a random walk.

<Path> -> <Design> stop <Design> -> 4 <Arm> <Arm> -> 4F 3<Corner> 1F <Corner> -> 2F 3<Turn> <Turn> -> 90R F

Example - a compound leaf (or branch)

Below is a model (as used by FRACTINT) to draw a leaf (Fig. 3). A semi-colon indicates that the rest of a line is a comment.

     Leaf1 {          ; Name of the l-system, "{" indicates start
                      ; Compound leaf with alternating branches,
       angle 8        ; Set angle increment to (360/8)=45 degrees
       axiom x        ; Starting character string
       a=n            ; Change every "a" into an "n"
       n=o            ; Likewise change "n" to "o" etc ...
       o=p
       p=x
       b=e
       e=h
       h=j
       j=y
       x=F[+A(4)]Fy   ; Change every "x" into  "F[+A(4)]Fy"
       y=F[-B(4)]Fx   ; Change every "y" into  "F[-B(4)]Fx"
       F=@1.18F@i1.18
       }              ; final } indicates end