L'étoile de Kleene, parfois appelée fermeture de Kleene ou encore fermeture itérative, est, en théorie des langages, un opérateur unaire utilisé pour décrire les langages formels. Le nom étoile vient de la notation employée, un astérisque, et Kleene de Stephen Cole Kleene qui l'a introduite.
L'étoile de Kleene est l'un des trois opérateurs de base utilisés pour définir une expression rationnelle, avec la concaténation et l'union ensembliste.
Appliquée à un ensemble X {\displaystyle X} , elle a pour résultat le langage X ∗ {\displaystyle X^{*}} , défini ainsi :
Pour l'alphabet { a , b , c } {\displaystyle \{a,b,c\}} , on a
{ a , b , c } ∗ = { ε , a , b , c , a a , a b , a c , b a , b b , b c , c a , c b , c c , a a a , … } {\displaystyle \{a,b,c\}^{*}=\{\varepsilon ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,\ldots \}}Pour la partie X = { a a , b } {\displaystyle X=\{aa,b\}} composée des deux mots a a {\displaystyle aa} et b {\displaystyle b} sur l'alphabet { a , b } {\displaystyle \{a,b\}} , on obtient
{ a a , b } ∗ = { ε , b , a a , b b , a a b , b a a , b b b , a a a a , a a b b , b a a b , b b a a , b b b b , … } {\displaystyle \{aa,b\}^{*}=\{\varepsilon ,b,aa,bb,aab,baa,bbb,aaaa,aabb,baab,bbaa,bbbb,\ldots \}}On appelle étoile de Kleene d'une partie X {\displaystyle X} d'un monoïde M {\displaystyle M} le sous-monoïde engendré par X {\displaystyle X} . Ce sous-monoïde est noté X ∗ {\displaystyle X^{*}} . Comme d'usage pour les opérations de fermeture, il peut être défini de trois manières équivalentes :
Si X {\displaystyle X} est un ensemble générateur du monoïde M {\displaystyle M} , on a en particulier X ∗ = M {\displaystyle X^{*}=M} .
Dans le cas d'un alphabet A {\displaystyle A} , on note A ∗ {\displaystyle A^{*}} l'ensemble de tous les mots sur A {\displaystyle A} . L'ensemble A ∗ {\displaystyle A^{*}} est un monoïde pour la concaténation, et il est engendré par A {\displaystyle A} (pour être tout à fait rigoureux, A ∗ {\displaystyle A^{*}} est engendré par les mots composés d'une lettre, que l'on identifie avec les lettres).
Si X {\displaystyle X} est une partie de A ∗ {\displaystyle A^{*}} , alors X ∗ {\displaystyle X^{*}} est un sous-monoïde de A ∗ {\displaystyle A^{*}} qui peut être libre ou pas. Il est d'usage de noter par X n {\displaystyle X^{n}} l'ensemble
X n = { x 1 x 2 ⋯ x n ∣ x 1 , x 2 , … , x n ∈ X } {\displaystyle X^{n}=\{x_{1}x_{2}\cdots x_{n}\mid x_{1},x_{2},\ldots ,x_{n}\in X\}}de tous les produits de n {\displaystyle n} éléments de X {\displaystyle X} . On a alors la formule
X ∗ = ⋃ n ≥ 0 X n {\displaystyle X^{*}=\bigcup _{n\geq 0}X^{n}} .Si X ∗ {\displaystyle X^{*}} est un sous-monoïde librement engendré par X {\displaystyle X} , c'est-à-dire si tout mot de X ∗ {\displaystyle X^{*}} est produit, de manière unique, de mots de X {\displaystyle X} , on dit que X {\displaystyle X} est un code ou que X {\displaystyle X} est une base de X ∗ {\displaystyle X^{*}} .
Par exemple, l'ensemble X = { a a , b } {\displaystyle X=\{aa,b\}} est un code, et l'ensemble X = { a , a b , b a } {\displaystyle X=\{a,ab,ba\}} n'est pas un code parce que le mot a b a {\displaystyle aba} possède les deux factorisations
aba = ab . a = a . ba.L'opérateur plus, aussi appelé étoile propre ou étoile positive, est un opérateur analogue à l'étoile de Kleene. Il associe à une partie X {\displaystyle X} d'un demi-groupe M {\displaystyle M} le sous-demi-groupe engendré par X {\displaystyle X} , noté X + {\displaystyle X^{+}} . On a
X + = ⋃ n ≥ 1 X n {\displaystyle X^{+}=\bigcup _{n\geq 1}X^{n}} .Comme d'usage pour l'étoile, l'opérateur plus peut être défini de trois manières équivalentes:
Dans un monoïde, on a les relations suivantes entre l'étoile et l'opérateur plus:
X ∗ = X + ∪ { ε } , X + = X X ∗ = X ∗ X . {\displaystyle X^{*}=X^{+}\cup \{\varepsilon \},\ X^{+}=XX^{*}=X^{*}X.} .Les relations entre l'étoile et l'étoile positive ont fait l'objet de nombreux exposés ; l'un des plus complets est de Brzozowski, Grant et Shallit
Les deux opérations sur les langages formels que sont l'étoile (positive ou non) et le passage au complément ont des propriétés algébriques remarquables : la première est idempotente puisque ( L ∗ ) ∗ = L ∗ {\displaystyle (L^{*})^{*}=L^{*}} pour tout langage L {\displaystyle L} et la deuxième est involutive puisque en effet le complément du complément d'un langage est le langage de départ.
La répétition de ces deux opérations, à partir d'un langage L {\displaystyle L} donné, ne produit pas une infinité de langages, mais un nombre fini. Ce phénomène, constaté par David Peleg en 1984 est à mettre en relation avec un résultat de topologie déjà ancien de Kuratowski, le théorème de fermeture/complémentaire de Kuratowski.
Pour démontrer l'assertion, on considère donc les deux opérations
L ↦ L ∗ {\displaystyle L\mapsto L^{*}} et L ↦ L − {\displaystyle L\mapsto L^{-}}d'étoile et de complémentation. Ces opérations sont écrites en notation postfixée. On a en particulier
L ∗ ∗ = L ∗ {\displaystyle L^{**}=L^{*}} (idempotence) et L − − = L {\displaystyle L^{--}=L} (involution).Une suite d'opération peut donc toujours être simplifiée en remplaçant des opérations successives égales, et on est ramené à une alternance d'étoiles et de complémentations. La proposition découle de l'identité
L ∗ − ∗ − ∗ − ∗ = L ∗ − ∗ {\displaystyle L^{*-*-*-*}=L^{*-*}}qui dit qu'une suite de 8 opérations peut être remplacée par une suite de 4 opérations seulement (en tenant compte du fait qu'une suite peut commencer ou se terminer par une complémentation).
DémonstrationPour démontrer cette formule, on montre d'abord l'inclusion
L ∗ − ∗ − ∗ ⊆ L ∗ ( 1 ) {\displaystyle L^{*-*-*}\subseteq L^{*}\qquad (1)} .Cette inclusion s'obtient en partant de
L ∗ − ⊆ L ∗ − ∗ {\displaystyle L^{*-}\subseteq L^{*-*}} ,puis, en passant au complémentaire :
L ∗ − − = L ∗ ⊇ L ∗ − ∗ − {\displaystyle L^{*--}=L^{*}\supseteq L^{*-*-}} ,et enfin, en appliquant l'étoile
L ∗ ∗ = L ∗ ⊇ L ∗ − ∗ − ∗ {\displaystyle L^{**}=L^{*}\supseteq L^{*-*-*}} .L'équation (1) donne, en appliquant le complément puis l'étoile :
L ∗ − ∗ − ∗ − ∗ ⊇ L ∗ − ∗ {\displaystyle L^{*-*-*-*}\supseteq L^{*-*}} .D'autre part, en substituant L ∗ − {\displaystyle L^{*-}} à L {\displaystyle L} dans l'équation (1), on obtient :
L ∗ − ∗ − ∗ − ∗ ⊆ L ∗ − ∗ {\displaystyle L^{*-*-*-*}\subseteq L^{*-*}} .Les deux inégalités donnent le résultat cherché.
Des extensions sont présentées dans l'article de Brzozowski, Grant et Shallit déjà cité.
Les langages rationnels ou réguliers sont décrits par des expressions régulières, où l'étoile de Kleene intervient de manière essentielle : c'est elle qui fait passer aux langages infinis. La construction correspondante sur les automates finis déterministes passe par une étape intermédiaire utilisant un automate fini non déterministe. Si l'automate minimal reconnaissant un langage L {\displaystyle L} a n {\displaystyle n} états, l'automate fini déterministe minimal reconnaissant L ∗ {\displaystyle L^{*}} peut avoir, en principe, jusqu'à 2 n {\displaystyle 2^{n}} états. Or on sait depuis longtemps que ce nombre d'états est au plus 3 / 4 ⋅ 2 n {\displaystyle 3/4\cdot 2^{n}} , et même, plus précisément, au plus 2 n − 1 + 2 n − 1 − k {\displaystyle 2^{n-1}+2^{n-1-k}} , où k {\displaystyle k} est le nombre d'états terminaux qui ne sont pas état initial. Tout un ensemble de valeurs intermédiaires sont possibles.
La famille des langages formels obtenue, à partir des langages qui sont l'étoile d'un mot, par les opérations de fermeture booléenne est une famille assez restreinte. Elle admet une caractérisation équationnelle effective, ce qui permet de décider si un langage donné appartient à cette famille.