Génération aléatoire

Définitions et notations

Dans cette section, nous fournissons quelques définitions, certaines inédites et d’autres bien connues, qui seront indispensables pour la suite. 1.1 Automates Dans cette partie, nous ne manipulerons que des automates déterministes, c’est à dire des automates qui sont des tuples hQ, A, δ, {i}, Fi où l’unique état initial est i et où la fonction de transition (partielle) δ est une fonction de Q × A dans Q (l’image d’une paire (état,lettre) ne peut être qu’un singleton ou ∅). Dans la suite, si p est un état d’un automate A, on note Ap l’ensemble des lettres a ∈ A telles que δ(p, a) est défini. Définition 1.1 Un état q ∈ Q est transitoire si pour tout w ∈ A+, δ(q, w) 6= q. Un état qui n’est pas transitoire est appelé récurrent. Un automate est acyclique quand chacun de ses états est transitoire. Cette nouvelle définition d’automate acyclique nous sera utile dans la suite. A noter qu’il est impossible pour un automate complet d’être acyclique. Dans la suite, sans perte de généralité, l’ensemble des états Q d’un automate déterministe à n états sera toujours {1, . . . , n}, 1 sera toujours l’état initial, et nous assumons également qu’à partir de maintenant n ≥ 2. De plus, étant donné que nous ne traitons désormais que des automates acycliques, accessibles et déterministes, nous les appellerons simplement « automates acycliques ». On note An l’ensemble de tous les automates acycliques à n états. Nous considérons également, à partir de maintenant, que |A| ≥ 2, le cas  |A| = 1 étant trivial pour les questions que nous traitons dans ce qui suit. 1.2 Automates en hamac La notion d’automate en hamac va être très utile dans la seconde partie où nous nous concentrons sur les automates acyclique minimaux. Définition 1.2 Un automate acyclique A est appelé automate en hamac s’il possède un unique état sans transition sortante, appelé l’état cible. Proposition 1.1 Soit A = (Q, A, δ, {1}, F) un automate en hamac et soit s ∈ Q un état de A. Alors il existe un chemin de s à l’état cible. Démonstration. Étant donné que A est acyclique tous les chemins dans A ont une longueur bornée par n−1. Soit t l’état cible. Soit w un chemin tel que δ(s, w) est défini et tel que la longueur de w est maximale parmi les chemins partant de s. Par contradiction, on suppose que δ(s, w) = r 6= t. Alors r possède une transition étiquetée par la lettre a. Donc δ(s, wa) est définie et |wa| = |w| + 1 > |w|. Ce qui est impossible étant donné que la longueur de w est maximale parmi les chemins partant de s. Donc δ(s, w) = t.

Automates minimaux

