Automate universel d’Oméga-langages

Automate universel d’Oméga-langages

Dans la suite de cette étude, nous manipulons un certains nombre d’ex- tensions des automates élémentaires comme par exemple les automates à multiplicité ou encore les automates bidirectionnels. Une autre extension que nous allons aborder dans ce chapitre consiste à ne plus traiter des séquences finies de lettres mais des séquences infinies. Les mots infinis apparaissent naturellement en informatique pour décrire le comportement de processus (potentiellement) infinis et de modéliser des calculs qui ne sont pas censés se terminer comme par exemple des programmes de contrôle, des systèmes d’exploitation ou encore des protocoles réseaux ; ils constituent une exten- sion naturelle des mots finis. Comme nous l’avons déjà vu, quand il s’agit de langages rationnels, différents types de formalismes peuvent être étudiés : les automates, les monoïdes, les expressions rationnelles, . . . Il existe des no- tions similaires pour les langages rationnels sur les mots infinis, également appelés langages ω-rationnels. En effet, les monoïdes classiques ainsi que les expressions rationnelles ont été étendues aux ω-semigroupes et aux expres- sions ω-rationnelles respectivement. Bien que ces deux notions soient sans équivoque, pour ce qui est du modèle des automates, il existe plusieurs ex- tensions pour les mots infinis : les automates de Büchi, les automates de Muller, les automates de Rabin, . . . Le formalisme le plus intuitif, qui corres- pond aux automates de Büchi et qui s’avère être le modèle que nous allons utiliser dans ce chapitre, possède certains inconvénients.

Quelques uns des résultats bien connus sur les mots finis se transposent également sur les mots infinis comme par exemple le célèbre théorème de Kleene que nous avons déjà vu sur les mots finis et qui affirme, sur les mots infinis, que les langages ω-rationnels sont exactement les langages qui sont reconnus par les automates de Büchi et, par extension, par les ω-semigroupes. Cela dit, il y a d’autres propriétés qui ne s’appliquent pas au cas des mots infinis comme par exemple l’existence d’un automate déterministe minimal canonique : les automates de Büchi déterministes sont strictement moins expressifs que les non-déterministes et de ce fait, il n’y a pas de notion d’au- tomate de Büchi minimal. Carton et Michel [16] ont prouvé que les automates prophétiques (qui correspondent, de façon pertinente, à la notion de détermi- nisme « droite/gauche ») sont aussi expressifs que les automates de Büchi, mais il n’existe pas d’automate prophétique minimal unique pour un ω-langage donné. Cela dit, l’automate minimal n’est pas le seul automate canonique associé à un langage rationnel. . . Dans ce chapitre, nous étudions une extension d’un autre automate ca- nonique associé à chaque langage rationnel. En 1971, Conway [20] introduit la notion de factorisation d’un langage rationnel (par le biais de sa matrice des facteurs). Ce concept a conduit à la définition d’un nouvel objet appelé l’automate universel d’un langage [35, 45]. Il possède plusieurs propriétés im- portantes étant donné que tout automate qui reconnaît le même langage L a une image par morphisme qui se trouve être un sous-automate de l’automate universel de L. Par exemple, il peut être utilisé pour calculer un automate fini (non déterministe) de taille minimal [42], ou dans des preuves théoriques sur l’existence d’automates possédant des propriétés particulières (hauteur d’étoile [34], réversibilité [32],etc.).

Nous avons étendu le concept de factorisation aux langages ω-rationnels. Avec ces ω-factorisations, nous avons construit l’automate universel d’un lan- gage ω-rationnel et nous avons prouvé que, moyennant une conversion sous forme normale, tout automate de Büchi a une image par morphisme dans cet automate (propriété d’universalité), et que cet automate est minimal pour cette propriété. Dans la première partie, nous rappelons quelques définitions basiques à propos des langages sur mots infinis et des automates de Büchi. De même, pour les besoins de la construction de l’automate universel, nous introdui- sons la forme normale d’un automate de Büchi. Finalement, nous rappelons la définition d’ω-semigroupe donnée par [41] et le principe de reconnaissance (par morphisme) d’un langage ω-rationnel par un ω-semigroupe. La dernière partie est consacrée à la définition de l’automate universel d’un langage ω-rationnel L. Cela fait intervenir aussi bien les ω-factorisations pures que les standard ainsi que des factorisations dites positives sur les mots finis. Enfin, nous exposons les principales propriétés de cet automate : il accepte exactement L, il a la propriété d’universalité et il est minimal parmi les automates universels de L.