Étoile de Kleene

Pour l'alphabet ${\displaystyle \{a,b,c\}}$, on a

${\displaystyle \{a,b,c\}^{*}=\{\varepsilon ,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,\ldots \}}$

Pour la partie ${\displaystyle X=\{aa,b\}}$ composée des deux mots ${\displaystyle aa}$ et ${\displaystyle b}$ sur l'alphabet ${\displaystyle \{a,b\}}$, on obtient

${\displaystyle \{aa,b\}^{*}=\{\varepsilon ,b,aa,bb,aab,baa,bbb,aaaa,aabb,baab,bbaa,bbbb,\ldots \}}$

On appelle étoile de Kleene d'une partie ${\displaystyle X}$ d'un monoïde ${\displaystyle M}$ le sous-monoïde engendré par ${\displaystyle X}$. Ce sous-monoïde est noté ${\displaystyle X^{*}}$. Comme d'usage pour les opérations de fermeture, il peut être défini de trois manières équivalentes :

• ${\displaystyle X^{*}}$ est la plus petite partie de ${\displaystyle M}$ contenant ${\displaystyle X}$ et l'élément neutre de ${\displaystyle M}$ et fermée pour l'opération de ${\displaystyle M}$.
• ${\displaystyle X^{*}}$ est l'intersection de tous les sous-monoïdes de ${\displaystyle M}$ contenant ${\displaystyle X}$.
• ${\displaystyle X^{*}}$ est l'ensemble de tous les produits de la forme ${\displaystyle x_{1}x_{2}\cdots x_{n}}$, pour ${\displaystyle n\geq 0}$ et ${\displaystyle x_{1},x_{2},\ldots ,x_{n}\in X}$.

Si ${\displaystyle X}$ est un ensemble générateur du monoïde ${\displaystyle M}$ , on a en particulier ${\displaystyle X^{*}=M}$.

Dans le cas d'un alphabet ${\displaystyle A}$, on note ${\displaystyle A^{*}}$ l'ensemble de tous les mots sur ${\displaystyle A}$. L'ensemble ${\displaystyle A^{*}}$ est un monoïde pour la concaténation, et il est engendré par ${\displaystyle A}$ (pour être tout à fait rigoureux, ${\displaystyle A^{*}}$ est engendré par les mots composés d'une lettre, que l'on identifie avec les lettres).

Si ${\displaystyle X}$ est une partie de ${\displaystyle A^{*}}$, alors ${\displaystyle X^{*}}$ est un sous-monoïde de ${\displaystyle A^{*}}$ qui peut être libre ou pas. Il est d'usage de noter par ${\displaystyle X^{n}}$ l'ensemble

${\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 ${\displaystyle n}$ éléments de ${\displaystyle X}$. On a alors la formule

${\displaystyle X^{*}=\bigcup _{n\geq 0}X^{n}}$.

Si ${\displaystyle X^{*}}$ est un sous-monoïde librement engendré par ${\displaystyle X}$, c'est-à-dire si tout mot de ${\displaystyle X^{*}}$ est produit, de manière unique, de mots de ${\displaystyle X}$, on dit que ${\displaystyle X}$ est un code ou que ${\displaystyle X}$ est une base de ${\displaystyle X^{*}}$.

Par exemple, l'ensemble ${\displaystyle X=\{aa,b\}}$ est un code, et l'ensemble ${\displaystyle X=\{a,ab,ba\}}$ n'est pas un code parce que le mot ${\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 ${\displaystyle X}$ d'un demi-groupe ${\displaystyle M}$ le sous-demi-groupe engendré par ${\displaystyle X}$, noté ${\displaystyle X^{+}}$. On a

${\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:

• ${\displaystyle X^{+}}$ est la plus petite partie de ${\displaystyle M}$ contenant ${\displaystyle X}$ et fermée pour l'opération de ${\displaystyle M}$.
• ${\displaystyle X^{+}}$ est l'intersection de tous les sous-demi-groupes de ${\displaystyle M}$ contenant ${\displaystyle X}$.
• ${\displaystyle X^{+}}$ est l'ensemble de tous les produits de la forme ${\displaystyle x_{1}x_{2}\cdots x_{n}}$, pour ${\displaystyle n>0}$ et ${\displaystyle x_{1},x_{2},\ldots ,x_{n}\in X}$.

Dans un monoïde, on a les relations suivantes entre l'étoile et l'opérateur plus:

${\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[1]

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 ${\displaystyle (L^{*})^{*}=L^{*}}$ pour tout langage ${\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 ${\displaystyle L}$ donné, ne produit pas une infinité de langages, mais un nombre fini. Ce phénomène, constaté par David Peleg en 1984[2] 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

${\displaystyle L\mapsto L^{*}}$ et ${\displaystyle L\mapsto L^{-}}$

d'étoile et de complémentation. Ces opérations sont écrites en notation postfixée. On a en particulier

${\displaystyle L^{**}=L^{*}}$ (idempotence) et ${\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é

${\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).

Des extensions sont présentées dans l'article de Brzozowski, Grant et Shallit[1] 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 ${\displaystyle L}$ a ${\displaystyle n}$ états, l'automate fini déterministe minimal reconnaissant ${\displaystyle L^{*}}$ peut avoir, en principe, jusqu'à ${\displaystyle 2^{n}}$ états. Or on sait depuis longtemps que ce nombre d'états est au plus ${\displaystyle 3/4\cdot 2^{n}}$, et même, plus précisément, au plus ${\displaystyle 2^{n-1}+2^{n-1-k}}$, où ${\displaystyle k}$ est le nombre d'états terminaux qui ne sont pas état initial. Tout un ensemble de valeurs intermédiaires sont possibles[4].

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[5].

• (en) Stephen C. Kleene, « Representation of events in nerve nets and finite automata », dans Claude E. Shannon et John McCarthy (éditeurs), Automata Studies, Princeton, Princeton University Press, coll. « Annals of Mathematics Studies » (n^o 34), 1956, viii+285 (ISBN 978-0691079165), p. 3-41
• Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs), Encyclopédie de l'informatique et des systèmes d'information, Paris, Vuibert, 2006, xxxv+1941 (ISBN 978-2-7117-4846-4)
• Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, présentation en ligne)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)

• Algèbre de Kleene
• Forme de Backus-Naur étendue