Théorème de Kleene

Théorème de Kleene
Page d'aide sur l'homonymie Ne doit pas être confondu avec Théorème de récursion de Kleene ni Théorème du point fixe de Kleene.

En informatique théorique, et plus précisément en théorie des automates, le théorème de Kleene affirme qu'un langage peut être décrit par une expression rationnelle (c'est-à-dire est rationnel) 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.

Sommaire

Historique

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 contemporaine

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 A est par définition le plus petit ensemble de parties de A * 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é Rat A * .

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

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

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

Rat A * = Rec A *

Démonstrations

De nombreuses variantes de démonstrations de ce théorème existent[6]. La plupart des preuves sont constructives, et montrent les deux inclusions \text{Rat } A^* \subset \text{Rec } A^* et \text{Rat } A^* \supset \text{Rec } A^*.

\text{Rat } A^* \subset \text{Rec } A^*.

Récemment, 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.

\text{Rec } A^* \subset \text{Rat } A^*.

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

  • L'algorithme de McNaughton et Yamada : on calcule par itération les langages reconnus dont les chemins n'utilisent que certains états.
  • L'algorithme de Conway : on calcule la matrice des langages reconnus par partition
  • L'algorithme d'élimination ou algorithme de Brzozowski et McCluskey (en) : on élimine les états, et on remplace les étiquettes par des expression rationnelles.

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

Généralisations et extensions

Théorème de Kleene-Schützenberger

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ées). 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 des étiquettes sont des éléments de ce demi-anneau [7].

Extensions aux monoïdes

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 M, les parties rationnelles de M sont la plus petite famille de parties de M 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 Rat M l'ensemble des parties rationnelles de M.

Il convient d'exprimer de façon plus algébrique la notion de partie reconnaissable d'un monoïde. Une partie H d'un monoïde M est une partie reconnaissable de M si elle est saturée par une congruence d'index fini, en d'autres termes s'il existe un monoïde fini N, et un morphisme surjectif f:M\to N tel que H = f − 1(K), où H = f(H). On note Rec M l'ensemble des parties reconnaissables de M.

Avec ces définitions, l'égalité Rec M = Rat M est par exemple vraie dans les monoïdes finis. McKnight a prouvé que si M est un monoïde finiment engendré, alors \text{Rec } M\subset \text{Rat } M. 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 groupes

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

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

Si G 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 commutatifs

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 (en) ou monoïdes partiellement commutatifs libres[8].

Soit A un alphabet. Une relation d'indépendance ou relation de commutation I est une partie I de A\times A qui est irréflexive et symétrique. Un relation d'indépendance I définit une relation de dépendance réflexive et symétrique D par D=A\times A\setminus I, et réciproquement.

Une relation d'indépendance induit une relation binaire ∼ sur A * , où u∼v si et seulement si u = xaby et v = xbay pour des mots x,y\in A^* et une paire (a,b)\in I. On note \equiv est la fermeture réflexive, symétrique et transitive de ∼. Le monoïde des traces est le monoïde quotient de A^*/{\equiv}. Les éléments de A^*/{\equiv} sont des traces. Pour un mot ou une trace w, on note alph(w) l'ensemble des lettres qui apparaissent dans w. Deux traces u et v sont indépendantes si toute lettre de u commute avec toute lettre de v. Une trace u est connexe si alph(u) induit un sous-graphe dont les sommets sont les lettres et les arêtes sont les éléments de D.

L'étoile de Kleene concurrente (concurrent star en anglais) d'une partie X de A^*/{\equiv} est l'ensemble (c(X)) * , où c(X) est l'ensemble des traces connexes non vides qui commutent avec une trace de X. Notons \text{Rat}^c (A^*/{\equiv}) le plus petit ensemble de parties de A^*/{\equiv} 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:

\text{Rat}^c (A^*/{\equiv})\ =\ \text{Rec} (A^*/{\equiv}).

Notes

Articles

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

Bibliographie

  • (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, 1997 (ISBN 978-3-5406-0649-9) 
  • (en) Manfred Droste, Werner Kuich et Heiko Vogler, Handbook of Weighted Automata, Springer-Verlag, 2009 (ISBN 978-3-64201491-8) 
  • (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, 1974 (ISBN 978-0-12234001-7) 
  • (en) John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Prentice Hall, 2007, 3e éd. (ISBN 978-0-32146225-1) 
  • Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (ISBN 978-2-7117-4807-5).
    Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 978-0-52184425-3)
     

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Théorème de Kleene de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Theoreme de Kleene — Théorème de Kleene En théorie des automates, le théorème de Kleene affirme qu un langage est rationnel si et seulement s’il est reconnu par un automate fini. Ce théorème est dû à Stephen Kleene. C est un théorème essentiel des langages formels,… …   Wikipédia en Français

  • Théorème de kleene — En théorie des automates, le théorème de Kleene affirme qu un langage est rationnel si et seulement s’il est reconnu par un automate fini. Ce théorème est dû à Stephen Kleene. C est un théorème essentiel des langages formels, puisqu il fait le… …   Wikipédia en Français

  • Théorème de récursion de Kleene —  Ne doit pas être confondu avec Théorème de Kleene ni Théorème du point fixe de Kleene. En théorie de la calculabilité plusieurs théorèmes dus à à Kleene sont appelés théorèmes de la récursion. Ils établissent l existence de points fixes… …   Wikipédia en Français

  • Théorème du point fixe de Kleene —  Ne doit pas être confondu avec Théorème de Kleene ni Théorème de récursion de Kleene. En mathématiques, dans le domaine de la théorie des ordres, le théorème du point fixe de Kleene, s énonce comme suit : Soient L un ordre partiel… …   Wikipédia en Français

  • Théorème de l'étoile — Lemme de l étoile En théorie des langages, le lemme de l étoile (ou encore lemme d itération, lemme de pompage, pumping lemma en anglais) décrit une propriété essentielle de tout langage rationnel. Informellement, il établit que tout mot… …   Wikipédia en Français

  • Theoreme de recursion de Kleene — Théorème de récursion de Kleene Le théorème de récursion de Kleene est un théorème important de la théorie de la calculabilité. Il permet d établir l égalité de fonctions calculables. Sommaire 1 Formulation avec les énumérations de fonctions… …   Wikipédia en Français

  • Théorème de récursion de kleene — Le théorème de récursion de Kleene est un théorème important de la théorie de la calculabilité. Il permet d établir l égalité de fonctions calculables. Sommaire 1 Formulation avec les énumérations de fonctions récursives 2 Autre formes 3 …   Wikipédia en Français

  • Theoreme d'incompletude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

  • Théorème d'incomplétude — de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme (Sur les… …   Wikipédia en Français

  • Théorème d'incomplétude de Godel — Théorème d incomplétude de Gödel Les théorèmes d incomplétude de Gödel sont deux théorèmes célèbres de logique mathématique, démontrés par Kurt Gödel en 1931 dans son article Über formal unentscheidbare Sätze der Principia Mathematica und… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”