Ouvrir le menu principal

En informatique théorique, et plus précisément en théorie des automates, le théorème de Kleene affirme qu'un langage est rationnel (i.e. décrit par une expression rationnelle) si et seulement s’il est reconnu par un automate fini. C'est un théorème fondamental de la théorie des langages formels et des automates. La première formulation de ce théorème est due au mathématicien Stephen C. Kleene[réf. nécessaire].

Sommaire

HistoriqueModifier

Le début des automates finis, et notamment la genèse du théorème de Kleene a été décrite par Dominique Perrin[1]. La première mention des automates finis remonte à un article McCulloch et Pitts en 1943[2]. C'est Stephen Kleene qui reprend cet article en 1956, et présente la première preuve de son théorème[3]. Le premier exposé complet est donné par Rabin et Scott en 1959[4].

Formulation contemporaineModifier

Depuis le traité d'Eilenberg[5], le théorème de Kleene est formulé de façon plus concise comme suit.

L'ensemble des langages rationnels sur un alphabet   est par définition le plus petit ensemble de parties de   contenant les singletons (parties réduites à un seul élément) et l'ensemble vide, et fermé par les opérations d'union, produit et étoile. Cet ensemble est noté  .

On appelle langage reconnaissable sur un alphabet   tout langage qui peut être reconnu par un automate fini sur  . L'ensemble des langages reconnaissables est noté  .

Le théorème de Kleene s'énonce alors comme suit.

Théorème de Kleene — Sur un alphabet fini  , il y a égalité entre langages rationnels et langages reconnaissables. En d'autres termes, on a

 

DémonstrationsModifier

De nombreuses variantes de démonstrations de ce théorème existent[6]. La plupart des preuves sont constructives, c'est-à-dire que l'on donne des algorithmes qui calculent un automate à partir d'une expression rationnelle, et une expression rationnelle à partir d'un automate.

Inclusion  Modifier

Les applications pratiques ont suscité un intérêt pour le développement d'algorithmes efficaces pour réaliser les constructions qui interviennent dans la preuve.

Inclusion  Modifier

Il s'agit de donner une expression rationnelle pour le langage reconnu par un automate fini. Trois algorithmes sont courants :

Toutes ces méthodes sont des méthodes d'élimination d'états.

Généralisations et extensionsModifier

Théorème de Kleene-SchützenbergerModifier

On doit au mathématicien Marcel-Paul Schützenberger l'extension du théorème de Kleene aux séries formelles (respectivement aux automates pondérés). Le théorème affirme qu'une série formelle en variables non commutatives à coefficients dans un demi-anneau est rationnelle si et seulement si elle est reconnue par un automate fini pondéré, dont les poids respectifs des étiquettes sont des éléments de ce demi-anneau[7].

Extensions aux monoïdesModifier

Le théorème de Kleene a fait l'objet de tentatives d'extension aux monoïdes généraux, pas nécessairement libres. Étant donné un monoïde  , les parties rationnelles de   sont la plus petite famille de parties de   contenant les singletons et l'ensemble vide, et fermée par union, produit et passage au sous-monoïde engendré (l'analogue de l'étoile de Kleene dans les monoïdes). On note   l'ensemble des parties rationnelles de  .

Il convient d'exprimer de façon plus algébrique la notion de partie reconnaissable d'un monoïde. Une partie   d'un monoïde   est une partie reconnaissable de   si elle est saturée par une congruence d'index fini, en d'autres termes s'il existe un monoïde fini  , et un morphisme surjectif   tel que  , où  . On note   l'ensemble des parties reconnaissables de  .

Avec ces définitions, l'égalité   est par exemple vraie dans les monoïdes finis. McKnight a prouvé que si   est un monoïde finiment engendré, alors  . L'égalité n'est pas vraie en général. En particulier, dans le produit de deux monoïdes libres, les parties rationnelles sont les transductions rationnelles, alors que les parties reconnaissables sont, d'après un théorème de Mezei, des unions finies de produits de parties reconnaissables des deux monoïdes composants[6].

Le cas des groupesModifier

Un sous-groupe   d'un groupe   est une partie reconnaissable de   si et seulement s'il est d'index fini.

Un sous-groupe   d'un groupe   est une partie rationnelle de   si et seulement s'il est finiment engendré.

Si   lui-même est finiment engendré, le théorème de McKnight cité plus haut implique que tout sous-groupe d'index fini est finiment engendré, un résultat habituellement attribué à Howson.

Théorèmes de Kleene pour les monoïdes partiellement commutatifsModifier

Le théorème de Kleene reste valide, sous réserve d'une restriction de l'étoile de Kleene, dans les monoïdes des traces ou monoïdes partiellement commutatifs libres[8].

Soit   un alphabet. Une relation d'indépendance ou relation de commutation   est une partie   de   qui est irréflexive et symétrique. Une relation d'indépendance   définit une relation de dépendance réflexive et symétrique   par  , et réciproquement.

Une relation d'indépendance induit une relation binaire   sur  , où   si et seulement si   et   pour des mots   et une paire  . On note   est la fermeture réflexive, symétrique et transitive de  . Le monoïde des traces est le monoïde quotient de  . Les éléments de   sont des traces. Pour un mot ou une trace  , on note   l'ensemble des lettres qui apparaissent dans  . Deux traces   et   sont indépendantes si toute lettre de   commute avec toute lettre de  . Une trace   est connexe si   induit un sous-graphe dont les sommets sont les lettres et les arêtes sont les éléments de  .

L'étoile de Kleene concurrente (concurrent star en anglais) d'une partie   de   est l'ensemble  , où   est l'ensemble des traces connexes non vides qui commutent avec une trace de  . Notons   le plus petit ensemble de parties de   contenant les singletons et l'ensemble vide, et fermé par les opérations d'union, produit et l'étoile de Kleene concurrente. On a alors l'égalité suivante, due à Ochmański :

 

NotesModifier

ArticlesModifier

  • (en) Warren S. McCulloch et Walter Pitts, « A logical calculus of the ideas immanent in nervous activity », Bull. Math. Biophys., vol. 5,‎ , p. 115-133
  • (en) Stephen C. Kleene, « Representation of events in nerve nets and finite automata. Automata studies », Annals of Mathematics Studies, Princeton University Press, no 34,‎ , p. 3-41
  • Dominique Perrin, « Les débuts de la théorie des automates », Technique et science informatiques, vol. 14, no 4,‎ , p. 409-433 (lire en ligne)
  • (en) Michael O. Rabin et Dana Scott, « Finite automata and their decision problems », IBM J. Res. Develop., vol. 3,‎ , p. 114-125

BibliographieModifier

  • (en) Volker Diekert et Yves Métivier, « Partial Commutation and Traces », dans G. Rozenberg, A. Salomaa (éditeurs), Handbook of Formal Languages, vol. 3 : Beyond Words, Springer Verlag, (ISBN 978-3-5406-0649-9)
  • (en) Manfred Droste, Werner Kuich et Heiko Vogler, Handbook of Weighted Automata, Springer-Verlag, (ISBN 978-3-64201491-8)
  • (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, (ISBN 978-0-12234001-7)
  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, (ISBN 978-2-7117-4807-5)
    Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 978-0-52184425-3)

Articles connexesModifier