Langages sans ´etoile

Langages sans étoile

L’approche algébrique est un outil puissant pour l’étude des ensembles rationnels. Contrairement `a la théorie des automates, elle permet d’associer un objet canonique `a chaque ensemble rationnel : le semigroupe syntaxique. Les chapitres précédents ont montré qu’un ensemble est rationnel si et seulement si sonsemigroupe syntaxique est fini. Dans le cas des mots finis, l’étude des propriétésalgébriques des semigroupes syntaxiques a permis d’établir toute une hiérarchiedes ensembles rationnels. Sch¨utzenberger fˆut le premier `a considérer les ensembles dont les semigroupes syntaxiques sont finis et apériodiques, c’est-`a-direne contenant pas de groupes. Il a montré que ces ensembles étaient exactementles langages sans étoile [38], définis par des expressions rationnelles n’utilisantque les opérations booléennes et le produit fini. Cette classe est importante d’unpoint de vue logique puisqu’elle contient exactement les ensembles définissablespar des formules logiques du premier ordre [24]. Ces résultats ont été étendusaux mots de longueur ω par Ladner [22], Thomas [41] et Perrin [29] et mˆemeaux mots ordinaux par Bedon [5]. Etant donné un entier n, les ensembles sansétoile de mots indexés par des ordres linéaires dispersés de rang inférieur ou égal`a n, sont construits `a partir des lettres de l’alphabet en utilisant le produit finiet les opérations booléennes o`u le complément est pris dans l’ensemble des motsnon vides de rang au plus n. Dans ce chapitre, on montre que le ⋄-semigroupe

syntaxique d’un ensemble X de rang fini n est apériodique et fini si et seulement si X est sans étoile dans l’ensemble des mots de rang au plus n. Pourmontrer que le semigroupe syntaxique d’un ensemble sans étoile de rang fini estapériodique, le produit de Sch¨utzenberger est généralisé aux ⋄-semigroupes. Lapreuve de la réciproque, inspirée de [4], utilise une induction sur le rang et n’estdonc pas adaptable aux ordres linéaires de rang quelconque.

Semigroupes apériodiques

Définition 25 Un semigroupe S est apériodique s’il existe un entier k tel quepour tout s appartenant `a S, sk+1 = skLangages sans étoileUn ⋄-semigroupe (respectivement ω-semigroupe, ω1-semigroupe) est apériodiquesi son semigroupe de support est apériodique.

Langages sans étoile

Un ensemble sans étoile est défini par une expression rationnelle o`u l’opérateur∗ est interdit mais dans laquelle la complémentation peut ˆetre utilisée. Nous rappelons les définitions des langagessans étoile de mots finis, infinis et ordinauxde rang fini avant de les généraliser aux mots sur les ordres linéaires dispersésde rang fini.

Mots finis

Définition 26 La classe SF(A∗) des ensembles sans étoile de mots finis est laplus petite famille contenant l’ensemble P(A) des parties de A et fermée parproduit fini et par les opérations booléennes o`u la complémentation est prisepar rapport `a A∗Notons que l’ensemble vide est sans étoile et son complémentaire A∗ aussi.Exemple 61 L’ensemble (ab)+ est sans étoile puisqu’il est défini par l’expression (aA∗ ∩ A∗b) \ (A+aaA+ ∪ A+bbA+).Théor`eme 61 (Sch¨utzenberger) [38] Un ensemble de mots finis est sansétoile si et seulement si son semigroupe syntaxique est apériodique et fini.Exemple 62 Le semigroupe syntaxique de l’ensemble (ab)

Mots infinis

