On représente le monoïde engendré par deux éléments `a`, `b`, par un graphe orienté où les sommets sont les éléments du monoïde. Chaque sommet possède deux arrêtes partantes libellées `a` et `b`. Le sommet racine est l'élément neutre du monoïde. Et pour chaque sommet `x`, l'arrête libellée `a` partant de `x` arrive sur le sommet `x"*"a`, et l'arrête libellée `b` partant de `x` arrive sur le sommet `x"*"b`, où `"*"` est la loi du monoïde.

On commence par étape un programme en python qui aura pour but de construire ce graphe en mémoire.

On utilise le module numpy qui permet de manipuler des tableaux de façon efficace. On définit le type cellule, structuré comme suit : .

`{`
    `a " uint"32`      # Noeud fille selon la voie a
    `b " uint"32`      # Noeud fille selon la voie b
    `d " uint"32`      # Profondeur du noeud
    `L " uint"32`      # Pointeur
    `u0 " bool"`       # Indique si la cellule n'est pas libre
    `u1 " bool"`
    `u2 " bool"`
    `u3 " bool"`
    `u4 " bool"`
    `u5 " bool"`
    `u6 " bool"`
    `u7 " bool"`
`}`

On crée un tableau `M` uni-dimensionnel de 10_000 cellules libres initialisées comme suit :

Chaque cellule est désignée par son Indexe dans `M`. La cellule `M[0]` n'est pas utilisée. L'index `0` qui est la valeur minimal représente le rien.

Pour chaque cellule libre, l'attribut `L` contient l'indexe de la cellule libre suivante, et la dernière cellule contient comme attribut `L` la valeur `0` qui représente le rien.

La variable globale `L=1` désigne la première cellule vide du tableau `M`.

On crée le premier noeud qui correspond à l'élément neutre du monoïde en `M[1]`.
La variable `L` est alors modifiée comme suit : `L = M[L]"."L` afin de désigner la première cellule vide dans `M`.

`M[0]"."L= 0 `
`M[0]"."a = 0`
`M[0]"."b = 0`
`M[0]"."u0 = 1`     # Marque la cellule comme occupée (c'est un noeud)

Les enfants `M[0]"."a` et `M[0]"."b` n'étant pas encore définit, ils ont la valeur `0`.

Les cellules occupées sont appelées des nœuds, et correspondent au sommet du graphe, et correspondent aux éléments du monoïde.

Parfait, tu as déjà posé une base claire et structurée pour représenter le monoïde et son graphe orienté. Voici une implémentation fidèle à ta description, en utilisant numpy avec des types structurés pour définir le tableau `M` de cellules :

import numpy as np # Définition du type structuré pour une cellule cell_dtype = np.dtype([ ('a', np.uint32), # Fille par transition 'a' ('b', np.uint32), # Fille par transition 'b' ('d', np.uint32), # Profondeur ('L', np.uint32), # Pointeur vers cellule libre suivante ('u0', np.bool_), # Occupation ('u1', np.bool_), ('u2', np.bool_), ('u3', np.bool_), ('u4', np.bool_), ('u5', np.bool_), ('u6', np.bool_), ('u7', np.bool_) ]) # Taille du tableau de cellules N = 10_000 M = np.zeros(N, dtype=cell_dtype) # Initialisation de la liste des cellules libres for i in range(1, N - 1): M[i]['L'] = i + 1 M[N - 1]['L'] = 0 # Dernière cellule pointe vers rien # La cellule M[0] n'est pas utilisée (0 = rien) M[0]['L'] = 0 # Variable globale L désignant la première cellule libre L = 1 # Création du noeud racine (élément neutre du monoïde) root_index = L L = M[L]['L'] # Avancer dans la liste des cellules libres # Initialiser la cellule racine M[root_index]['L'] = 0 M[root_index]['a'] = 0 M[root_index]['b'] = 0 M[root_index]['d'] = 0 M[root_index]['u0'] = True # Marquer la cellule comme utilisée # Affichage de contrôle print(f"Racine créée à l'index {root_index}") print(f"Première cellule libre maintenant : {L}")

