Automates et expressions rationnelles 

Télécharger le fichier original (Mémoire de fin d’études)

Automates et expressions rationnelles

La théorie des automates commen¸ca en 1956 lorsque Kleene établit l’équiva-lence entre expressions rationnelles et automates pour les ensembles de mots finis [21]. Depuis lors, ce célèbre théorème de Kleene a et´ généralis´ aux mots infinis [11, 25], bi-infinis [19, 26], aux mots indexés par des ordinaux [13], et enfin aux mots sur les ordres linéaires dispersés [8]. Dans ce chapitre, nous redonnons, pour chaque classe d’ordres linéaires dispersés, les opérateurs rationnels et les automates définissant la classe de langages rationnels correspondante.
B¨uchi et Muller furent les premiers à définir des automates acceptant des mots de longueur ω. B¨uchi généralisa ensuite les automates pour les mots sur les ordinaux. Ces derniers possèdent non seulement les transitions classiques des automates sur les mots finis c’est-à-dire de la forme p−→q o`u p et q sont des états et a une lettre de l’alphabet, mais également des transitions de la forme P → p o`u p est un état et P un ensemble d’états. Entre deux états successifs d’un chemin, il existe une transition etiquetée par la lettre correspondante. Au niveau des ordinaux limites, un chemin possède une transition P → p aux points o`u l’ensemble limite d’états est P . Un chemin possède toujours une fin, mˆeme lorsque son étiquette est de longueur limite. Ces automates acceptent les langages définis par les expressions rationnelles construites avec l’union finie, l’étoile, le ω-produit et l’itération sur les ordinaux dénombrables dénotée ♮. Ces automates sur les ordinaux dénombrables sont déterminisables ce qui montre que cette classe est fermée par complémentation et qu’elle forme une algèbre de Boole.
Plus récemment, cette théorie a et´ généralisée de fa¸con naturelle aux mots sur les ordres linéaires dénombrables dispersés par Bruyère et Carton. De fa¸con symétrique, ces automates possèdent des transitions limites à gauche de la forme P → p et des transitions limites à droite de la forme p → P o`u p est un état et P un ensemble d’état. La définition de chemin, basée sur la notion de coupures, généralise celle des chemins de longueurs finies et ordinales. Ils se construisent en insérant un état entre deux lettres consécutives de l’étiquette. Autrement dit, pour tout mot x index´ par un ordre linéaire I, un chemin d’étiquette x est une suite d’états indexés par l’ordre I des coupures de I. Lorsqu’un état p n’a pas de prédécesseur (respectivement pas de successeur) il doit exister une transition transition limite à gauche (respectivement `a droite) menant de l’ensemble cofinal à gauche vers p (respectivement de p vers l’ensemble cofinal à droite). Aux opérateurs rationnels des mots sur les ordinaux dénombrables, il faut ajouter les opérateurs inverses : le −ω-produit et l’itération ordinale dénombrable inverse −♮ ainsi qu’une sorte d’itérateur sur tous les ordres linéaires dispersés noté ⋄. On retrouve un théorème de Kleene pour les ensembles de mots sur des ordres linéaires dispersés.
Lorsqu’on restreint l’ensemble des opérations rationnelles utilisées dans les expressions, on obtient toute une hiérarchie de classes d’ensembles rationnels. En imposant des conditions sur les transitions limites des automates, on retrouve un théorème de Kleene pour chacune des classes. Par exemple, la classe des langages rationnels de rangs finis est définie par les expressions rationnelles utilisant l’union finie, le produit fini, l’étoile, le ω-produit et le −ω-produit. Ces langages sont exactement ceux acceptés par des automates sur les ordres linéaires dont les transitions limites de la forme p → P ou P → p vérifient p ∈/ P .
Ce chapitre rappelle les définitions d’ensembles rationnels de mots finis, in-finis, bi-infinis, mots sur les ordinaux et mots sur les ordres linéaires dispersés. Pour chaque classe d’ordre, les expressions rationnelles et les automates sont redéfinis.

Mots finis

Nous définissons dans cette partie la notion de langage rationnel de mots finis sur un alphabet A. Ces ensembles sont définis de fa¸con équivalente par des expressions rationnelles ou par des automates. Pour les exemples, on prendra l’alphabet A = {a, b}.

Expressions rationnelles

Tout ensemble rationnel peut ˆetre décrit par une expression rationnelle formée des lettres de l’alphabet et de symboles représentant les opérateurs. Pour deux ensembles X et Y ⊆ A∗, on définit les opérations suivantes :
l’union X + Y = {z | z ∈ X ou z ∈ Y }
le produit X • Y = {xy | x ∈ X et y ∈ Y } X ∗ n
l’itération = { Π xi | n ∈ N et pour tout 1 ≤ i ≤ n , xi ∈ X } i=1
Définition 1 La classe Rat(A∗) des langages rationnels de A ∗ est la plus petite famille contenant l’ensemble P(A) des parties de A et fermée par union finie, produit fini et itération finie.
Exemple 7 L’expression rationnelle A∗aA∗ représente l’ensemble des mots finis sur l’alphabet A contenant la lettre a.
Exemple 8 L’ensemble X ∈ Rat(A∗) des mots possédant un nombre pair d’occurrences de la lettre a est représent´ par l’expression (ab∗a + b)∗ et son complémentaire A∗ \ X par l’expression b∗a(ab∗a + b)∗.
Notons que la classe Rat(A∗) des langages rationnels est strictement incluse dans celle des langages de A∗. Par exemple, l’ensemble des mots contenant exactement autant de a que de b n’est pas rationnel.

Automates

Nous définissons ici les automates sur les mots finis qui permettent, comme les expressions rationnelles, de décrire de fa¸con finie les ensembles de mots.
Définition 2 Un automate est un quintuplet (Q, A, E, I , F ) o`u
– Q est un ensemble fini d’états,
– A est un alphabet fini,
– E ⊆ (Q × A × Q) est un ensemble de transitions,
– I ⊆ Q est un ensemble d’états initiaux,
– F ⊆ Q est un ensemble d’états finaux.
Un automate est représent´ par un diagramme o`u les états sont représentés par des cercles et les transitions par des flèches. Les états initiaux sont marqués par une flèche entrante et les états finaux par une flèche sortante.
Exemple 9 L’automate A = (Q = {0, 1}, A = {a, b} , E = {(0, a, 0), (0, a, 1), (1, a, 1), (1, b, 1), (1, a, 0)}, I = {0}, F = {0}) est représent´ par le diagramme suivant : Un automate A = (Q, A, E, I , F ) possède un chemin menant de l’état p ∈ Q à l’état q ∈ Q s’il existe un entier n et une suite d’états (qi)0≤i≤n tels que q0 = p, qn = q et pour tout 0 ≤ i ≤ n − 1, il existe ai ∈ A tel que (qi, ai, qi+1) ∈ E. Le mot u = a0a1 . . . an−1 est l’étiquette de ce chemin et n sa longueur. L’ensemble {q0, q1 , . . . , qn} est le contenu du chemin.
Un chemin est dit acceptant s’il mène d’un état initial à un état final. Un mot est accept´ par un automate s’il est l’étiquette d’un chemin acceptant.
Exemple 10 L’automate de l’exemple 9 accepte exactement les mots com-men¸cant et finissant par la lettre a ainsi que le mot vide ǫ.
Les notions d’automates et d’expressions rationnelles sont équivalentes.
Théorème 4 (Kleene, [21]) Un ensemble de mots finis est rationnel si et seule-ment s’il est accept´ par un automate.
Exemple 11 L’automate de la figure 2.1 accepte le langage rationnel (ab∗a+b)∗ des mots contenant un nombre pair de a p =⇒ q l’existence d’un chemin menant de p à q et d’étiquette u dans A.
Un automate A = (Q, A, E, I , F ) est dit déterministe si quels que soient q ∈ Q et a ∈ A, il existe au plus un état p ∈ Q tel que (q, a, p) ∈ E et si l’ensemble I des états initiaux est réduit à un singleton. Il est complet si quels que soient q ∈ Q et a ∈ A, il existe au moins un état p ∈ Q tel que (q, a, p) ∈ E. Un automate est co-déterministe si quels que soient p ∈ Q et a ∈ A, il existe au plus un état q ∈ Q tel que (q, a, p) ∈ E. Il est non-ambigu si pour tous les états p, q ∈ Q et tout mot x ∈ A∗, il existe au plus un chemin menant de p à q d’étiquette x.
Exemple 12 L’automate de l’exemple 9 n’est pas déterministe puisqu’en par-tant de l’état 0 et en lisant la lettre a les transitions vers les états 0 et 1 sont autorisées. Il n’est pas complet non plus car il n’existe aucune transition partant de l’état 0 et d’étiquette b.
Théorème 5 Tout ensemble rationnel de mots finis est accept´ par un automate déterministe et complet.
Exemple 13 L’automate de la figure 2.2 est déterministe, complet et accepte le mˆeme langage que l’automate de l’exemple 9.
Soit X un sous-ensemble rationnel de A∗ et soit A un automate complet et déterministe acceptant X Il suffit d’échanger les états finaux pour obtenir un automate acceptant le complémentaire A∗ \ X . Exemple 14 L’automate de la figure 2.3 accepte le complémentaire A∗\(aA∗a+ ǫ) = bA∗ + A∗b du langage accept´ par l’automate de l’exemple 9.
Proposition 6 La classe des ensembles rationnels de mots finis est fermée par union finie, intersection, produit fini, étoile et complémentation dans A∗.
Les automates etudiés dans la suite pourront toujours ˆetre complétés en ajou-tant un état “puits” o`u convergent toutes les transitions ajoutées. C’est le cas de l’état 3 de l’automate de la Figure 2.2. Lorsque les automates sont équivalents à des automates déterministes, la fermeture par complémentation de la classe de langages correspondante s’obtiendra donc par la méthode dite de déterminisation. D’autre part, notons qu’une forme canonique existe pour les automates sur les mots finis. Parmi tous les automates déterministes et complets acceptant un ensemble rationnel donné, il en existe un unique, dit minimal qui possède strictement moins d’états que les autres.

Mots de longueur ω

Les ensembles rationnels de mots de longueur ω ont et´ principalement etudiés par B¨uchi [12], Muller [25] et McNaughton [23]. Différents types d’auto-mates ont et´ définis, largement détaillés dans [32]. Nous rappelons rapidement ceux de B¨uchi et de Muller par souci historique.

Automates

Nous redonnons dans ce paragraphe les deux types d’automates acceptant des mots de longueur ω introduits indépendamment par B¨uchi [12] et Muller [25]. Tous deux sont définis à partir d’automates sur les mots finis et se distinguent par leurs conditions d’acceptation d’un chemin. Soit A un automate sur les mots finis. Un chemin de longueur ω est une suite d’états (qi)i∈ω telle que pour tout i ∈ ω, il existe une lettre ai ∈ A telle que (qi, ai, qi+1 ) ∈ E. Le mot u = a0a1 . . . est l’étiquette de ce chemin. On dit qu’il passe infiniment souvent par un état p si pour tout i ∈ ω, il existe j > i tel que qj = p.
Automates de B¨uchi :
Un automate de B¨uchi est un automate (Q, A, E ⊆ Q×A×Q, I ⊆ Q, F ⊆ Q) acceptant les étiquettes des chemins passant infiniment souvent par au moins un état de F .
Exemple 16 L’automate de B¨uchi de la figure 2.4 accepte exactement l’en-semble des mots possédant un nombre fini d’occurrences de la lettre b. Il est complet.

Table des matières

1 Définitions et notations 
1.1 Ensembles, relations et fonctions
1.2 Cardinaux
1.3 Ordinaux
1.4 Ordres linéaires
1.4.1 Définitions et opérations
1.4.2 Ordres linéaires dispersés
1.4.3 Coupures
1.5 Mots indexés par des ordres linéaires
1.6 Théor`eme de Ramsey
1.7 Définitions algébriques
2 Automates et expressions rationnelles 
2.1 Mots finis
2.1.1 Expressions rationnelles
2.1.2 Automates
2.2 Mots de longueur ω
2.2.1 Expressions rationnelles
2.2.2 Automates
2.3 Mots bi-infinis
2.3.1 Expressions rationnelles
2.3.2 Automates
2.4 Mots sur les ordinaux
2.4.1 Expressions rationnelles
2.4.2 Automates
2.4.3 Ordinaux de rang fini
2.5 Mots sur les ordres linéaires
2.5.1 Expressions rationnelles
2.5.2 Automates sur les ordres linéaires
2.5.3 Hiérarchie de langages rationnels
3 Complémentation des langages de rang fini 
3.1 Déterminisme
3.2 Complément des ensembles de rang fini
4 Equivalence algébrique 
4.1 Reconnaissabilité
4.1.1 Semigroupes
4.1.2 ω-semigroupes
4.1.3 ω1-semigroupes
4.2 Définitions algébriques
4.2.1 Idempotents
4.2.2 Relations de Green
4.2.3 Factorisations ramseyennes
4.3 Complémentation par l’approche algébrique
4.3.1 ⋄-semigroupes
4.3.2 Des automates vers les ⋄-semigroupes
4.3.3 Des ⋄-semigroupes vers les automates
4.4 ⋄-semigroupe syntaxique
5 Langages sans étoile 
5.1 Semigroupes apériodiques
5.2 Langages sans étoile
5.2.1 Mots finis
5.2.2 Mots infinis
5.2.3 Mots sur les ordinaux de rang fini
5.2.4 Mots sur les ordres linéaires
5.3 Des ⋄-semigroupes apériodiques vers les langages sans étoile
5.4 Des langages sans étoile vers les ⋄-semigroupes apériodiques

Télécharger le rapport complet