Pour les mots de longueur ω, le produit fini n’est autorisé que du coté gauche.Définition 27 La classe SF(Aω) des ensembles sans étoile de Aω est la pluspetite famille contenant P(A) et fermée par les opérations booléennes o`u lacomplémentation est prise par rapport `a Aω, et fermée par produit fini `a gauchedes ensembles sans étoile de A∗De mˆeme que A∗ appartient `a SF(A∗), l’ensemble Aω appartient `a SF(Aω) en tant que complémentaire de l’ensemble vide.Exemple 63 L’ensemble (ab)ω est sans étoile : (ab)ω = aAω \ (A∗aaAω ∪A∗bbAω).Théor`eme 62 (Perrin) [29] Un ensemble de mots de longueur ω est sansétoile si et seulement si son semigroupe syntaxique est apériodique et fini.Mots sur les ordinaux de rang finiPour tout entier n, notons A<ωn l’ensemble des mots non vide sur A indexéspar un ordinal strictement inférieur `a ωn.Définition 28 Soit n un entier naturel. La classe SF(A<ωn+1) des ensemblessans étoile de mots indexés par des ordinaux inférieur `a ωn+1 est la plus petite famille contenant l’ensemble P(A) des parties de A et fermée par les opérations booléennes o`u la complémentation est prise par rapport `a A<ωn+1 , et fermée par produit fini.Exemple 64 L’ensemble X = ((ab)+ + (ab)ω)+ appartient `a SF(A<ω2 ). En effet, en notant L= A<ω2\ A<ω2 A l’ensemble des mots de A<ω2 de longueurlimite, il vientX = abA<ω2\ (LbA<ω2+ A<ω2a + A<ω2aaA<ω2+ A<ω2bbA<ω2).Théor`eme 63 (Bedon) [6] Un ensemble de mots indexés par des ordinauxde rang fini est sans étoile si et seulement si son semigroupe syntaxique estapériodique et fini.La preuve de ce théor`eme utilise une approche logique et montre également queles langages sans étoile de mots transfinis sont définis par des formules logiquesdu premier ordre.

Mots sur les ordres linéaires

Définition 29 Soit A un alphabet fini et soit n un entier naturel. La classe SFn(A) (ou SFn) des ensembles sans étoile de rang au plus n est le plus petitensemble contenant P(A) des parties de A et fermé par produit fini et par lesopérations booléennes o`u le complément est pris par rapport `a l’ensemble AWn .Bien sˆur, l’ensemble AWn appartient `a SFn puisque c’est le complément de∅ ∈ SFn.Exemple 65 Pour tout entier naturel n, les ensembles G et D de mots de rangau plus n et de longueur limite `a gauche et `a droite sont sans étoile :G = AWn \ AAWn , D = A Wn \ AWn A.L’ensemble A∗ des mots finis appartient aussi `a SFn : c’est l’ensemble des motsne contenant aucun facteur de longueur limite :A∗ = AWn \ AWn (G ∪ D)AWn= AWn \ (AWn (G ∪ D)AWn ∪ GAWn ∪ AWn D).Lemme 64 Quels que soient les entiers naturels n et k < n, les ensemblesAWk , (AWk )ω et (AWk )−ω appartiennent `a SFn.Preuve. Soit n ∈ N. L’exemple 65 montre déj`a que A∗ ∈ SFn. On montre que pour tout 0 ≤ k < n, si AWk ∈ SFn, alors (AWk )ω,(AWk )−ω et AWk+1 appartiennent `a SFn. Soit 0 ≤ k < n. Supposons AWk ∈ SFn. Son complémentAWk = AWn \AWk appartient donc aussi `a SFn. On montre que (AWk )ω ∈ SFnen utilisant l’expression sans étoile suivante :(AWk)ω = AWk \ (AWk AWk ∪ AWk AWk)L’inclusion de gauche `a droite est directe. Réciproquement, soit x appartenantau membre droit de l’égalité. Comme x ∈ AWn \AWk , il existe un entier k < r ≤n tel que |x| ∈ Wr \Wr−1. Notons |x| =Pmi=1Ki o`u Ki ∈ Ur pour tout 1 ≤ i ≤ m.Comme x ∈ AWk \ AWk AWk , il existe un unique entier 1 ≤ i0 ≤ m tel queKi0 ∈ Ur \ Wk. De plus, i0 = m puisque x ∈ AWk \ AWk AWk . On sait donc quex admet une factorisation x = x′x′′ o`u |x′| ∈ Wk et |x′′| ∈ Ur \Wk. Par définitionde Ur, |x′′| =Pj∈JIj o`u pour tout j ∈ J,Ij ∈ Wr−1 et o`u J ∈ N ∪ {ω, −ω}. SiJ ∈ N alors |x| ∈ Wr−1 ce qui est une contradiction. Donc J ∈ {ω, −ω}. Parl’absurde, supposons qu’il existe j0 ∈ J tel que Ij0 ∈ Wr−1 \ Wk. si J = ω alorsles ordres linéaires Pj≤j0Ij et Pj0<jIj appartiennent tous les deux `a Wr−1 \ Wk.Cela signifierait que x ∈ AWk AWk ce qui est une contradiction. L’argumentsymétrique pour J = −ω montre que x′′ ∈ (AWk )ω ou que x′′ ∈ (AWk )−ω.