Grammaire

Grammaire de Lindenmayer

L-System

Un L-System est un système de réécriture formelle que nous allons présenter de façon simplifiée comme suit. Il nous faut à minima trois éléments :

Un alphabet
Un axiome de départ (le mot initial)
Une règle de réécriture

La régle de réécriture indique comment passer d'une génération à une autre, en donnant pour un symbole de l'alphabet son devenir à la génération suivante

Exemple

L'algue de LINDENMAYER était un système sensé représenter l'évolution d'une algue unicellulaire. L'alphabet contenait deux lettres A et B. Le mot de départ était A. La règle de réécriture était la suivante :

A devient AB
B devient A

Si on applique ce système pour 5 générations, voici ce que l'on obtient :

n = 0, A
n = 1, AB
n = 2, AB A
n = 3, AB A AB
n = 4, AB A AB AB A
n = 5, AB A AB AB A AB A AB

À faire vous même

Écrivez la chaine de caractère obtenue à la génération suivante, pour n = 6

Pour n = 6, on aura AB A AB AB A AB A AB AB A AB AB A

Codage informatique

Premiers remplacements

Cette grammaire formelle se prête très bien à un code informatique. On va créer une fonction remplacer_algue qui va prendre en entrée une chaine de l'algue de LINDENMAYER et qui en sortie va renvoyer la génération suivante. Vous compléterez le code fourni pour cela.

def remplacer_algue(mot):
    mot_suivant = ""
    # Mettez votre code ici
    return mot_suivant

# Test de la fonction
algue = "A"
print(algue)
for k in range(6):
    algue = remplacer_algue(algue)
    print(algue)

Règles de réécriture

Plutôt que de faire une fonction propre à chaque type de L-system, on va faire une fonction générique qui permettra de passer à la génération suivante en passant à la fonction deux éléments :

Le mot actuel
les règles de réécriture

À faire vous même

À votre avis, quelle structure informatique est adaptée pour stocker les règles de réécriture ?

Le mieux est d'utiliser un dictionnaire. Les clefs seront les symboles de l'alphabet à remplacer et les valeurs seront les chaînes de remplacement. Comme chaque symbole de l'alphabet ne peut avoir qu'une seule réécriture, le dictionnaire est adapté.

Vous allez donc compléter le programme suivant, avec la fonction remplacer_dico qui prend en entrée :

un mot
un dictionnaire qui représente les remplacements

et l'éxécuter pour pouvoir obtenir l'exemple de départ

Le code final

On va encore ajouter un élément à notre fonction : au lieu de se contenter d'avoir juste la génération suivante, on aura directement la génération n° k. Pour cela, il suffit de passer le numéro de la génération en paramètre de la fonction. On va donc écrire une fonction l_system qui prend en entrée trois paramètres :

le mot initial
le dictionnaire des règles de réécriture
le nombre de générations à effectuer

et qui retournera en sortie le mot correspondant à la génération recherchée.

Pensez à sauvegarder votre code avant de passer à la suite, vous en aurez besoin pour l'exercice final.. Mais pour le moment, nous allons voir (ou revoir) le module turtle qui permet de faire facilement des dessins en python.