#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ idioma_hasard.py — Générateur aléatoire de termes d'un langage algébrique. Le langage est présenté par ses générateurs entre crochets angulaires : L'automate { |--a, |--b, |--f(.), |--g(.,.), |--h(.,.,.) } est ici parcouru au hasard : à chaque appel il tire une règle de production selon des probabilités transmises en argument, chaque point "." de la règle choisie déclenchant un nouvel appel récursif du générateur. C'est un processus de branchement (Galton-Watson) : le nombre moyen de descendants m = somme des p_s * arité(s) décide de la terminaison. m < 1 : terminaison presque sûre, taille moyenne 1/(1-m) ; m = 1 : terminaison presque sûre, taille moyenne infinie ; m > 1 : probabilité strictement positive de ne jamais terminer. Un garde-fou de profondeur protège les régimes critiques. """ import re import random # ---------------------------------------------------------------------- # 1. Analyse de la présentation # ---------------------------------------------------------------------- def analyse_signature(spec: str) -> dict: """ Extrait de la présentation la signature du langage : un dictionnaire { symbole : arité }. >>> analyse_signature("") {'a': 0, 'b': 0, 'f': 1, 'g': 2, 'h': 3} """ spec = spec.strip() if not (spec.startswith("<") and spec.endswith(">")): raise ValueError("La présentation doit être encadrée par < et >.") interieur = spec[1:-1] motif = re.compile(r"([A-Za-z_][A-Za-z_0-9]*)\s*(\((\s*\.\s*(,\s*\.\s*)*)\))?") signature = {} pos = 0 while pos < len(interieur): while pos < len(interieur) and interieur[pos] in " ,\t\n": pos += 1 if pos >= len(interieur): break m = motif.match(interieur, pos) if not m: raise ValueError(f"Générateur illisible à partir de : {interieur[pos:]!r}") symbole = m.group(1) arite = 0 if m.group(2) is None else m.group(2).count(".") if symbole in signature and signature[symbole] != arite: raise ValueError(f"Le symbole {symbole!r} est déclaré avec deux arités.") signature[symbole] = arite pos = m.end() if not signature: raise ValueError("La présentation ne contient aucun générateur.") return signature # ---------------------------------------------------------------------- # 2. Le générateur aléatoire # ---------------------------------------------------------------------- class ProfondeurDepassee(Exception): """Levée quand la récursion excède le garde-fou de profondeur.""" class GenerateurHasard: """ Générateur aléatoire de termes : à chaque appel, une règle de production est tirée selon les probabilités données ; chaque point "." de la règle est un appel récursif du générateur. """ def __init__(self, signature: dict, probabilites: dict, profondeur_max: int = 500, graine=None): self.signature = dict(signature) self.profondeur_max = profondeur_max self.alea = random.Random(graine) # -- validation des probabilités ------------------------------------ manquants = set(signature) - set(probabilites) etrangers = set(probabilites) - set(signature) if manquants: raise ValueError(f"Probabilité absente pour : {sorted(manquants)}") if etrangers: raise ValueError(f"Symboles hors signature : {sorted(etrangers)}") if any(p < 0 for p in probabilites.values()): raise ValueError("Les probabilités doivent être positives.") total = sum(probabilites.values()) if abs(total - 1.0) > 1e-9: raise ValueError(f"Les probabilités doivent sommer à 1 (somme = {total}).") if sum(p for s, p in probabilites.items() if signature[s] == 0) == 0: raise ValueError("Au moins une constante doit avoir une probabilité " "non nulle, sinon aucun terme fini n'est engendrable.") self.probabilites = dict(probabilites) # tirage : listes parallèles symboles / poids self._symboles = list(self.probabilites) self._poids = [self.probabilites[s] for s in self._symboles] # -- analyse de criticité ------------------------------------------------ def moyenne_descendants(self) -> float: """m = somme des p_s * arité(s) : critère de terminaison.""" return sum(p * self.signature[s] for s, p in self.probabilites.items()) def regime(self) -> str: m = self.moyenne_descendants() if m < 1 - 1e-9: return "sous-critique" if m > 1 + 1e-9: return "sur-critique" return "critique" def taille_moyenne(self): """Taille moyenne des termes engendrés (infinie si m >= 1).""" m = self.moyenne_descendants() return 1.0 / (1.0 - m) if m < 1 - 1e-9 else float("inf") # -- l'automate parcouru au hasard ----------------------------------------- def _terme(self, profondeur: int) -> str: if profondeur > self.profondeur_max: raise ProfondeurDepassee # tirage de la règle de production selon les probabilités symbole = self.alea.choices(self._symboles, weights=self._poids)[0] arite = self.signature[symbole] if arite == 0: # règle |--s return symbole sous_termes = [self._terme(profondeur + 1) # les points "." : for _ in range(arite)] # appels récursifs return f"{symbole}({','.join(sous_termes)})" def tirer(self) -> str: """ Engendre un terme au hasard. Si le garde-fou de profondeur est atteint (régimes critique et sur-critique), le tirage est recommencé : le terme rendu est donc toujours fini. """ while True: try: return self._terme(0) except ProfondeurDepassee: continue # tirage abandonné def __call__(self) -> str: return self.tirer() def echantillon(self, m: int) -> list: """Engendre m termes au hasard.""" return [self.tirer() for _ in range(m)] def __repr__(self): regles = ", ".join( (f"|--{s}" if k == 0 else f"|--{s}({','.join(['.'] * k)})") + f" [{self.probabilites[s]:g}]" for s, k in self.signature.items() ) return "{" + regles + "}" # ---------------------------------------------------------------------- # 3. La fonction demandée # ---------------------------------------------------------------------- def idioma_hasard(spec: str, probabilites: dict, **options) -> GenerateurHasard: """ Construit et retourne le générateur aléatoire de termes du langage présenté par `spec`, chaque règle de production étant tirée selon `probabilites` : un dictionnaire {symbole: proba} de somme 1. >>> G = idioma_hasard("", ... {"a": 0.3, "b": 0.3, "f": 0.2, "g": 0.15, "h": 0.05}, ... graine=2026) >>> t = G() # un terme au hasard """ return GenerateurHasard(analyse_signature(spec), probabilites, **options) # ---------------------------------------------------------------------- # 4. Programme principal # ---------------------------------------------------------------------- SYNOPSIS = """ ====================================================================== idioma_hasard — génération aléatoire de termes d'un langage ====================================================================== Le langage est présenté par ses générateurs entre < et > : L'automate { |--a, |--b, |--f(.), |--g(.,.), |--h(.,.,.) } est parcouru au hasard : à chaque appel une règle de production est tirée selon les probabilités transmises en argument, chaque point "." de la règle déclenchant un appel récursif du générateur. Terminaison (processus de branchement, m = somme p_s * arité(s)) : m < 1 sous-critique : taille moyenne finie = 1/(1-m) m = 1 critique : termine, mais taille moyenne infinie m > 1 sur-critique : risque de non-terminaison (garde-fou) idioma_hasard(présentation, probabilités) retourne un générateur G : - G() ou G.tirer() un terme au hasard ; - G.echantillon(m) m termes au hasard ; - G.regime() sous-critique / critique / sur-critique ; - G.taille_moyenne() espérance de la taille des termes. ====================================================================== """ if __name__ == "__main__": print(SYNOPSIS) presentation = "" probabilites = {"a": 0.30, "b": 0.30, "f": 0.20, "g": 0.15, "h": 0.05} print(f"Présentation du langage : {presentation}") print(f"Probabilités des règles : {probabilites}") G = idioma_hasard(presentation, probabilites, graine=2026) print(f"Automate parcouru : {G}\n") m = G.moyenne_descendants() print(f"Nombre moyen de descendants m = {m:.3f} ({G.regime()})") print(f"Taille moyenne théorique des termes : {G.taille_moyenne():.3f}\n") print("Dix termes tirés au hasard :") for t in G.echantillon(10): apercu = t if len(t) <= 60 else t[:57] + "..." print(f" {apercu}") # -- vérification empirique de la taille moyenne ------------------------- def taille(t): return len(re.findall(r"[A-Za-z_][A-Za-z_0-9]*", t)) N = 10_000 tailles = [taille(t) for t in G.echantillon(N)] print(f"\nTaille moyenne observée sur {N} tirages : " f"{sum(tailles) / N:.3f} (théorie : {G.taille_moyenne():.3f})") # -- contrôle de cohérence avec l'automate reconnaisseur ------------------ print("\nContrôle de cohérence avec l'automate reconnaisseur :") try: from idioma_recursif import idioma_recursif A = idioma_recursif(presentation) verdicts = all(A(t) for t in G.echantillon(500)) print(f" 500 termes tirés au hasard, tous reconnus : {verdicts}") except ImportError: print(" (idioma_recursif.py absent : contrôle sauté)") # -- illustration d'un régime sur-critique -------------------------------- print("\nIllustration : probabilités sur-critiques " "{a:0.1, b:0.1, f:0.1, g:0.2, h:0.5}") S = idioma_hasard(presentation, {"a": 0.1, "b": 0.1, "f": 0.1, "g": 0.2, "h": 0.5}, profondeur_max=200, graine=2026) print(f" m = {S.moyenne_descendants():.3f} ({S.regime()}) : " "les tirages divergents sont abandonnés par le garde-fou,") t = S.tirer() print(f" mais chaque terme rendu reste fini, par ex. taille {taille(t)}.")