Voir la source de Langage rationnel

En [[théorie des langages]], les '''langages rationnels''' ou '''langages réguliers''' ou encore '''langages reconnaissables''' peuvent être décrits de plusieurs façons équivalentes :
* ce sont les langages décrits par les [[expression rationnelle|expressions régulières ou rationnelles]], d'où le nom de langages ''réguliers'' ;
* ce sont les langages obtenus, à partir des lettres et de l'ensemble vide, par les ''opérations rationnelles'', à savoir l'union, le produit et l'[[étoile de Kleene]], d'où le nom de langages ''rationnels'' ;
* ce sont les langages reconnus par des [[automate fini|automates finis]], d'où le nom de langages ''reconnaissables''.
Les langages rationnels ont de très nombreuses applications, à la fois théoriques et pratiques. Ils sont utilisés en informatique (par exemple en [[compilation (informatique)|compilation]]), en linguistique (par exemple pour décrire la [[morphologie (linguistique)|morphologie d'une langue]]), ils interviennent dans les traitements de texte, ou dans des commandes spécifiques comme [[grep]] du système [[Unix]].

Pour la manipulation des langages rationnels et des automates, il existe de nombreux outils informatiques, notamment dans les systèmes du type [[Unix]] comme la commande [[lex et yacc|lex]]. Le langage informatique [[Java (langage)|Java]] fournit aussi la classe <tt>Pattern</tt>. Les algorithmes utilisés pour manipuler les langages rationnels possèdent en général une implémentation rapide et efficace.

== Définition ==

On considère un ensemble fini <math>A</math> de ''caractères'' ou ''lettres'', appelé ''alphabet''. Une ''chaîne de caractères'' (ou ''chaîne'' ou ''mot'') est une suite finie, éventuellement vide, de caractères. Par exemple, la chaîne formée de la lettre <math>a</math>, puis de la lettre <math>b</math>, puis encore de la lettre <math>a</math>, se note <math>aba</math>.

L'ensemble des ''mots'' que l'on peut former avec ces lettres de <math>A</math> est noté <math>A^*</math>.
Toute partie de <math>A^*</math> s'appelle un '''langage'''.

=== Opérations rationnelles ===
Les opérations suivantes, définies sur les langages, sont appelées les ''opérations rationnelles''. Soient <math>X</math> et <math>Y</math> deux parties de <math>A^*</math> :

1. la ''[[concaténation]]'' ou le ''produit'' de <math>X</math> et <math>Y</math>, noté <math>XY</math>, est l'ensemble de mots <math>xy</math>, où <math>x</math> est dans <math>X</math> et <math>y</math> est dans <math>Y</math>.
::::Par exemple, le produit de <math>\{ab, c\}</math> et de <math>\{ba,c\}</math> est <math>\{abba,abc, cba,cc\}</math>;
2. l'''[[Union (mathématiques)|union ensembliste]]'', de <math>X</math> et <math>Y</math>, notée <math>X\cup Y</math>, est l'ensemble des mots appartenant à <math>X</math> ou à <math>Y</math>.
::::Par exemple, l'union ensembliste de <math>\{ab, c\}</math> et de <math>\{ba,c\}</math> est <math>\{ab,c,ba\}</math>;
3. l'''[[étoile de Kleene]]'', notée <math>X^{*}</math> est le plus petit langage qui contient le mot vide <math>\varepsilon</math>, le langage <math>X</math>, et qui est clos pour l'opération de concaténation. C'est aussi l'ensemble de tous les produits de tous les mots de <math>X</math>.
::::Par exemple, <math>\{a,ab\}^\star = \{\varepsilon,a,aa,ab,aaa,aab,aba,aaaa,aaab,aaba,abaa,abab,\dots\}</math>.

=== Langages rationnels ===
L'ensemble des '''langages rationnels''' sur l'alphabet <math>A</math>
est le plus petit ensemble de langages stable pour les opérations rationnelles, et qui contient le langage vide <math>\emptyset</math> , les langages réduits à une lettre et le langage composé du mot vide <math>\{\varepsilon\}</math>.

=== Expressions rationnelles ===

Les '''expressions rationnelles''' sur l'alphabet <math>A</math> sont des expressions obtenues à partir des ''constantes'' 0, 1, et de constantes <math>a</math>, pour les lettres <math>a</math> de <math>A</math>, par des
opérations suivantes :
# L'opération <math>+</math> ou <math>|</math> (pour représenter l'union)
# L'opération <math>\cdot</math> (pour représenter le produit, ce point est d'ailleurs souvent omis)
# L'opération <math>*</math> (pour représenter l'étoile de Kleene, aussi appelée itération).

Chaque expression rationnelle <math>e</math> '''dénote''' un langage rationnel. Ce langage, noté <math>L(e)</math>, est défini comme suit :
# <math>L(0)=\emptyset</math>, <math>\ L(1)=\{\varepsilon\}</math>, <math>\ L(a)=\{a\}\,</math> pour chaque lettre <math>a</math>
# <math>L(e+f)=L(e)\cup L(f)</math>, <math>\ L(e\cdot f)=L(e)L(f)</math>, <math>\ L(e^\star)=L(e)^\star\,</math>

Deux expressions rationnelles sont '''équivalentes''' si elles dénotent le même langage.

Dotées d'un opérateur d'addition, d'un opérateur de produit et d'une [[relation d'équivalence]], les expressions rationnelles sont des [[demi-anneau]]x, des [[algèbre de Kleene|algèbres de Kleene]] et des demi-anneaux étoilés complets.

==== Exemple ====
Les expressions <math>(a^\star b)^\star a^\star</math> et <math>(a+b)^\star</math> sont équivalentes.

==== Variantes ====

Pour diminuer les parenthèses dans les expressions, on omet les parenthèses résultant de l'[[associativité]] des opérations, et de donner la plus haute [[Priorité (mathématiques)|priorité]] à l'étoile de Kleene, suivie de la concaténation, puis de l'union. Formellement, cela signifie que l'on identifie des expressions qui se déduisent l'une de l'autre par l'application de ces règles<ref group="note">Pour une définition précise des règles de simplification, on peut consulter {{harvsp|Sakarovitch (2003)|réf=Sakarovitch}}.</ref>.

On ajoute parfois aussi, aux opérateurs sur les expressions, la fermeture <math>+</math>, donnant l'expression <math>e^+</math>. Le langage dénoté est donné par <math>L(e^+)=L(e)^+</math>, au sens de [[Étoile de Kleene#Opérateur plus|opérateur plus]].

En revanche, l'opérateur de complémentation ne fait pas partie des opérations définissant les expressions rationnelles. Par contre, on définit les ''expressions rationnelles étendues'' comme les expressions incluant aussi l'opérateur de complémentation.

Dans les [[Expression rationnelle|expressions régulières]] fournis par de nombreux outils de programmation ou d'édition, comme [[Unix]], [[QED (logiciel)|qed]], [[grep]], [[Emacs]], d'autres opérateurs sont généralement ajoutés, avec des propriétés qui les rendent capables de décrire des langages qui ne sont pas rationnels. Ces expressions ne sont donc pas strictement équivalentes aux expressions rationnelles définies formellement ci-dessus.

== Expressions rationnelles et automates finis ==

=== Le théorème de Kleene ===
{{Article détaillé|théorème de Kleene|automate fini}}

Le [[théorème de Kleene]] affirme que l'ensemble des langages rationnels sur un alphabet <math>A</math> est exactement l'ensemble des langages sur <math>A</math> reconnaissables par [[automate fini]]. C'est le résultat fondamental pour la théorie et les applications.

La correspondance entre langages rationnels et langages reconnaissables est effective : pour toute expression régulière, on peut construire effectivement, et de plusieurs façons, des automates qui reconnaissent le langage dénoté par l'expression. Réciproquement, à tout automate fini on peut associer une expression régulière qui dénote le langage reconnu par l'automate. Là aussi, il y a plusieurs méthodes, et on peut obtenir des expressions différentes, mais équivalentes.

=== Hauteur d'étoile ===
{{loupe|Problème de la hauteur d'étoile}}
La ''hauteur d'étoile d'une expression rationnelle'' <math>e</math> est le nombre <math>h(e)</math> défini récursivement comme suit :
# <math>h(0)=h(1)=h(a)=0\,</math> pour toute lettre <math>a</math>
# <math>h(e+f)=h(e\cdot f)=\max\{h(e),h(f)\}</math>
# <math>h(e^\star)=1+h(e)</math>.
En d'autres termes, la hauteur d'étoile d'une expression est le nombre maximum d'étoiles imbriquées. Par exemple, <math>h((a+b)^\star)=1</math> et <math>\ h((a^\star b)^\star a^\star)=2</math>. Ces deux expressions dénotent le même langage, on voit donc que la notion de hauteur d'étoile est liée à l'expression.

La ''hauteur d'étoile d'un langage rationnel'' <math>X</math> est le minimum des hauteurs d'étoile des expressions dénotant ce langage, c'est-à-dire
:<math>h(X)=\min\{h(e)\mid L(e)=X\}.</math>

La question de l'existence de langages rationnels de hauteur d'étoile arbitrairement grande a été posée par Lawrence C. Eggan et résolue par Françoise Dejean et [[Marcel-Paul Schützenberger]]<ref>{{harvsp|Dejean et Schützenberger (1966)|réf=DejeanSchutz1966}}.</ref>. Le [[problème de la hauteur d'étoile]] est de calculer, de manière efficace, la hauteur d'étoile d'un langage rationnel. Ce problème a résisté longtemps. Il a été résolu la première fois en 1982 ; le meilleur algorithme, dû à Kirsten, est de 2005.

Une question qui est toujours ouverte en 2016 concerne le {{Lien|langue=en|trad=Generalized_star_height_problem|fr=problème de la hauteur d'étoile généralisée}}: si l'on autorise, comme opérateur supplémentaire, l'opérateur de complémentation, le pouvoir de description des expressions rationnelles (appelées ''généralisées'') augmente bien entendu. On ne sait toujours pas s'il existe des langages rationnels de hauteur d'étoile généralisée arbitrairement grande (ni même de hauteur 2). Les langages de hauteur d'étoile généralisée 0 sont les « [[langage sans étoile|langages sans étoile]] » caractérisés par [[Marcel-Paul Schützenberger]].

=== Le théorème de Myhill-Nerode ===
{{Article détaillé|Théorème de Myhill-Nerode}}

À tout langage <math>L</math> de <math>A^*</math>, on associe une [[relation d'équivalence]] <math>\equiv_L</math> sur <math>A^*</math> définie de la façon suivante :
:<math>u\equiv_L v\,</math> si et seulement si pour tout mot <math>x</math> de <math>A^*</math>, on a <math>ux\in L \iff vx\in L</math>
Cette relation est une [[relation d'équivalence|équivalence]] régulière à droite car elle est compatible avec la concaténation : si <math>u\equiv_L v</math> alors <math>ux\equiv_L vx</math>.

Le [[théorème de Myhill-Nerode]] affirme qu'un langage <math>L</math> est rationnel si et seulement si la relation <math>\equiv_L</math> est d'indice fini, c'est-à-dire possède un nombre fini de [[relation d'équivalence#Classe d'équivalence|classes d'équivalence]].

Ce théorème a un intérêt théorique puisqu'il donne une caractérisation intrinsèque de l'automate minimal reconnaissant un langage donné. En effet, les états de l'automate fini déterministe minimal reconnaissant un langage rationnel <math>L</math> sont en bijection avec les classes d'équivalence de la relation <math>\equiv_L</math><ref> voir par exemple {{harvsp|Hopcroft|Ullman|1979}} ou {{harvsp|Carton (2008)|réf=Carton2008}} ou {{harvsp|Sakarovitch (2003)|réf=Sakarovitch}}.</ref>. Ce résultat est aussi à la base d'un algorithme efficace de [[Minimisation d'un automate fini déterministe|minimisation]], appelé l'algorithme de Moore.

== Propriétés ==
=== Propriétés algébriques ===
* Les langages rationnels sont fermés, en plus de l'union, du produit et de l'étoile, par complémentation et donc par intersection.

* Les langages rationnels sont fermés par image miroir : si <math>X</math> est un langage rationnel, alors <math>X^r</math> est rationnel, où <math>X^r</math> est l'ensemble des retournés ou [[mot (mathématiques)|images miroir]] des mots de <math>X</math>.

* L'ensemble des [[mot (mathématiques)|préfixes]], l'ensemble des [[mot (mathématiques)|suffixes]], l'ensemble des [[mot (mathématiques)|facteurs]], l'ensemble des [[mot (mathématiques)|sous-mots]] des mots d'un langage rationnel est un langage rationnel<ref>{{Ouvrage|langue=fr|auteur1=Petazzoni, Bruno|titre=Seize problèmes d'informatique|éditeur=|année=|passage=73|isbn=}}.</ref>.

* Pour tout langage rationnel <math>X</math> et tout mot <math>u</math>, le ''quotient gauche'' <br />&nbsp; &nbsp; &nbsp; &nbsp;<math>u^{-1}X=\{w\mid uw\in X\}</math><br /> est un langage rationnel.

* L'image d'un langage rationnel par un morphisme est un langage rationnel.

* L'image par un morphisme inverse d'un langage rationnel est un langage rationnel

* L'image, par une substitution rationnelle, d'un langage rationnel est un langage rationnel (une ''substitution'' <math>\sigma</math> de <math>A^*</math> dans <math>B^*</math> est une application de <math>A^*</math> dans l'ensemble des parties de <math>B^*</math> qui est un morphisme pour la structure de monoïde multiplicatif sur l'ensemble des parties de <math>B^*</math>, c'est-à-dire <math>\sigma(\varepsilon)=\{\varepsilon\}</math> et <math>\sigma(xy)=\sigma(x)\sigma(y)</math>, où le produit dans le membre droit est le produit des parties de <math>B^*</math>. Une ''substitution rationnelle'' est une substitution <math>\sigma</math> telle qui <math>\sigma(a)</math> est un langage rationnel sur <math>B</math> pour toute lettre <math>a</math> de <math>A</math>).

* Le produit de mélange (en anglais ''shuffle product'') de deux langages rationnels est un langage rationnel (le produit de mélange de deux mots <math>x</math> et <math>y</math> est l'ensemble des mots <math>x_1y_1x_2y_2\cdots x_ny_n</math>, où les <math>x_i</math> et les <math>y_i</math> sont des mots, tels que <math>x=x_1x_2\dots x_n</math> et <math>y=y_1y_2\dots y_n</math>. Le produit de mélange de deux langages est la réunion des produits de mélange des mots des langages).

* La ''première moitié'' d'un langage <math>X</math> est le langage<br />&nbsp; &nbsp;&nbsp;&nbsp;<math>P(X)=\{p\in A^\star \mid\exists q\in A^\star : |p|=|q| \text{ et } pq\in X\}</math>.<br /> En d'autre termes, on coupe au milieu des mots de <math>X</math> de longueur paire et on garde la première partie. Si <math>X</math> est un langage rationnel, alors <math>P(X)</math> est un langage rationnel.

* Si l'on supprime, dans les mots d'un langage rationnel, une lettre sur deux, le résultat est encore un langage rationnel.

=== Propriétés décidables ===
La plupart des questions que l’on pose habituellement pour des langages formels sont décidables pour les langages rationnels, et les démonstrations sont souvent faciles<ref>{{harvsp|Hopcroft|Ullman|1979|p=40}}.</ref>. On suppose que le langage ou les langages sont donnés par des automates finis. Les propriétés sont donc plutôt des propriétés des automates finis, ou simplement des graphes finis sous-jacents. Les propriétés suivantes sont décidables :
* Un mot donné appartient-il à un langage rationnel : il suffit de tester si le mot est reconnu par l’automate.
* Le langage rationnel est-il vide : pour cela, on teste si, parmi les états accessibles, figure un état final.
* Le langage contient-il tous les mots : il suffit de tester si le complémentaire est vide.
* Le langage est-il fini : pour ce faire, on teste si l'automate, une fois émondé, a un graphe sous-jacent sans circuit.
* Deux langages rationnels <math>L</math> et <math>M</math> étant donnés, a-t-on l'inclusion <math>L\subset M</math>, l'égalité <math>L= M</math> ? <br />L'inclusion <math>L\subseteq M</math> se ramène à tester que langage <math>L\cap \bar M</math> est vide, où <math>\bar M</math> est le langage complément de <math>M</math>. Comme ce langage est lui-même rationnel, la décidabilité découle de la deuxième des propriétés ci-dessus. L'égalité équivaut à la double inclusion.
Une question plus difficile concerne la [[Théorie de la complexité des algorithmes|complexité algorithmique]] de ces problèmes de décision; par exemple, le calcul du complémentaire d'un langage demande la déterminisation de l'automate, et peut donc exiger une place et un temps exponentiel.

== Lemme d'itération ==
Le [[Lemme de l'étoile|lemme d'itération]] (en anglais ''pumping lemma'', traduit parfois malheureusement par ''lemme de pompage'') donne une propriété nécessaire des langages rationnels. Il s'énonce informellement comme suit : dans tout mot assez long <math>w</math> d'un langage rationnel <math>X</math>, on peut trouver un facteur <math>u</math> non vide que l'on peut répéter un nombre arbitraire de fois, tout en restant dans le langage <math>X</math>.

C'est en fait une propriété d'un automate reconnaissant le langage <math>X</math> : un mot assez long reconnu par l'automate contient nécessairement un circuit qui l'on peut parcourir un nombre arbitraire de fois, tout en restant reconnu par l'automate

Ce lemme n'est pas une caractérisation des langages rationnels : il existe des langages qui vérifient la propriété d'itération mais qui ne sont pas rationnels.

== Exemples et contre-exemples ==
Les langages suivants '''sont''' rationnels :

* L'ensemble des notations décimales des entiers naturels sur l'alphabet : <math>0, 1, 2, 3, 4, 5, 6, 7, 8, 9</math>.
* Tout langage fini.
* L'ensemble des mots qui contient un mot fixé.
* L'ensemble des mots qui contiennent un nombre pair de "1".
* L'ensemble des mots qui sont l'écriture en binaire d'un entier [[Congruence sur les entiers|congruent]] à 2 modulo 5.

Les langages suivants '''ne sont pas''' rationnels :

* L'ensemble de mots <math>\{a^nb^n: n \ge 0 \}</math>
* Les ensembles <math>\{a^nb^p: n \ge p\ge0 \}</math>,<math>\{a^nb^p: n \ne p\}</math>
* Une ''expression bien parenthésée'' est obtenue comme étant soit le mot vide, soit <math>(e)e'</math> où <math>e</math> et <math>e'</math> sont bien parenthésées. L'ensemble des expressions bien parenthésées est aussi appelé le [[langage de Dyck]].<br /> Ce n'est pas un langage rationnel car son intersection avec le langage rationnel <math>(^\star )^\star </math> n'est pas un langage rationnel (c'est le langage précédent à un changement de symboles près).
* L'ensemble des [[palindrome]]s.

=== Les langages rationnels sur une seule lettre ===

Lorsque l'alphabet est composé d'une seule lettre <math>a</math>, on connait une caractérisation précise des langages rationnels. Pour tout langage <math>L</math> de <math>a^*</math>, on note <math>X(L)</math> l'ensemble des ''exposants'' de <math>L</math>, soit
:<math>X(L)=\{n\in\N\mid a^n\in L\}</math>.
On a alors la propriété suivante :
:''Un langage <math>L</math> sur <math>a^*</math> est rationnel si et seulement si son ensemble d'exposant <math>X(L)</math> est la réunion d'un ensemble fini de [[progression arithmétique|progressions arithmétiques]].''
Une progression arithmétique est un ensemble de la forme <math>\{r+ns\mid n\in \N\}</math>. Dans cette définition, la raison <math>s</math> est positive ou nulle; quand elle est nulle, la progression est réduite au singleton <math>r</math> ; on autorise aussi <math>r</math> à être plus grand que <math>s</math>. Par exemple, il existe un langage rationnel sur une lettre dont l'ensemble des exposants est la réunion des entiers pairs plus grand que 10, et des entiers 3 et 5. Ce langage est <math>\{a^3,a^5\}\cup (a^2)^*a^{10}</math>.

Pour ''démontrer'' que le langage rationnel de l'énoncé a bien la forme indiquée, on considère un automate fini déterministe complet qui reconnaît <math>L</math>. Soit <math>q_0</math> son état initial, et soit
:<math>q_h=q_{h-1}\cdot a=q_0\cdot a^h</math>
l'état atteint après la lecture de <math>h</math> lettres. La suite d'états
:<math>q_0,q_1,\ldots,q_n,\ldots</math>
est ultimement périodique; en effet, l'automate n'a qu'un nombre fini d'états, donc il existe des entiers <math>n</math> et <math>m>n</math> tels que <math>q_n=q_m</math>, et alors <math>q_{n+k}= q_{m+k}</math> pour tout <math>k>0</math>. Soit <math>n</math> le plus petit indice tel que <math>q_n</math> apparaît deux fois, et donc une infinité de fois, dans la suite des états, et soit <math>s>0</math> le plus petit entier tel que <math>q_n=q_{n+s}</math>. L'ensemble des mots qui amènent l'état initial <math>q_0</math> sur l'état <math>q_h</math> est égal au singleton <math>a^h</math> si <math>h<n</math>, et est égal à <math>a^h(a^s)^*</math> sinon. Dans les deux cas, l'ensemble des exposants est une progression arithmétique. Comme le langage reconnu est une réunion de langages de ce type, il est de la forme annoncée.
La réciproque se démontre tout simplement : chaque langage de la forme <math>a^h(a^s)^*</math> est visiblement rationnel, et une réunion finie de langages de cette forme l'est encore.

Dans cette preuve, on utilise les expressions rationnelles dans une des directions, et la structure de l'automate fini dans l'autre<ref group="note">Pour des détails supplémentaires, on peut consulter {{harvsp|Sakarovitch (2003)|réf=Sakarovitch}}. L'énoncé se trouve à la page 117, c'est la Proposition I.3.3.</ref>.

== Nombre de mots de longueur donnée dans un langage rationnel ==
Pour un langage rationnel <math>L</math> donné, notons <math>s_n</math> le nombre de mots de longueur <math>n</math> de <math>L</math>. Par exemple, si <math>L</math> est l'ensemble des mots sur deux lettres <math>a,b</math> ne contenant pas deux <math>b</math> consécutifs, on a
:<math>L=\{\varepsilon, a, b, aa, ab, ba, aaa, aab, aba, baa, bab,\ldots \}</math>
et la suite des nombres de mots est
:<math>1,2,3,5,\ldots</math>.
C'est en fait la suite des [[nombre de Fibonacci|nombres de Fibonacci]].

La [[série génératrice]] de la suite des longueurs est la série
:<math>f_L(z)=\sum_{n=0}^\infty s_n z^n</math>.
Dans l'exemple, c'est la série
:<math>f_L(z)=1 + 2z + 3z^2+ 5z^3+\cdots=\frac{1+z}{1-z- z^2}</math>.
L'observation importante est que la série génératrice des longueurs, pour un langage rationnel, est toujours une fraction rationnelle. La suite des longueurs vérifie donc une relation de récurrence linéaire à coefficients constants. La série et la relation de récurrence sont effectivement calculables.

Le fait que la série reste rationnelle peut être exploité pour montrer que certains langages ne sont pas rationnels. Par exemple, pour le [[langage de Dyck]] sur une paire de parenthèses, le nombre de mots de longueur <math>2 n</math> est le <math>n</math>-ième [[nombre de Catalan]], et la série génératrice des nombres de Catalan n'est pas rationnelle.

[[Fichier:Automate-Fibonacci.jpg|vignette|Automate de Fibonacci.]]

Soit <math>\mathcal{A} = (Q, \mathcal{F}, I, T)</math> un automate fini sur un alphabet A reconnaissant un langage <math>L</math> donné. Pour simplifier les notations, on suppose que <math>Q=\{1,2,\ldots,k\}</math>. On note <math>L_{i,j}</math> le langage des mots <math>w</math> qui sont étiquettes de chemins de <math>i</math> à <math>j</math>, de sorte que
:<math>L=\bigcup_{i\in I, t\in T}L_{i,t}</math>.
Pour l'exemple de l'automate de Fibonacci, on a <math>L=L_{1,1}\cup L_{1,2}</math>.
On suppose maintenant que l'automate <math>\mathcal{A}</math> est [[automate fini déterministe|déterministe]] - ou [[automate fini inambigu|inambigu]] - et on note
:<math>s_{i,j}(n)=\mathrm{Card}\{w\mid i\cdot w = j,\ |w|=n\}</math>.
C'est donc le nombre de mots de longueur <math>n</math> qui sont étiquettes de chemins de <math>i</math> à j. Il en résulte que le nombre de mots de longueur <math>n</math> du langage <math>L</math> est
:<math>s_n=\sum_{i\in I,t\in T}s_{i,t}(n)</math>.
Pour l'exemple de l'automate de Fibonacci, on a <math>s_n =s_{1,1}(n)+s_{1,2}(n)</math>.
Les nombres <math>s_{i,j}(n)</math> sont des coefficients d'une matrice associée naturellement à l’automate <math>\mathcal{A}</math>. Soit <math>M=(m_{i,j})</math> la matrice d'ordre <math>k</math> définie par
:<math>m_{i,j}=\mathrm{Card}\{a\in A\mid i\cdot a = j\}</math>.
Le nombre <math>m_{i,j}</math> est le nombre de transition de <math>i</math> à <math>j</math>; on a donc <math>m_{i,j}=s_{i,j}(1)</math> avec les notations précédentes.
Pour l'exemple de l'automate de Fibonacci, on a

:<math>M=\begin{pmatrix}1&1\\1&0\end{pmatrix}</math>

Il est facile de vérifier que, parce que l’automate est déterministe ou inambigu, les coefficients de la puissance <math>n</math>-ième de <math>M</math> sont précisément le nombre de mots de longueur <math>n</math> entre les états, soit
:<math>M^n=(s_{i,j}(n))</math>.
Le nombre de mots de longueur <math>n</math> du langage est la somme des coefficients indicés par l'état initial et les états terminaux.
Pour l'exemple de l'automate de Fibonacci, on a
:<math>M^2=\begin{pmatrix}2&1\\1&1\end{pmatrix}\ ,\quad M^3=\begin{pmatrix}3&2\\2&1\end{pmatrix}
\ ,\quad M^4=\begin{pmatrix}5&3\\3&2\end{pmatrix}</math>
et plus généralement
:<math>M^n=\begin{pmatrix}u_{n+1}&u_n\\u_n&u_{n-1}\end{pmatrix}</math>,
où <math>u_n</math> est le <math>n+1</math>-ième nombre de Fibonacci.
Enfin, comme toute matrice, la matrice <math>M</math> vérifie le [[théorème de Cayley-Hamilton]], les suites
<math>(s_{i,j}(n))_n\ge0</math> vérifient toutes la même relation de récurrence. Pour l'exemple de l'automate de Fibonacci, on a <math>M^2=M+I</math>, où <math>I</math> est la matrice identité.

== Autres caractérisations ==
Les langages rationnels sont aussi :
* les langages dont le [[monoïde syntaxique]] est fini ;
* les langages définissables dans S1S, la [[logique monadique du second ordre]] avec successeur (et aussi dans WS1S, la variante "weak", où la quantification du second ordre est sur les ensembles finis)<ref>{{Article|langue=en|prénom1=J. Richard|nom1=Büchi|titre=Weak Second-Order Arithmetic and Finite Automata|périodique=Mathematical Logic Quarterly|volume=6|numéro=1-6|date=1960-01-01|issn=1521-3870|doi=10.1002/malq.19600060105|lire en ligne=http://onlinelibrary.wiley.com/doi/10.1002/malq.19600060105/abstract|consulté le=2018-02-12|pages=66–92}}.</ref>{{,}}<ref>{{Article|prénom1=Calvin C.|nom1=Elgot|titre=Decision Problems of Finite Automata Design and Related Arithmetics|périodique=Transactions of the American Mathematical Society|volume=98|numéro=1|date=1961|doi=10.2307/1993511|lire en ligne=https://www.jstor.org/stable/1993511|consulté le=2018-02-12|pages=21–51}}.</ref>{{,}}<ref>{{Article|langue=|auteur1=Boris A. Trakhtenbrot|titre=Finite automata and the logic of monadic predicates|périodique=Dokl. Akad Nauk SSSR 140|date=1961|issn=|lire en ligne=|pages=326-329}}.</ref>{{,}}<ref>{{Ouvrage|langue=en|prénom1=Mark|nom1=Weyer|titre=Automata Logics, and Infinite Games|éditeur=Springer, Berlin, Heidelberg|collection=Lecture Notes in Computer Science|année=2002|passage=207–230, Theorem 12.26|isbn=3-540-36387-4|doi=10.1007/3-540-36387-4_12|lire en ligne=https://link.springer.com/chapter/10.1007/3-540-36387-4_12|consulté le=2018-02-12}}.</ref> ;
* les langages de type 3 dans la [[classification des langages|hiérarchie de Chomsky-Schützenberger]] : ce sont les langages qui peuvent être engendrés par une [[Hiérarchie de Chomsky#Type 3 : grammaires régulières|grammaire régulière]], c'est-à-dire une grammaire linéaire droite (ou linéaire gauche) ;
* les langages reconnus par des [[machine de Turing|machines de Turing]] qui n'écrivent pas sur leur bande (s'ils peuvent se déplacer dans les deux sens ce sont des [[automate fini déterministe bidirectionnel|automates finis ''bidirectionnels'']]) ;
* les langages reconnus par des [[automate fini alternant|automates finis alternants]] ;
* les [[langage congruentiel|langages congruentiels]] définissables par certains [[réécriture (informatique)|systèmes de réécriture]] de mots.
* la plus petite famille de langages qui contient les langages [[singleton]] et est fermée par union, concaténation, itération, fermeture, union, complémentation, division, miroir et substitution.

== Généralisation aux monoïdes quelconques ==

{{article détaillé|amorce=Voir aussi|Théorème de Kleene|Ensemble rationnel}}

Les parties rationnelles et les parties reconnaissables peuvent être définis dans tout [[monoïde]]. La contrepartie est qu'en général, le théorème de Kleene n'y est pas vérifié, c'est-à-dire que toute partie reconnaissable n'est pas nécessairement rationnelle et vice-versa.

Dans un [[monoïde]] <math>M</math>, l'ensemble des parties rationnelles est défini comme dans le cas de l'ensemble des mots <math>A^*</math>: c'est la plus petite famille, au sens de l'inclusion, de parties de <math>M</math> qui contient l'ensemble vide <math>\emptyset</math> et les singletons, et est stable par toutes les opérations rationnelles. Il est à noter que l'opération étoile revient à prendre le sous-monoïde engendré par la partie: ainsi, <math>a^*</math> est le monoïde engendré par l'élément <math>a</math>.

Pour ce qui est des parties reconnaissables, la définition par automates n'est plus appropriée car rien ne permet d'écrire un élément de <math>M</math> comme produit d'éléments minimaux (les lettres dans le cas de <math>A^*</math>). On utilise alors une définition équivalente, et qui peut être généralisée à tous les monoïdes. Une partie <math>L</math> de <math>M</math> est ''reconnue par un monoïde <math>N</math>'' s'il existe un [[Monoïde#Morphisme de monoïdes|morphisme de monoïdes]] <math>\Phi</math> de <math>M</math> sur <math>N</math> et une partie <math>R</math> de <math>N</math> tels que <math>L=\Phi^{-1}(R)</math>. Une ''partie reconnaissable'' de <math>M</math> est alors une partie reconnue par un monoïde <math>N</math> ''fini''.

Cette définition est bien équivalente à la première pour l'ensemble des mots. Si <math>L</math> est un langage rationnel, alors <math>L</math> est reconnu par son [[monoïde syntaxique]] (il suffit de prendre pour <math>\Phi</math> la projection canonique et pour <math>R</math> l'ensemble des classes d'équivalence incluses dans <math>L</math>).
Réciproquement, si <math>L</math> est un langage reconnu par un [[monoïde]] fini <math>M</math>, alors l'automate <math>(M,A,\delta,e,R)</math> où:
* <math>e</math> est l'élément neutre de <math>M</math>;
* <math>\delta</math> est défini pour tout <math>q\in M</math> et <math>a\in A</math> par: <math>\delta(q,a)=q\Phi(a)</math>
reconnaît <math>L</math>. En effet, par hypothèse, on a <math>L=\Phi^{-1}(R)</math>, et
un mot <math>w</math> est accepté si et seulement si <math>\delta(e,w)=\Phi(w)\in R</math>, donc si et seulement si <math>w</math> appartient à <math>\Phi^{-1}(R)</math>.

Le théorème de Kleene ne s'applique plus dans le cas général de monoïdes quelconques. Ainsi, une partie rationnelle pourra ne pas être reconnaissable et vice-versa. Néanmoins, on dispose d'un théorème dû à McKnight, qui recouvre une partie du théorème de Kleene et s'énonce ainsi: toute partie reconnaissable d'un monoïde <math>M</math> est rationnelle si et seulement si <math>M</math> admet une [[Monoïde#Famille génératrice d'un sous-monoïde|famille génératrice]] finie, c'est-à-dire est finiment engendrée.

== Histoire ==

La théorie débute dans les années 1940<ref group="note">Pour un exposé des premières années de la théorie des automates et des langages rationnels, voir {{harvsp|Perrin (1995)|réf=Perrin1995}}.</ref>. [[Warren McCulloch]] et [[Walter Pitts]] ont décrit, en 1943, le système nerveux en modélisant les neurones par des automates simples. Le logicien [[Stephen Cole Kleene]] a ensuite prouvé, en 1956, ce que l'on appelle le [[théorème de Kleene]]<ref>{{Chapitre 
| auteur1 = S. C. Kleene
| titre chapitre = Representation of events in nerve nets and finite automata.
| titre ouvrage = Automata Studies
| auteurs ouvrage = C.E. Shannon and J. McCarthy
| collection = Annals of Mathematics Studies
| volume = 34
| éditeur = Princeton University Press
| lieu = Princeton, N. J. 
| année = 1956
| page = 3 -- 41
| lire en ligne = http://www.dtic.mil/get-tr-doc/pdf?AD=ADA596138
}}.</ref>{{,}}<ref group="note"> P.46, Kleene introduit la notion d’''événement régulier'' (regular event), pour ce qui a été appelé plus tard ''ensemble régulier'' ou ''langage régulier'' et demande qu'on lui suggère un terme plus descriptif ! La définition des événements réguliers est p. 48.</ref>.
En 1956, [[Edward F. Moore]] publie son algorithme de minimisation.
En 1958, [[Anil Nerode]] et [[John Myhill]] publient leur caractérisation.
En 1959, [[Michael Rabin]] et [[Dana S. Scott|Dana Scott]] donnent, dans un célèbre article<ref>{{harvsp|Rabin et Scott (1959)|réf=RabinScott1959}}.</ref>, un traitement rigoureux de la théorie des automates. Cet exposé pionnier leur vaut le [[prix Turing]].

Du point de vue pratique, c'est [[Ken Thompson]]<ref group="note">Notons qu'il a lui aussi reçu le [[prix Turing]].</ref> qui implémente les expressions rationnelles dans l'éditeur [[QED (logiciel)|qed]], puis l'éditeur [[ed (logiciel)|ed]] sous Unix, et finalement dans [[grep]]. Depuis lors, les expressions rationnelles ont été largement utilisées dans les utilitaires tels que [[Lex et yacc|lex]] ainsi que dans les [[Langage de programmation|langages de programmation]] nés sous Unix, tels que [[expr]], [[awk]], [[Perl (langage)|Perl]], [[Langage de programmation Python|Python]]… Une bonne partie d'entre eux reposent sur la [[bibliothèque logicielle|bibliothèque]] regex, créée par Henry Spencer.

== Voir aussi ==
* [[Théorème de Kleene]]
* [[Monoïde syntaxique]]
* [[Théorème des variétés d'Eilenberg]]
* [[Algorithme de Thompson]]

== Notes et références ==
=== Notes ===
{{Références| groupe=note}}

=== Références ===
{{Références}}

== Bibliographie ==

* {{Article
| auteur = Dominique Perrin
| titre = Les débuts de la théorie des automates
| journal = Technique et science informatiques
| volume = 14
| numéro = 4
| année = 1995
| pages= 409-433
| url texte = http://www-igm.univ-mlv.fr/~perrin/Recherche/Publications/Loi/copie3.ps
| id=Perrin1995}}
* {{Article
| auteur = Françoise Dejean et [[Marcel-Paul Schützenberger]]
| titre = On a Question of Eggan
| journal = ''[[Information and Computation|Information and Control]]''
| volume = 9
| numéro = 1
| année = 1966
| pages= 23-2
| id=DejeanSchutz1966}}
* {{Ouvrage | langue=en | auteur1=John E. Hopcroft | auteur2=Jeffrey D. Ullman | titre=Introduction to Automata Theory, Languages, and Computation | éditeur=Addison Wesley | année=1979 | isbn=0-201-02988-X}}
* {{Langages formels, calculabilité et complexité}} <!-- id: Carton2008 -->
* {{Article|lang=en
| auteur = Michael O. Rabin et Dana Scott
| titre = Finite automata and their decision problems
| journal = IBM J. Res. Develop.
| volume = 3
| année = 1959
| pages= 114-125
| id=RabinScott1959}}
* {{Ouvrage
 | auteur1=Jacques Sakarovitch
 | titre=Éléments de théorie des automates
 | éditeur=[[Vuibert]]
 | année=2003
 | pages totales=816
 | isbn=978-2-7117-4807-5
 | id=Sakarovitch
}}{{Commentaire biblio|Traduction anglaise avec corrections: ''Elements of Automata Theory'', Cambridge University Press 2009, {{ISBN|9780521844253}}}}

{{Palette|Langages formels grammaires et automates|Informatique théorique}}
{{Portail|logique|informatique|informatique théorique}}

[[Catégorie:Langage formel]]
[[Catégorie:Calculabilité]]
[[Catégorie:Logique mathématique]]
[[Catégorie:Automates finis et langages réguliers]]