Langage rationnel

Les opérations suivantes, définies sur les langages, sont appelées les opérations rationnelles. Soient ${\displaystyle X}$ et ${\displaystyle Y}$ deux parties de ${\displaystyle A^{*}}$ :

1. la concaténation ou le produit de ${\displaystyle X}$ et ${\displaystyle Y}$, noté ${\displaystyle XY}$, est l'ensemble de mots ${\displaystyle xy}$, où ${\displaystyle x}$ est dans ${\displaystyle X}$ et ${\displaystyle y}$ est dans ${\displaystyle Y}$.

Par exemple, le produit de ${\displaystyle \{ab,c\}}$ et de ${\displaystyle \{ba,c\}}$ est ${\displaystyle \{abba,abc,cba,cc\}}$;

2. l'union ensembliste, de ${\displaystyle X}$ et ${\displaystyle Y}$, notée ${\displaystyle X\cup Y}$, est l'ensemble des mots appartenant à ${\displaystyle X}$ ou à ${\displaystyle Y}$.

Par exemple, l'union ensembliste de ${\displaystyle \{ab,c\}}$ et de ${\displaystyle \{ba,c\}}$ est ${\displaystyle \{ab,c,ba\}}$;

3. l'étoile de Kleene, notée ${\displaystyle X^{*}}$ est le plus petit langage qui contient le mot vide ${\displaystyle \varepsilon }$, le langage ${\displaystyle X}$, 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 ${\displaystyle X}$.

Par exemple, ${\displaystyle \{a,ab\}^{\star }=\{\varepsilon ,a,aa,ab,aaa,aab,aba,aaaa,aaab,aaba,abaa,abab,\dots \}}$.

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

Les expressions rationnelles sur l'alphabet ${\displaystyle A}$ sont des expressions obtenues à partir des constantes 0, 1, et de constantes ${\displaystyle a}$, pour les lettres ${\displaystyle a}$ de ${\displaystyle A}$, par des opérations suivantes :

1. L'opération ${\displaystyle +}$ ou ${\displaystyle |}$ (pour représenter l'union)
2. L'opération ${\displaystyle \cdot }$ (pour représenter le produit, ce point est d'ailleurs souvent omis)
3. L'opération ${\displaystyle *}$ (pour représenter l'étoile de Kleene, aussi appelée itération).

Chaque expression rationnelle ${\displaystyle e}$ dénote un langage rationnel. Ce langage, noté ${\displaystyle L(e)}$, est défini comme suit :

1. ${\displaystyle L(0)=\emptyset }$, ${\displaystyle \ L(1)=\{\varepsilon \}}$, ${\displaystyle \ L(a)=\{a\}\,}$ pour chaque lettre ${\displaystyle a}$
2. ${\displaystyle L(e+f)=L(e)\cup L(f)}$, ${\displaystyle \ L(e\cdot f)=L(e)L(f)}$, ${\displaystyle \ L(e^{\star })=L(e)^{\star }\,}$

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-anneaux, des algèbres de Kleene et des demi-anneaux étoilés complets.

Les expressions ${\displaystyle (a^{\star }b)^{\star }a^{\star }}$ et ${\displaystyle (a+b)^{\star }}$ sont équivalentes.

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é à 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[note 1].

On ajoute parfois aussi, aux opérateurs sur les expressions, la fermeture ${\displaystyle +}$, donnant l'expression ${\displaystyle e^{+}}$. Le langage dénoté est donné par ${\displaystyle L(e^{+})=L(e)^{+}}$, au sens de 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 expressions régulières fournis par de nombreux outils de programmation ou d'édition, comme Unix, 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.

Le théorème de Kleene affirme que l'ensemble des langages rationnels sur un alphabet ${\displaystyle A}$ est exactement l'ensemble des langages sur ${\displaystyle A}$ 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.

La hauteur d'étoile d'une expression rationnelle ${\displaystyle e}$ est le nombre ${\displaystyle h(e)}$ défini récursivement comme suit :