Pour des raisons pratiques, nous avons besoin de calculer l’automate minimal d’un langage rationnel L en partant d’un automate déterministe qui le reconnait. Pour cela, nous avons besoin d’une nouvelle relation d’équivalence, appelée équivalence de Nerode. Cette relation d’équivalence ∼ est définie sur les états d’un automate donné A de la façon suivante : p ∼ q ⇐⇒ FutA(p) = FutA(q), Si un automate est déterministe l’équivalence satisfait la propriété suivante. p ∼ q ⇐⇒    p ∈ F ⇐⇒ q ∈ F, Ap = Aq, ∀a ∈ Ap, δ(p, a) ∼ δ(q, a). Théorème 1.2 Un automate déterministe est minimal s’il est émondé 1 et si toute classe d’équivalence est réduite à un singleton. 1. Dans la littérature l’automate minimal est défini soit comme un automate complet soit comme un automate émondé. Nous utilisons la seconde définition ici.  L’équivalence de Nérode peut être utilisée pour calculer l’automate minimal de L à partir d’un automate déterministe qui reconnaît L : on fusionne deux états qui sont équivalents jusqu’à ce que la relation d’équivalence soit l’égalité. L’automate ainsi obtenu est exactement l’automate minimal du langage, et la plupart des algorithmes de minimisation procèdent de cette façon. Comme nous le verrons dans la Section 4.2, les automates acycliques minimaux sont toujours des automates en hamac. De même que nous voulons que l’état initial soit étiqueté par 1, il est pratique de choisir une étiquette (toujours la même) pour l’état cible : dans ce qui suit nous notons Mn l’ensemble des automates acycliques minimaux à n états, dont l’état initial est 1 et l’état cible est n. 1.4 Automorphisme d’automates Soit A = (Q, A, δ, {1}, F) un automate déterministe. Une bijection φ de Q dans Q est un automorphisme quand – φ(1) = 1, – ∀p ∈ Q, Ap = Aφ(p) , – ∀p ∈ Q, ∀a ∈ Ap, δ(φ(p), a) = φ(δ(p, a)), – ∀p ∈ Q, p ∈ F ⇐⇒ φ(p) ∈ F. Comme l’a fait remarqué Liskovets [29], le seul automorphisme d’un automate accessible et déterministe est l’identité. Ceci a l’importante conséquence combinatoire qu’il y a exactement (n − 1)! façons distinctes d’étiqueter avec {1, . . . , n} les états d’un tel automate de taille n, avec la convention que 1 est l’état initial. En particulier, pour une famille Fn d’automates accessibles et déterministes de taille n, stable par ré-étiquetage, le fait de générer aléatoirement et de façon uniforme un élément étiqueté de Fn, puis de supprimer les étiquettes (formellement : de considérer sa classe d’équivalence à l’étiquetage près) n’influence pas l’uniformité. Pour les éléments de Mn, comme nous demandons que 1 soit l’état initial et n l’état cible, le même résultat est vrai, mais il y a maintenant exactement (n − 2)! éléments dans chaque classe d’équivalence, à l’étiquetage près. 1 2 3 a a a Figure 1.1 – Un automate déterministe qui n’est pas accessible. A noter que son groupe d’automorphisme n’est pas trivial : si nous permutons l’étiquette 2 avec l’étiquette 3 nous obtenons le même automate.  Figure 1.2 – Un automate déterministe accessible. A la différence de l’automate précédent, toute permutation non triviale des étiquettes produit un automate différent. 2 Chaînes de Markov et génération aléatoire Dans cette section nous décrivons la chaîne de Markov utilisée pour générer aléatoirement et de façon presque uniforme les éléments de An, pour tout n ≥ 2 fixé. Nous en profitons pour rappeler la notion de base d’une chaîne de Markov dont nous aurons besoin dans la suite. Pour plus d’informations sur les chaînes de Markov pour la génération aléatoire, voir [28]. L’entrée de l’algorithme consiste en deux entiers positifs : le nombre d’états n, et le nombre d’itérations T. L’algorithme repose sur un processus de chaîne de Markov : il se déplace aléatoirement dans l’ensemble An et retourne l’automate atteint après T itérations. La chaîne de Markov de l’algorithme peut être vue comme un graphe orienté dont les sommets sont des éléments de An. Définition 2.1 Une chaîne de Markov est dite irréductible quand son graphe est fortement connexe. Un arc d’un automate A vers un autre automate B est étiqueté par un réel r ∈ [0, 1], qui représente la probabilité de se déplacer de l’automate A à l’automate B en une seule itération. Pour deux automates A et B de An, on note PA,B l’étiquette de l’arc de A à B, s’il existe, sinon on note PA,B = 0. Comme il s’agit d’une probabilité, on a : ∀A ∈ An, X B∈An PA,B = 1. Définition 2.2 Une distribution sur An est une application p de An dans [0, 1] telle que X A∈An p(A) = 1 Une distribution stationnaire π d’une chaîne de Markov est une distribution qui reste globalement inchangée après chaque déplacement aléatoire, i.e. ∀B ∈ An, π(B) = X A∈An π(A) × PA,B