Langage rationnel - Définition

Introduction

Les expressions rationnelles permettent d'engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les langages de type 3 dans la hiérarchie de Chomsky. Ils peuvent donc être utilisés pour décrire la morphologie d'une langue.

Ces langages sont aussi exactement les langages reconnus formellement par des automates finis.

Les expressions rationnelles ont pour origine la théorie des automates et celle des langages formels.

Il existe de nombreux outils informatiques, notamment dans les systèmes du type Unix, pour opérer sur des expressions régulières (lex, yacc...). Le langage informatique Java fournit aussi la classe Pattern, qui offre toutes les fonctionnalités fondamentales pour la manipulation des expressions régulières, c'est-à-dire des langages rationnels. Les algorithmes utilisés pour manipuler les langages rationnels possèdent en général une implémentation rapide et efficace.

Théorie

On considère un ensemble fini de caractères ou lettres, ou alphabet, Σ. Une chaîne de caractères (ou chaîne tout court) est une suite finie, éventuellement vide, de caractères. La chaîne formée de 'a' puis 'b', puis 'a' se note "aba".

L'ensemble des chaînes de caractères (aussi appelées mots ou phrases) que l'on peut former avec ces lettres est noté Σ^*.

Cet ensemble Σ^* contient tous les mots possibles pouvant être construits à partir de l'alphabet Σ. Toute partie de Σ^* s'appelle un langage. Les expressions rationnelles constituent une sorte particulière de langage. On peut les générer à partir de constantes et d'opérateurs qui les décrivent.

Les constantes suivantes sont définies :

1. ensemble vide (noté ∅) : désigne l'ensemble vide (aucune chaîne de caractère n'est dans ∅) ;
2. mot vide ou chaîne vide (noté ε ) : désigne la chaîne de caractères qui ne contient aucune lettre ;
3. caractère littéral (noté a) : lorsque a est un élément de Σ, désigne la chaîne formée par le caractère a seul.

Les opérations suivantes sont aussi définies (soient R et S deux sous-ensembles de Σ^*) :

1. concaténation (notée R.S) : désigne l'ensemble { αβ où α appartient à R et β appartient à S }. Par exemple {"ab", "c"}.{"d", "ef"} = {"abd", "abef", "cd", "cef"} ;
2. union ensembliste (notée R U S) : désigne l'union des ensembles R et S;
3. fermeture de Kleene (notée R*): désigne le plus petit ensemble qui contient R comme sous-ensemble, ε comme élément, et est clos pour l'opération de concaténation. En d'autres termes, c'est l'ensemble de toutes les chaînes de caractères qui peuvent être formées en concaténant ε, une ou plusieurs chaînes de R. Par exemple, {"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }.

Comme il n'y a pas d'ambiguïté, les guillemets « " » seront omis dans la suite de l'article.

Les langages rationnels sur l'alphabet Σ sont définis récursivement comme étant :

1. soit le langage vide, noté ∅
2. soit les langages fait de mots à une lettre {a} avec a∈Σ, (notés simplement a)
3. soit les langages L₁ U L₂ où L₁,L₂ ∈ Rat(Σ)
4. soit les langages L₁L₂ où L₁,L₂ ∈ Rat(Σ)
5. soit les langages L₁^* où L₁ ∈ Rat(Σ)

On désigne l'ensemble des langages rationnels sur l'alphabet Σ par Rat(Σ).

Ainsi Rat(Σ) est le plus petit ensemble de langages stable par la concaténation de langages (notée « . »), par l'union et par la fermeture de Kleene (notée « * ») et qui contient le langage vide ∅ ainsi que tous les langages {a}où a∈Σ (que l'on notera abusivement a, tout simplement; de même que {ε}, le langage contenant le mot vide, est noté ε).

En théorie des langages formels

On remarque que R ε = εR = R, que (RS)T = R(ST), que R U ∅ = ∅ U R = R et que (R U S) U T = R U (S U T). Donc Σ^* muni de la concaténation avec comme élément neutre ε est un monoïde de même que Σ^* muni de l'union ensembliste avec comme élément neutre ∅.

Pour éviter le recours excessif aux parenthèses, on décide d'omettre les parenthèses résultant de l'associativité et de donner la plus haute priorité à l'étoile de Kleene, suivie de la concaténation, puis de l'union. Par exemple, (ab)c s'écrira abc et a U (b(c*)) s'écrira a U bc*. On omet aussi les accolades autour des singletons et les guillemets autour des mots.

On ajoute aussi la fermeture '+' définie comme suit: R⁺ est le plus petit ensemble contenant R et clos pour l'opération de concaténation. '+' se définit à partir des autres opérations par R⁺ = R R^*. Informellement, la fermeture '+' est la fermeture de Kleene dans lequel on ne prend pas ε.