1. ${\displaystyle h(0)=h(1)=h(a)=0\,}$ pour toute lettre ${\displaystyle a}$
2. ${\displaystyle h(e+f)=h(e\cdot f)=\max\{h(e),h(f)\}}$
3. ${\displaystyle h(e^{\star })=1+h(e)}$.

En d'autres termes, la hauteur d'étoile d'une expression est le nombre maximum d'étoiles imbriquées. Par exemple, ${\displaystyle h((a+b)^{\star })=1}$ et ${\displaystyle \ h((a^{\star }b)^{\star }a^{\star })=2}$. 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 ${\displaystyle X}$ est le minimum des hauteurs d'étoile des expressions dénotant ce langage, c'est-à-dire

${\displaystyle h(X)=\min\{h(e)\mid L(e)=X\}.}$

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[1]. 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 problème de la hauteur d'étoile généralisée (en): 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 « langages sans étoile » caractérisés par Marcel-Paul Schützenberger.

À tout langage ${\displaystyle L}$ de ${\displaystyle A^{*}}$, on associe une relation d'équivalence ${\displaystyle \equiv _{L}}$ sur ${\displaystyle A^{*}}$ définie de la façon suivante :

${\displaystyle u\equiv _{L}v\,}$ si et seulement si pour tout mot ${\displaystyle x}$ de ${\displaystyle A^{*}}$, on a ${\displaystyle ux\in L\iff vx\in L}$

Cette relation est une équivalence régulière à droite car elle est compatible avec la concaténation : si ${\displaystyle u\equiv _{L}v}$ alors ${\displaystyle ux\equiv _{L}vx}$.

Le théorème de Myhill-Nerode affirme qu'un langage ${\displaystyle L}$ est rationnel si et seulement si la relation ${\displaystyle \equiv _{L}}$ est d'indice fini, c'est-à-dire possède un nombre fini de 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 ${\displaystyle L}$ sont en bijection avec les classes d'équivalence de la relation ${\displaystyle \equiv _{L}}$[2]. Ce résultat est aussi à la base d'un algorithme efficace de minimisation, appelé l'algorithme de Moore.

• 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 ${\displaystyle X}$ est un langage rationnel, alors ${\displaystyle X^{r}}$ est rationnel, où ${\displaystyle X^{r}}$ est l'ensemble des retournés ou images miroir des mots de ${\displaystyle X}$.

• L'ensemble des préfixes, l'ensemble des suffixes, l'ensemble des facteurs, l'ensemble des sous-mots des mots d'un langage rationnel est un langage rationnel[3].

• Pour tout langage rationnel ${\displaystyle X}$ et tout mot ${\displaystyle u}$, le quotient gauche
  ${\displaystyle u^{-1}X=\{w\mid uw\in X\}}$
  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 ${\displaystyle \sigma }$ de ${\displaystyle A^{*}}$ dans ${\displaystyle B^{*}}$ est une application de ${\displaystyle A^{*}}$ dans l'ensemble des parties de ${\displaystyle B^{*}}$ qui est un morphisme pour la structure de monoïde multiplicatif sur l'ensemble des parties de ${\displaystyle B^{*}}$, c'est-à-dire ${\displaystyle \sigma (\varepsilon )=\{\varepsilon \}}$ et ${\displaystyle \sigma (xy)=\sigma (x)\sigma (y)}$, où le produit dans le membre droit est le produit des parties de ${\displaystyle B^{*}}$. Une substitution rationnelle est une substitution ${\displaystyle \sigma }$ telle qui ${\displaystyle \sigma (a)}$ est un langage rationnel sur ${\displaystyle B}$ pour toute lettre ${\displaystyle a}$ de ${\displaystyle A}$).

