Étoile de Kleene

opérateur unaire utilisé pour décrire les langages formels

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 , elle a pour résultat le langage , défini ainsi :

  1. Si est un alphabet, c'est-à-dire un ensemble de symboles ou caractères, alors est l'ensemble des mots sur , mot vide inclus.
  2. Si est un langage, alors est le plus petit langage qui le contienne, qui contienne et qui soit stable par concaténation.

Exemples

modifier

Pour l'alphabet  , on a

 

Pour la partie   composée des deux mots   et   sur l'alphabet  , on obtient

 

Définition

modifier

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

  •   est la plus petite partie de   contenant   et l'élément neutre de   et fermée pour l'opération de  .
  •   est l'intersection de tous les sous-monoïdes de   contenant  .
  •   est l'ensemble de tous les produits de la forme  , pour   et  .

Si   est un ensemble générateur du monoïde   , on a en particulier  .

Cas du monoïde libre

modifier

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

Si   est une partie de  , alors   est un sous-monoïde de   qui peut être libre ou pas. Il est d'usage de noter par   l'ensemble

 

de tous les produits de   éléments de  . On a alors la formule

 .

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

Par exemple, l'ensemble   est un code, et l'ensemble   n'est pas un code parce que le mot   possède les deux factorisations

aba = ab . a = a . ba.

Opérateur plus

modifier

L'opérateur plus, aussi appelé étoile propre ou étoile positive, est un opérateur analogue à l'étoile de Kleene. Il associe à une partie   d'un demi-groupe   le sous-demi-groupe engendré par  , noté  . On a

 .

Comme d'usage pour l'étoile, l'opérateur plus peut être défini de trois manières équivalentes:

  •   est la plus petite partie de   contenant   et fermée pour l'opération de  .
  •   est l'intersection de tous les sous-demi-groupes de   contenant  .
  •   est l'ensemble de tous les produits de la forme  , pour   et  .

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

 .

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

modifier

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   pour tout langage   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   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

  et  

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

  (idempotence) et   (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é

 

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

Cas des langages rationnels

modifier

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   a   états, l'automate fini déterministe minimal reconnaissant   peut avoir, en principe, jusqu'à   états. Or on sait depuis longtemps que ce nombre d'états est au plus  , et même, plus précisément, au plus  , où   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

modifier

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

modifier
  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, no 02,‎ , p. 301–321 (ISSN 0129-0541, DOI 10.1142/S0129054111008052, arXiv 0901.3761)
  2. David Peleg, « A generalized closure and complement phenomenon », Discrete Mathematics, vol. 50,‎ , 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,‎ , p. 251–261 (DOI 10.1051/ita/2016024).
  5. Laure Daviaud et Charles Paperman, « Classes of languages generated by the Kleene star of a word », Information and Computation, vol. 262,‎ , p. 90–109 (ISSN 0890-5401, DOI 10.1016/j.ic.2018.07.002).

Bibliographie

modifier
  • (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 » (no 34), , 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, , 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, , 237 p. (ISBN 978-2-7117-2077-4, présentation en ligne)
  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, , 816 p. (ISBN 978-2-7117-4807-5)

Voir aussi

modifier