LES L-SYSTÈMES
Généralités sur les langages
Définition d´un langage
On appelle alphabet un ensemble A fini et non vide
d´éléments.
Exemple: A = {a, b, c, d}.
On appelle symbole les éléments de A. Exemple: a est un symbole.
On appelle mot sur l´alphabet A toute suite finie de
symboles. Exemple: bcca est un mot.
On appelle longueur d´un mot le nombre de ses éléments.
Exemple: |bcca| = 4.
L´ensemble de tous les mots construits sur A est un ensemble infini,
note A*.
On appelle langage d´alphabet A un sous ensemble L
de mots.
Exemple: L = {a, ab, bdc, ccd}.
On appelle expression un élément de L. Exemple: bdc.
Il se pose deux problèmes à propos des langages:
1) Comment générer un langage.
Dans le cas ou L est fini, on peut définir le langage en donnant
simplement la liste L de ses expressions.
Mais, dans le cas général, L est infini, et une
définition procédurale
est préférée:
2) Comment reconnaitre si un mot est une expression, c´est
à dire si une combinaison de symboles appartient à L. Le problème
ne se pose véritablement que si L est infini (problème des compilateurs).
Langage arborescent
Dans un langage arborescent, ou à pile, les
expressions sont représentées par des arbres. Par exemple
soient:
A = {x, y, z, ++, +, *, (, )} un alphabet définissant des
expressions arithmétiques:
(x, y, z) sont les variables ou symboles
d´arité 0 ou 0-aires
++ est l´opérateur d´incrémentation applicable à une
variable: x -> x+1, qui est dit d´arité 1 ou 1-aire
+ et * sont des opérateurs d´arité 2 ou 2-aires
ou encore binaires, applicables à deux
variables: x + y et x * y
( et ) sont les parenthèses permettant de préciser
l´ordre d´application des opérateurs, ainsi:
(x * y) + z et x *( y + z) sont des expressions différentes.
Il y a plusieurs façons de noter une expression:
Notation parenthésée, exemple: x * (y + z)
Notation polonaise préfixée, exemple: * x + y z
On peut mettre des parenthèses pour en faciliter la lecture:
(* x (+ y z))
Remarque:
Un opératuer d´arité 3, ou ternaire ne peut pas se noter
avec des parenthèses, mais s´écrit sans difficultés en polonaise préfixée.
Par exemple ´if then else´ est un opérateur qui a pour argument une
condition COND et deux espressions EXP1 et EXP2:
if(COND) then {EXP!} else {EXP2} peut se noter, en langage C:
(COND) ? EXP1 : EXP2.
Si on le note ITE, il s´écrit, en polonaise préfixée:
ITE COND EPX1 EXP2
Une expression notée en polonaise préfixée peut se représenter
par un arbre dont chaque noeud est un opérateur n-aire, il part
alors n branches de ce noeud. Ainsi les variables (0-aires) sont
des symboles terminaux, ou feuilles de l´arbre, les
opérateurs unaires, comme ++, ont une branche, les opérateurs binaires
en ont deux, etc...
Exemples:
Figure LS-1: Expressions parenthésées, polonaises préfixées
et arborescences.
L´évaluation d´une expression se fait en utilisant une pile
(d´ou le nom de ces langages) comme le montre l´exemple suivant:
Figure LS-2: Évaluation d´une expression avec une pile
Une opération syntaxique, associe à un symbole n-aire sn,
s´applique à un mot de longueur n:
sn a1 a2 ... an
Exemple:
Opérateur 0-aire: x
Opérateur unaire: ++x
Opérateur binaire: + (++ x) (* y z)
Grammaire
On appelle production, ou encore règle de réécriture,
toute écriture de la forme:
u -> v ou u et v sont des expressions.
Une grammaire (non contexuelle) est une liste de productions,
elle engendre un langage par application récursive de ces règles
aux symboles.
Exemples du langage sur les expressions arithmetiques:
Liste des productions:
L -> L
L -> ++ L
L -> + L L
L -> * L L
L -> (L)
Exemples d´expressions engendrees:
x -> ++x -> (++ x)
++x -> (+ (++ x) y)
(+ (++ x) y) -> (* (+ (++ x) y) z)
L-systèmes
Définition
Lindenmayer [LINDENMAYER 68] introduisit la notion de grammaires
à règles de réécritures parallèles pour modèliser et développer
des systèmes biologiques: Ce sont des grammaires semblables à celles
utilisées pour définir les langages formels (voir LS-1),
mais les productions
y sont appliquées simultanément et il n´y a pas de différence
entre symboles terminaux et non terminaux. Plus précisement, soient:
V = {A1, A2, ..., An}
un vocabulaire fini de symboles.
Un ensemble de règles de réécritures qui transforment des
chaînes de symboles en d´autres.
Un axiome ou chaîne initiale.
Toute chaîne déduite par application récursive des règles de
réécriture à l´axiome sont des mots du langage.
Exemple:
V = {A, B, C, D} est le vocabulaire.
A -> CB est la première règle
B -> A est la deuxième règle
C -> DA est la troisième règle
D -> C est la quatrième règle
et A est l´axiome
Par application de la première règle:
A -> CB
Par application des règles 3 (a C) et 2 (a B):
CB -> DAA
Par application des règles 4 (a D) et 1 (a A et A):
DAA -> CCBCB qui est donc un mot du langage, etc...
Voir programmation d´un L-système dans la rubrique
"programmation"
(lsys.c)
(lsys0.c)
L-systèmes parenthésé
Lindenmayer a aussi utilisé la notion de langage complètement
parenthésé obtenu en ajoutant au vocabulaire des symboles
de branchement permettant une représentation arborescente
des mots du langage.
Par exemple, soit V* = V U {(, ),[ ,]} le nouvel
alphabet et soient les productions:
1) A -> C[B]D
2) B -> A
3) C -> C
4) D -> C(E)A
5) E -> D
On obtient des mots:
A -> C[B]D -> C[A]C(E)A (regles 1, 2 et 4)
-> C[C[B]D]C(D)C[B]D (regles 1, 5 et 1)
Interprétation graphique
Si l´on définit les parenthèses comme un branchement à gauche
et les crochets comme un branchement à droite, on a la
représentation arborescente suivante:
Figure LS-3: Interprétation graphique d´une expression
En utilisant une "tortue" (proche de celle du langage LOGO),
dont les déplacements sont commandés par les symboles d´une
expression, on peut associer un dessin à cette expression. Par exemple:
A = {a, +, -} l´alphabet dans lequel ´a´ signifie ´avancer´,
´+´ signifie ´tourner de 60o´ et ´-´ signifie
´tourner de -60o´
A -> A-A++A-A est la regle de production
et A est l´axiome
Le développement du langage construit une courbe de Von Koch
(Voir aussi FR-3):
Figure LS-4: Courbe de Van Koch
Le développement des L-systemes produit des courbes dont
la croissance et la forme rappellent celles des plantes. Du
fait du déterminisme de la méthode, tous les motifs correspondant
à une même expression sont identiques. Mais, dans la nature,
deux plantes d´une même espèce ne sont jamais exactement identiques.
Pour simuler cette variete on introduit de l´aléatoire dans
l´interprétation graphique des règles. On peut aussi réaliser
une application stochastique des règles en leur associant par
exemple une probabilité d´application.
Voici l´exemple d´une fougère obtenue par un tel procédé (d´apres
[HEUDIN 1994]):
En 1984 Smith [Smith 1984] s´intéressa à des algorithmes de
générations de plantes utilisant les langages formels et la notion
d´objet fractal.
Figure LS-5: Fougere
L-systèmes ouverts
Interaction d´une plante avec son environnement
Les L-systèmes présentés ci-dessus sont construits a partir de
règles de production qui, une fois définies, fonctionnent de façon
autonome or, dans la réalité, la croissance d´une plante tient
compte de son environnement:
Influence des variations de la lumière et de la température.
Obstacles modifiant la croissance, nature du sol.
Influence des plantes sur l´écosystème dont elles font partie:
Compétition pour la place et l´accès à la lumière.
La simulation des plantes passe donc par la simulation de leur environnement
[MECH 1996]. Une plante réagit à un stimulus en affectant l´environnement
ce qui, par feedback, modifie la plante. Par exemple la croissance
des racines dans le sol peut absorber ou extraire de l´eau modofiant
ainsi la circulation de celle-ci, ce qui influera sur la
croissance de la plante. L´interaction d´une plante avec son
environnement peut se décrire comme suit:
1) Réception d´un stimulus.
2) Transport et traitement de l´information dans la plante.
3) Génération d´une réponse sous la forme de changements dans
la croissance (comme le développement de nouvelles branches) envoyant
des informations à l´environnement.
4) Perception, par celui-ci, de l´action de la plante.
5) Simulation du traitement de cette information (diffusion de
substances ou propagation de lumière).
6) Retour en 1).
L-systèmes ouverts
À l´origine les L-systèmes sont des systèmes cybernetiques fermés
sans moyen d´interagir. Rozenberg [ROZENBERG 1973] définit les
table L-systems pouvant modifier l´ensemble de ses
règles de production en réponses à des stimulus externes. Plus
tard les L-systemès paramétriques [HANAN 1992] [PRUSINKIEWICZ 1990]
et les L-systèmes sensibles à l´environnement [PRUSINKIEWIZC 1994]
permirent d´introduire des symboles spéciaux retournant la position
et l´orientation de la "tortue"; ces paramètres sont ensuite passés
à une fonction définie par l´utilisateur retournant des propriétés
locales de l´environnement à cet endroit.
Les L-systèmes ouverts [MECH 1996] utilisent un symbole
spécial pour gérer l´interaction avec l´environnement, les paramètres
associés à ce symbole peuvent être modifiés par l´environnement
et passés à la plante, ou modifiés par la plante et passés à
l´environnement. Celui-ci n´est plus modelisé par une simple fonction
mais devient un processus tournant en parallèle avec le L-système.
Définissons une règle de production par:
id: cg | pred | cd : cond -> succ : prob avec:
id est une étiquette (nom de la règle)
cg désigne le "contexte de gauche"
pred désigne le "prédécesseur"
cd désigne le "contexte de droite"
cond est une condition d´exécution de la règle
prob est la probabilité d´exécution
Exemple:
A(1)B(3)A(5) est l´axiome et les règles de production sont:
r1: A(x) -> A(x+1): 0.4
remplace A(x) par A(x+1) avec la probabilité 0.4
r2: A(x) ->B(x-1): 0.6
remplace A(x) par B(x-1) avec la probabilité 0.6
r3: A(x) | B(y) | B(z): y B(x+z)[A(y)]
est une règle sensible au contexte qui remplace B(y), avec
A(x) pour contexte gauche et A(z) pour contexte droite, par B(x+z)
avec un branchement A(y), si y<4 est vérifié.
Appliquons ces règles à l´axiome:
Supposons que r1 s´applique à A(1): A(1)B(3)A(5) -> A(2)B(3)A(5)
Supposons que r2 s´applique à A(5): A(2)B(3)A(5) -> A(2)B(3)B(4)
Alors A(2)B(3)B(4) répond au contexte de la règle 3:
A(x) | B(y) | B(z) avec x=2, y=3 et z=4 vérifiant y
Donc la règle s´applique à B(3) qui devient B(6)[A(3)], d´où:
A(2)B(3)B(4) -> A(2)B(6)[A(3)]B(4)
Les règles de production peuvent aussi contenir des instructions
assignant des variables locales notées: {x=1;}
Elles comportent aussi des tableaux selon la syntaxe C: Tab[N].
La liste des productions est ordonnée. Dans le cas
déterministe elles sont exécutées séquentiellement et dans le cas
stochastique elles sont choisies aléatoirement.
La position et l´orientation de la tortue est définie par
un vecteur P(x,y,z) et 3 vecteurs X, Y et Z de rotations.
F: avancer dans la direction X
+: rotation positive autour de X
-: rotation négatve autour de X
+: rotation positive autour de X
&e;: rotation positive autour de Y
^: rotation négative autour de Y
/: rotation positive autour de Z
back slash: rotation négative autour de Z
Les valeurs de cette translation et de ces rotations peuvent
être passées en paramètres.
Les modules spéciaux d´interaction sont de la forme: ?I(x,y,z), en
ce qui concerne la communication plante -> environnement,
avec I = P, X, Y ou Z et (x,y,z) = valeurs des paramètres de I.
Exemple:
?P(x,y,z): Passe à l´environnement la position (x,y,z) de la tortue,
qui peut être utilisée pour détecter les collisions de la plante avec
des obstacles (Y compris elle-même).
Ils sont de la forme ?E(r) en ce qui concerne la communicattion
dans l´autre sens (voir un exemple ci-dessosu).
Modèle de plante controlé par la lumière
Kanamaru [KANAMARU 1992] calcule la quantité de lumière atteignant
un ensemble de feuilles en les projetant sur un hemisphèrer. Le
pourcentage de la surface couverte est une mesure de l´éclairement.
Le modèle de plante répond en simulant un héliotropisme en favorisant
la croissance dans la direction de la lumière.
La plante envoie une position (x,y,z) et le rayon r d´un groupe
de feuilles. L´environnement renvoie l´éclairement r via le
module ?E(r).
Calcul de l´éclairement r:
Fi est le groupe de feuilles dont on calcule l´éclairement
L est la lumière éclairante d´intensité I
(Fj}j est l´ensemble des autres groupes pouvant
intercepter la lumière issue de L.
Ai est la projection de Fi sur un plan P perpendiculaire à la
direction de L
Aij = l´intersection des projections Ai et Aj
L´écliarement est donné par (voir figure LS-6):
r = (Ai - Aij)*I + ti*Aij*I avec ti = transparence du groupe j
Figure LS-6: Calcul de l´eclairement d´un groupe de feuilles.
Bibliographie
J.S. HANAN
Parametric L-systems and their application to the modeling and
visualization of plants
PhThesis, University of Regina, 1992
Jean-Claude HEUDIN
La Vie Artificielle
HERMES, 1994
N. KANAMARU, CHIBA, K. TAKAHASHI, N. SAITO
Simulation of natural shapes of botanical trees based on heliotropism
Institute of Electronics, 1992
Aristid LINDENMAYER
Mathematicals Models for Cellular Interactions in Development
Journal of Theorical Biology 18,280-315, 1968
Aristid LINDENMAYER
Developmental systems without cellular interaction, their languages
and grammar
Journal of Theoretical Biology (30),455-484, 1971
Aristid LINDENMAYER, Grzegorz ROZENBERG
Automata, Languages, Development
North-Holland Publishing Company, 1975
Radomir MECH, Przemyslaw PRUSINKIEWICZ
Visual Models of Plants Interacting with Their Environment
Computer Graphics 397-410, 1996
P. PRUSINKIEWICZ, LINDENMAYER
The algorithmic beauty of plants
Springer-Verlag, 1990
P. James PRUSINKIEWICZ, R. MECH
Synthetic topiary
SIGGRAPH 1994
G. ROZENBERG
T0L L-systems and languages
Information and Control (23),357-381, 1973
Alvy Ray SMITH
Plants, Fractals and Formal Languages
Computer Graphics (18),1-10, 1984