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 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 automates finis, d'où le nom de langages reconnaissables. Les langages rationnels ont des applications à la fois théoriques et pratiques. Ils sont utilisés en informatique (par exemple en compilation de programmes), en linguistique (par exemple pour décrire la 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. Le langage informatique Java fournit aussi la classe . Les algorithmes utilisés pour manipuler les langages rationnels possèdent en général une implémentation rapide et efficace.
Définitions
Alphabet et langage On considère un ensemble fini 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 , puis de la lettre , puis encore de la lettre , se note .
La longueur d'un mot est définie comme le nombre de lettres qui constituent ce mot : ainsi, par exemple, le mot est de longueur 4. Et le mot vide, noté ou , est le seul mot de longueur nulle.
L'ensemble des mots que l'on peut former avec des lettres de , y compris le mot vide, est noté . Toute partie de s'appelle un langage. L'ensemble des mots de à l'exception du mot vide est un langage noté .
Opérations rationnelles Les opérations suivantes, définies sur les langages, sont appelées les opérations rationnellesPour qualifier certains des objets exposés dans cet article les ouvrages en français utilisent l'adjectif "rationnel" mais aussi "régulier". Ces deux adjectifs sont considérés comme équivalents dans l'article. Ainsi, par exemple, les expressions "opération rationnelle" et "opération régulière" sont considérées comme synonymes.. Soient et deux parties de , autrement dit deux langages :
1. la concaténation ou le produit de et , noté , est l'ensemble de mots , où est dans et est dans . Par exemple, le produit de et de est ; 2. l'union ensembliste, de et , notée , est l'ensemble des mots appartenant à ou à . Par exemple, l'union ensembliste de et de est ; 3. létoile de Kleene, notée est le plus petit langage qui contient le mot vide , le langage , 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 . Par exemple, .
Expressions rationnelles
Les expressions rationnelles sur l'alphabet sont des expressions obtenues à partir des lettres de , par un nombre fini d'applications des opérations rationnelles suivantes : L'opération ou (pour représenter l'union) L'opération (pour représenter le produit, ce point est d'ailleurs souvent omis) L'opération (pour représenter l'étoile de Kleene, aussi appelée itération). L'ensemble des expressions rationnelles sur un alphabet est noté . Il est défini par induction comme suit :
Langages rationnels Les langages rationnels ou langages réguliers ou encore langages reconnaissables utilisant un alphabet peuvent être définis de plusieurs façons équivalentes : ce sont les langages décrits par les expressions rationnelles sur l'alphabet ; ce sont les langages obtenus, à partir des lettres de et de l'ensemble vide, par l'utilisation d'un nombre fini d'''opérations rationnelles ; ce sont les langages utilisant les lettres de qui sont reconnus par des automates finis, d'où le nom de langages reconnaissables.
L'ensemble des langages rationnels sur l'alphabet est le plus petit ensemble de langages stable pour les opérations rationnelles, et qui contient le langage vide , les langages réduits à une lettre et le langage composé du mot vide .
En utilisant la première définition, on peut dénoter un langage utilisant l'alphabet comme où est un élément de . Et l'ensemble des langages rationnels, noté , est alors défini par induction à partir de et des constantes 0 et 1 comme suit :
, , pour chaque lettre de , , pour tous et appartenant à .
Propriétés
Deux expressions rationnelles et sur un alphabet sont dites équivalentes si elles dénotent le même langage soit, exprimé plus formellement, si .
Exemple : les expressions et sont équivalentes et dénotent un langage contenant tous les mots formés à partir des lettres et .
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.
Variantes de notation
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èglesPour une définition précise des règles de simplification, on peut consulter ..
On ajoute parfois aussi, aux opérateurs sur les expressions, la fermeture , donnant l'expression . Le langage dénoté est donné par , 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.
Expressions rationnelles et automates finis
Le théorème de Kleene
Le théorème de Kleene affirme que l'ensemble des langages rationnels sur un alphabet est exactement l'ensemble des langages sur 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
vignette|Exemple d'une expression rationnelle de hauteur d'étoile égale à 2. La hauteur d'étoile d'une expression rationnelle est le nombre défini récursivement comme suit : pour toute lettre
. En d'autres termes, la hauteur d'étoile d'une expression est le nombre maximum d'étoiles imbriquées. Par exemple, et . 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 est le minimum des hauteurs d'étoile des expressions dénotant ce langage, c'est-à-dire :
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.. 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. Résolu la première fois en 1982, sa solution a été ensuite améliorée, notamment par Daniel Kirsten en 2005.
Une question qui est toujours ouverte en 2016 concerne le : 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.
Le théorème de Myhill-Nerode
À tout langage de , on associe une relation d'équivalence sur définie de la façon suivante : si et seulement si pour tout mot de , on a Cette relation est une équivalence régulière à droite car elle est compatible avec la concaténation : si alors .
Le théorème de Myhill-Nerode affirme qu'un langage est rationnel si et seulement si la relation 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 sont en bijection avec les classes d'équivalence de la relation voir par exemple ou ou .. Ce résultat est aussi à la base d'un algorithme efficace de minimisation, appelé l'algorithme de Moore.
Propriétés Propriétés algébriques L'ensemble des langages rationnels est stable, en plus de l'union, du produit et de l'étoile, par complémentation et donc par intersection. L'ensemble des langages rationnels est fermé par image miroir : si est un langage rationnel, alors est rationnel, où est l'ensemble des retournés ou images miroir des mots de . L'ensemble des préfixes, l'ensemble des suffixes, l'ensemble des facteurs, l'ensemble des sous-mots des mots d'un langage rationnel sont des langages rationnels.. Pour tout langage rationnel et tout mot , le quotient gauche est un langage rationnel. L'image d'un langage rationnel par un morphisme ou un morphisme inverse est un langage rationnel. L'image, par une substitution rationnelle, d'un langage rationnel est un langage rationnel (une substitution de dans est une application de dans l'ensemble des parties de qui est un morphisme pour la structure de monoïde multiplicatif sur l'ensemble des parties de , c'est-à-dire et , où le produit dans le membre droit est le produit des parties de . Une substitution rationnelle est une substitution telle qui est un langage rationnel sur pour toute lettre de ). 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 et est l'ensemble des mots , où les et les sont des mots, tels que et . 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 est le langage . En d'autres termes, on coupe au milieu des mots de de longueur paire et on garde la première partie. Si est un langage rationnel, alors 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.. 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.