Un autre opérateur redondant souvent inclus est l'opérateur complément noté ~, tel que ~R désigne l'ensemble des chaînes de caractères de Σ^* qui ne sont pas dans R. (Pour montrer que ~ est redondant, il faut faire un détour, par exemple par la théorie des automates finis).

Σ^* muni des opérateurs décrits ci-dessus forme une algèbre de Kleene.

Mise en œuvre

• a U b* désigne {"a", ε, "b", "bb", "bbb", ...};
• (a U b)* désigne l'ensemble des chaînes qui ne contiennent que des 'a' et des 'b', y compris la chaîne vide ε ;
• (a* b*)* désigne exactement le même ensemble (que des 'a' et des 'b', le mot vide compris) ;
• (ab*)* décrit tous les mots ne contenant que des 'a' et des 'b', commençant par 'a', y compris la chaîne vide ε ;
• ab*(c U ε) désigne l'ensemble des chaînes qui commencent par 'a', suivi de zéro ou plus 'b', et se terminent éventuellement par un 'c' optionnel ;

Expressions rationnelles et automates finis

Le premier résultat important concernant les langages rationnels est le théorème de Kleene, qui affirme que l'ensemble des langages rationnels sur Σ est exactement l'ensemble des langages reconnaissables par automate fini sur Σ. En d'autres termes, à tout automate fini on peut associer une expression régulière qui définit le langage reconnu par l'automate, et réciproquement. Il n'y a pas bijection car plusieurs automates différents peuvent reconnaître un même langage, et de même il existe plusieurs expressions régulières pour le définir. Il y a cependant une différence significative entre ces deux approches en termes de compacité de représentation : certaines familles de langages rationnels nécessitent pour leur description une famille d'automates dont la taille croît exponentiellement, alors que la taille des expressions rationnelles nécessaires ne croît que linéairement.

On peut également s'intéresser au pouvoir d'expression à l'intérieur du formalisme. Comme l'exemple ci-dessus le montre, des expressions rationnelles différentes peuvent désigner le même langage : le formalisme est redondant. Dans quelle mesure cette redondance peut-elle être éliminée ? Pouvons-nous trouver un sous-ensemble d'expressions rationnelles intéressant et toujours capable d'engendrer tous les langages rationnels ? L'étoile de Kleene et la concaténation ne peuvent pas être entièrement omises des opérations de base, mais peut-être peut-on restreindre leur usage. Ce problème est en fait d'une difficulté surprenante. Aussi simples que soient les expressions rationnelles, il n'existe pas de méthode systématique pour les ramener à une forme normale. Il faut donc avoir recours à d'autres techniques ; on arrive ainsi au problème de degré d'étoile.

Une autre caractérisation

À tout langage L on peut associer une relation d'équivalence ≡_L sur les mots définie de la façon suivante :

u ≡_L v si et seulement si pour tout mot w de Σ^*, on a uw ∈ L ⇔ vw ∈ L.

Cette relation est une congruence car elle est compatible avec la concaténation : si u ≡_L v alors uw ≡_L vw.

Le théorème de Myhill-Nerode affirme qu'un langage L est rationnel si et seulement si la relation ≡_L possède un nombre fini de classes d'équivalence. Outre le regard nouveau qu'il apporte, ce théorème a des conséquences pratiques importantes puisqu'il est au cœur des algorithmes de minimisation des automates déterministes. En effet, les états de l'automate fini déterministe minimum reconnaissant un langage rationnel L sont en bijection avec les classes d'équivalence de la relation ≡_L.

Propriétés remarquables

Tout d'abord, outre les propriétés de clôture issues de la définition des expressions régulières, les langages rationnels sont clos par complémentaire et intersection : si L₁ et L₂ sont rationnels alors Σ^* \ L₁ et L₁ ∩ L₂ sont également rationnels.

Le lemme de pompage donne une propriété structurelle forte des langages rationnels. Il s'énonce informellement ainsi : pour tout langage rationnel L, et pour tout mot u∈L suffisamment long, il existe une partie de u que l'on peut répéter autant que l'on veut en restant toujours dans L. L'appellation "pompage" vient de cette possibilité de répétition.

Une façon intuitive de comprendre ce lemme est de considérer la reconnaissance par automate fini. En effet, pour un automate A fixé, tout mot u suffisamment long et reconnu par A "passe" nécessairement deux fois par un même état q. La partie du mot u correspondant au parcours en boucle de q à q dans A peut être répétée autant que l'on veut sans que cela ne change rien à la reconnaissance par A du mot obtenu.

Attention cependant, ce lemme n'est pas une caractérisation des langages rationnels : il existe des langages qui vérifient la propriété de pompage mais qui ne sont pas rationnels. Par exemple, le langage L = {bⁱaⁿbⁿ \ i>O et n≥0} n'est pas rationnel (car son intersection avec le langage rationnel b a^* b^* n'est pas rationnelle puisqu'elle viole le lemme de pompage), cependant on peut "pomper" dans tout mot de L en restant dans L : il suffit de multiplier les occurrences de b en tête.