Étoile de Kleene

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$ , elle a pour résultat le langage $X^{*}$ , défini ainsi :

Si $X$ est un alphabet, c'est-à-dire un ensemble de symboles ou caractères, alors $X^{*}$ est l'ensemble des mots sur $X$ , mot vide $\varepsilon$ inclus.
Si $X$ est un langage, alors $X^{*}$ est le plus petit langage qui le contienne, qui contienne $\varepsilon$ et qui soit stable par concaténation.

Exemples

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

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

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

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

Définition

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

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

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

Cas du monoïde libre

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

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

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

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

.

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

Par exemple, l'ensemble $X=\{aa,b\}$ est un code, et l'ensemble $X=\{a,ab,ba\}$ n'est pas un code parce que le mot $aba$ possède les deux factorisations

aba = ab . a = a . ba.

Opérateur plus

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$ d'un demi-groupe $M$ le sous-demi-groupe engendré par $X$ , noté $X^{+}$ . On a

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:

$X^{+}$ est la plus petite partie de $M$ contenant $X$ et fermée pour l'opération de $M$ .
$X^{+}$ est l'intersection de tous les sous-demi-groupes de $M$ contenant $X$ .
$X^{+}$ est l'ensemble de tous les produits de la forme $x_{1}x_{2}\cdots x_{n}$ , pour $n>0$ et $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:

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]

Répétition de l'étoile et de la complémentation

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^{*}$ pour tout langage $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$ 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

L\mapsto L^{*}

et

L\mapsto L^{-}

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

L^{**}=L^{*}

(idempotence) et

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^{*-*}

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émonstration

Pour démontrer cette formule^[3], on montre d'abord l'inclusion

L^{*-*-*}\subseteq L^{*}\qquad (1)

.

Cette inclusion s'obtient en partant de

L^{*-}\subseteq L^{*-*}

,

puis, en passant au complémentaire :

L^{*--}=L^{*}\supseteq L^{*-*-}

,

et enfin, en appliquant l'étoile

L^{**}=L^{*}\supseteq L^{*-*-*}

.

L'équation (1) donne, en appliquant le complément puis l'étoile :

L^{*-*-*-*}\supseteq L^{*-*}

.

D'autre part, en substituant $L^{*-}$ à $L$ dans l'équation (1), on obtient :

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^[1] déjà cité.

Cas des langages rationnels

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

Étoile d'un mot

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

Notes et références

↑ ^{a et b} Janusz Brzozowski, Elyot Grant et Jeffrey Shallit, « Closures in formal languages and Kuratowski's theorem », International Journal of Foundations of Computer Science, vol. 22, n^o 02,‎ 2011, p. 301–321 (ISSN 0129-0541, DOI 10.1142/S0129054111008052, arXiv 0901.3761)
↑ David Peleg, « A generalized closure and complement phenomenon », Discrete Mathematics, vol. 50,‎ 1984, p. 285–293 (ISSN 0012-365X, DOI 10.1016/0012-365X(84)90055-4, lire en ligne).
↑ Peleg 1984, Lemma 3.1.
↑ Matúš Palmovský, « Kleene closure and state complexity », RAIRO-Theor. Inf. Appl., vol. 50,‎ 2016, p. 251–261 (DOI 10.1051/ita/2016024).
↑ Laure Daviaud et Charles Paperman, « Classes of languages generated by the Kleene star of a word », Information and Computation, vol. 262,‎ 2018, p. 90–109 (ISSN 0890-5401, DOI 10.1016/j.ic.2018.07.002).

Bibliographie

(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)

Voir aussi

[BrzozowskiGrant2011-1] {a et b} Janusz Brzozowski, Elyot Grant et Jeffrey Shallit, « Closures in formal languages and Kuratowski's theorem », International Journal of Foundations of Computer Science, vol. 22, n^o 02,‎ 2011, p. 301–321 (ISSN 0129-0541, DOI 10.1142/S0129054111008052, arXiv 0901.3761)

[Peleg1984-2] David Peleg, « A generalized closure and complement phenomenon », Discrete Mathematics, vol. 50,‎ 1984, p. 285–293 (ISSN 0012-365X, DOI 10.1016/0012-365X(84)90055-4, lire en ligne).

[3] Peleg 1984, Lemma 3.1.

[4] Matúš Palmovský, « Kleene closure and state complexity », RAIRO-Theor. Inf. Appl., vol. 50,‎ 2016, p. 251–261 (DOI 10.1051/ita/2016024).

[DaviaudPaperman2018-5] Laure Daviaud et Charles Paperman, « Classes of languages generated by the Kleene star of a word », Information and Computation, vol. 262,‎ 2018, p. 90–109 (ISSN 0890-5401, DOI 10.1016/j.ic.2018.07.002).

[1]

[2]

[3]

[4]

[5]