Le jardinier numérique (2/4): systèmes déterministes non contextuels

Les systèmes déterministes non contextuels ou DOL-systèmes sont les plus simples des L-systèmes. Concrètement, on va remplacer itérativement les lettres d'un mot par d'autres lettres. Chaque règle de réécriture (ou production) décrit la transformation d'une lettre en une autre, en un mot ou en rien. À chaque itération, les productions sont appliquées simultanément à l'ensemble des lettres du mot.

Soient les productions suivantes : $a \rightarrow ab$ (a se transforme en ab) et $b \rightarrow a$ (b se transforme en a).

Considérons que notre mot de départ est b, voici sa transformation au cours de quatre itérations: $b \rightarrow a \rightarrow ab \rightarrow aba \rightarrow abaab$

Les L-systèmes déterministes produisent toujours le même résultat pour une même configuration de départ (même mot de départ et mêmes productions).

Formalisme

Soit $V$ un alphabet, $V^{*}$ est l'ensemble des mots sur $V$ , $V^{+}$ est l'ensemble des mots non vides sur $V$ .

Un L-système sans contexte (ou OL-système) est décrit par le triplet $G = <V, \omega, P>$ , où :

$V$ est l'alphabet du système,
$\omega \in V^{+}$ , un mot non vide appelé axiome,
$P \in V \times V^{*}$ , un ensemble fini de productions.

Si une paire $(a, \chi)$ est une production, on écrit $a \rightarrow \chi$ . La lettre $a$ et le mot $\chi$ sont appelés respectivement prédécesseur et successeur de la production.

On suppose que quelque soit $a \in V$ , il existe au moins un mot $\chi \in V^{*}$ tel que $a \rightarrow \chi$ . Si aucune production n'est donnée pour un prédécesseur $a \in V$ , on considère que la production $a \rightarrow a$ fait partie de l'ensemble des productions $P$ .

Un L-système non contextuel est déterministe si, et seulement si, quelque soit $a \in V$ , il existe exactement un unique $\chi \in V^{*}$ tel que $a \rightarrow \chi$ .

Suite de la promenande botanique