Théorème de Kleene

• On prouve que l'ensemble des langages reconnaissables est fermé par les opérations d'union, produit et étoile en réalisant les constructions des automates appropriés (voir le paragraphe Construction d'automates finis à partir des expressions rationnelles de l'article Automate fini non déterministe) ; comme il contient de plus les singletons et l'ensemble vide, on conclut en utilisant la définition de ${\displaystyle {\text{Rat }}A^{*}}$.
• On prouve que les langages décrits par une expression rationnelle sont reconnus par automate fini. Les méthodes les plus répandues sont :
  • la méthode de Thompson ;
  • la méthode de Glushkov ;
  • la méthode de Brzozowski.

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.

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, dû à John Horton Conway : on calcule la matrice des langages reconnus par partition ;
• L'algorithme d'élimination ou méthode de Brzozowski et McCluskey : on élimine les états, et on remplace les étiquettes par des expressions rationnelles.
• Le lemme d'Arden

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

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

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

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

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

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

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

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

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 ${\displaystyle A}$ un alphabet. Une relation d'indépendance ou relation de commutation ${\displaystyle I}$ est une partie ${\displaystyle I}$ de ${\displaystyle A\times A}$ qui est irréflexive et symétrique. Une relation d'indépendance ${\displaystyle I}$ définit une relation de dépendance réflexive et symétrique ${\displaystyle D}$ par ${\displaystyle D=A\times A\setminus I}$, et réciproquement.

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

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

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

• Warren S. McCulloch et Walter Pitts, « A logical calculus of the ideas immanent in nervous activity », Bull. Math. Biophys., vol. 5,‎ 1943, p. 115-133
• Robert McNaughton et H. Yamada, « Regular Expressions and State Graphs for Automata », IEEE Transactions on Electronic Computers, vol. 9, n^o 1,‎ 1960, p. 39-47

• Stephen C. Kleene, « Representation of events in nerve nets and finite automata. Automata studies », Annals of Mathematics Studies, Princeton University Press, n^o 34,‎ 1956, p. 3-41
• Dominique Perrin, « Les débuts de la théorie des automates », Technique et science informatiques, vol. 14, n^o 4,‎ 1995, p. 409-433 (lire en ligne)
• Michael O. Rabin et Dana Scott, « Finite automata and their decision problems », IBM J. Res. Develop., vol. 3,‎ 1959, p. 114-125
• Michaël Cadilhac, Dmitry Chistikov et Georg Zetzsche, « Rational Subsets of Baumslag-Solitar Groups », dans Artur Czumaj Anuj Dawar Emanuela Merelli (éditeurs), Actes de ICALP 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, coll. « LIPIcs » (n^o 168), 2020 (DOI 10.4230/LIPIcs.ICALP.2020.116, arXiv 2006.11898 (version détaillée), lire en ligne), p. 116:1-116:16

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)

• (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, 608 p. (ISBN 978-3-642-01491-8)

• (en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, New York, Academic Press, 1974 (ISBN 978-0-12-234001-7)

• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)

• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
  Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 978-0-52184425-3)