• 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 ${\displaystyle x}$ et ${\displaystyle y}$ est l'ensemble des mots ${\displaystyle x_{1}y_{1}x_{2}y_{2}\cdots x_{n}y_{n}}$, où les ${\displaystyle x_{i}}$ et les ${\displaystyle y_{i}}$ sont des mots, tels que ${\displaystyle x=x_{1}x_{2}\dots x_{n}}$ et ${\displaystyle y=y_{1}y_{2}\dots y_{n}}$. 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 ${\displaystyle X}$ est le langage
  ${\displaystyle P(X)=\{p\in A^{\star }\mid \exists q\in A^{\star }:|p|=|q|{\text{ et }}pq\in X\}}$.
  En d'autre termes, on coupe au milieu des mots de ${\displaystyle X}$ de longueur paire et on garde la première partie. Si ${\displaystyle X}$ est un langage rationnel, alors ${\displaystyle P(X)}$ 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.

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[4]. 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 ${\displaystyle L}$ et ${\displaystyle M}$ étant donnés, a-t-on l'inclusion ${\displaystyle L\subset M}$, l'égalité ${\displaystyle L=M}$ ?
  L'inclusion ${\displaystyle L\subseteq M}$ se ramène à tester que langage ${\displaystyle L\cap {\bar {M}}}$ est vide, où ${\displaystyle {\bar {M}}}$ est le langage complément de ${\displaystyle M}$. 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 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.

Lorsque l'alphabet est composé d'une seule lettre ${\displaystyle a}$, on connait une caractérisation précise des langages rationnels. Pour tout langage ${\displaystyle L}$ de ${\displaystyle a^{*}}$, on note ${\displaystyle X(L)}$ l'ensemble des exposants de ${\displaystyle L}$, soit

${\displaystyle X(L)=\{n\in \mathbb {N} \mid a^{n}\in L\}}$.

On a alors la propriété suivante :

Un langage ${\displaystyle L}$ sur ${\displaystyle a^{*}}$ est rationnel si et seulement si son ensemble d'exposant ${\displaystyle X(L)}$ est la réunion d'un ensemble fini de progressions arithmétiques.

Une progression arithmétique est un ensemble de la forme ${\displaystyle \{r+ns\mid n\in \mathbb {N} \}}$. Dans cette définition, la raison ${\displaystyle s}$ est positive ou nulle; quand elle est nulle, la progression est réduite au singleton ${\displaystyle r}$ ; on autorise aussi ${\displaystyle r}$ à être plus grand que ${\displaystyle s}$. 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 ${\displaystyle \{a^{3},a^{5}\}\cup (a^{2})^{*}a^{10}}$.

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 ${\displaystyle L}$. Soit ${\displaystyle q_{0}}$ son état initial, et soit

${\displaystyle q_{h}=q_{h-1}\cdot a=q_{0}\cdot a^{h}}$

l'état atteint après la lecture de ${\displaystyle h}$ lettres. La suite d'états

${\displaystyle q_{0},q_{1},\ldots ,q_{n},\ldots }$

est ultimement périodique; en effet, l'automate n'a qu'un nombre fini d'états, donc il existe des entiers ${\displaystyle n}$ et ${\displaystyle m>n}$ tels que ${\displaystyle q_{n}=q_{m}}$, et alors ${\displaystyle q_{n+k}=q_{m+k}}$ pour tout ${\displaystyle k>0}$. Soit ${\displaystyle n}$ le plus petit indice tel que ${\displaystyle q_{n}}$ apparaît deux fois, et donc une infinité de fois, dans la suite des états, et soit ${\displaystyle s>0}$ le plus petit entier tel que ${\displaystyle q_{n}=q_{n+s}}$. L'ensemble des mots qui amènent l'état initial ${\displaystyle q_{0}}$ sur l'état ${\displaystyle q_{h}}$ est égal au singleton ${\displaystyle a^{h}}$ si ${\displaystyle h<n}$, et est égal à ${\displaystyle a^{h}(a^{s})^{*}}$ 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 ${\displaystyle a^{h}(a^{s})^{*}}$ 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[note 2].