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 décrit la transformation d'une lettre en une autre, en un mot ou en rien. À chaque itération, les régles de réécriture sont appliqués simultanément à l'ensemble des lettres du mot.
Soient les régles de réécritures 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
a
ab
aba
abaabLes 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 règles de production).
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 est décrit par le triple $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édecesseur 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édecesseur $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$.