On nomme couramment "x" qui est un uint32, pour désigner la cellule M[x]. Et lorsque x=0 alors "x" ne désigne rien.
Définit une fonction "a" qui appliquée à un nœud "x", teste si "x" est bien un nœud sinon produit une erreur, puis si "x" a un fils x.a alors le retourne, sinon alloue une cellule libre et en fait un noeud relié comme étant le fils x.a et retourne-le. Considère ces fils comme étant non connus. Calcul sa profondeur qui vaut celle du père augmenté de +1

Voici la fonction a(x) conforme à ta demande. Elle :

1. Vérifie que x désigne un nœud valide (≠ 0 et occupé),
2. Si le fils par 'a' existe déjà, retourne simplement l’index,
3. Sinon, elle :
   • alloue une cellule libre,
   • l’initialise comme un nœud,
   • relie M[x] à ce nouveau nœud par l’attribut .a,
   • initialise sa profondeur à M[x].d + 1,
   • et retourne son index.

def a(x): global L, M if x == 0 or not M[x]['u0']: raise ValueError(f"Erreur : x={x} n'est pas un noeud valide.") if M[x]['a'] != 0: return M[x]['a'] # Fils déjà connu if L == 0: raise RuntimeError("Erreur : plus de cellules libres disponibles.") # Allouer une nouvelle cellule y = L L = M[L]['L'] # Avancer dans la liste libre # Initialisation du nouveau noeud M[y]['L'] = 0 M[y]['a'] = 0 M[y]['b'] = 0 M[y]['d'] = M[x]['d'] + 1 M[y]['u0'] = True # Marquer comme utilisé # Rattacher ce nouveau noeud à x par l'étiquette 'a' M[x]['a'] = y return y

Remarques :

• La fonction suppose que les variables globales L et M sont définies au préalable.
• Les autres drapeaux u1 à u7 restent à False par défaut, comme non utilisés pour l’instant.
• Tu peux créer une fonction équivalente b(x) pour la transition 'b'.

Souhaites-tu aussi une fonction générique prenant un label 'a' ou 'b' en argument, ou tu préfères garder des fonctions spécifiques ?

Voici la fonction b(x) définie sur le même modèle que a(x), pour gérer la transition 'b' :

def b(x): global L, M if x == 0 or not M[x]['u0']: raise ValueError(f"Erreur : x={x} n'est pas un noeud valide.") if M[x]['b'] != 0: return M[x]['b'] # Fils déjà connu if L == 0: raise RuntimeError("Erreur : plus de cellules libres disponibles.") # Allouer une nouvelle cellule y = L L = M[L]['L'] # Avancer dans la liste libre # Initialisation du nouveau noeud M[y]['L'] = 0 M[y]['a'] = 0 M[y]['b'] = 0 M[y]['d'] = M[x]['d'] + 1 M[y]['u0'] = True # Marquer comme utilisé # Rattacher ce nouveau noeud à x par l'étiquette 'b' M[x]['b'] = y return y

Points importants :

• Même logique que pour a(x).
• Si la transition 'b' depuis x est déjà définie, elle est simplement retournée.
• Sinon, une cellule est allouée et reliée.

Tu peux maintenant utiliser a(x) et b(x) pour explorer ou construire dynamiquement le graphe du monoïde.

Voici une fonction générique nommée chemin(x, mot) qui :

prend en argument un nœud de départ x (index dans le tableau M),

ainsi qu’un mot (chaîne composée uniquement de 'a' et 'b'),

et construit pas à pas le chemin correspondant dans le graphe du monoïde,

en utilisant les fonctions a(x) et b(x) déjà définies,

retourne finalement le nœud d’arrivée (index dans M).

def chemin(x, mot): if x == 0 or not M[x]['u0']: raise ValueError(f"Erreur : x={x} n'est pas un noeud valide.") for c in mot: if c == 'a': x = a(x) elif c == 'b': x = b(x) else: raise ValueError(f"Caractère invalide dans le mot : '{c}' (seuls 'a' et 'b' sont permis)") return x

Exemple d'utilisation :

# Créer le mot 'abaab' depuis la racine x_final = chemin(root_index, 'abaab') print(f"Le noeud correspondant à 'abaab' est à l'index {x_final}") print(f"Sa profondeur est {M[x_final]['d']}")

Cette fonction construit le chemin de manière paresseuse : elle n’explore que ce qui est nécessaire, et crée les nœuds fils à la volée.

Souhaites-tu maintenant une fonction pour afficher le chemin ou les transitions suivies depuis la racine jusqu’au nœud final ?