Langage rationnel

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir régulier et rationnel.

Cet article est une ébauche à compléter concernant l'informatique, vous pouvez partager vos connaissances en le modifiant.

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 reconnus formellement par des automates finis.

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

Sommaire

1 Théorie
2 En théorie des langages formels
- 2.1 Mise en œuvre
3 Exemples et contre-exemples
4 Quelques résultats mathématiques
5 Historique

[modifier] Théorie

On considère un ensemble fini de caractères ou lettres, ou alphabet, $\Sigma\,$ . 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é $\Sigma^*\,$ .

Les expressions rationnelles sont composées de constantes et d'opérateurs qui décrivent des ensembles de chaînes de caractères (c'est-à-dire des parties de $\Sigma^*\,$ ), que l'on appelle « langages » et des opérations sur ces ensembles.

Les constantes suivantes sont définies :

ensemble vide (noté $\,\varnothing$ ) : désigne l'ensemble vide (aucune chaîne de caractère n'est dans $\varnothing\,$ ) ;
mot vide ou chaîne vide (noté ε ) : désigne la chaîne de caractères qui ne contient aucune lettre ;
caractère littéral (noté a) : lorsque a est un élément de $\Sigma\,$ , 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 $\Sigma^*\,$ ) :

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"} ;
union ensembliste (notée R U S) : désigne l'union des ensembles R et S;
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 zéro, 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é, on ne notera plus les guillemets ".

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

soit le langage vide, noté $\varnothing$
soit les langages fait de mots à une lettre $\,\{a\}$ avec $a\in\Sigma$ , (notés simplement $a$ )
soit les langages $L_1 \cup L_2, L_1\cdot L_2$ et $L_1^*$ où $L_1,L_2 \in {\mathcal Rat}(\Sigma).$

On désigne l'ensemble des langages rationnels sur l'alphabet Σ par ${\mathcal Rat}(\Sigma)$ .

Ainsi ${\mathcal Rat}(\Sigma)$ 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 $\varnothing$ ainsi que tous les langages $\,\{a\}$ où $a\in\Sigma$ (que l'on notera abusivement a, tout simplement; de même que {ε}, le langage contenant le mot vide, est noté ε).

[modifier] En théorie des langages formels

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

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 $\Sigma^*\,$ 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).

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

[modifier] 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;

Les expressions rationnelles sont capables de décrire exactement les mêmes langages que ceux exprimés par les automates finis (déterministes ou non) : ces langages sont appelés langages rationnels.

Il y a cependant une différence significative entre ces deux approches en termes de compacité de représentation : certaines familles de langages langage 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 langage 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.

[modifier] Exemples et contre-exemples

L'ensemble des notations décimales de nombres naturels forme un langage régulier sur le vocabulaire ${0,1,2,3,4,5,6,7,8,9}$ .
Les langages finis sont rationnels.
Le langage vide et le langage formé de tous les mots sont rationnels.
La réunion et l'intersection de langages rationnels sont rationnelles.
Une expression bien parenthèsée est obtenue comme étant soit () soit (e) où est e est elle-même bien parenthésée. L'ensemble des expressions bien parenthésées ne forme pas un langage rationnel.

[modifier] Quelques résultats mathématiques

Un 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. Notons qu'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.

Le lemme de pompage des langages rationnels permet de caractériser les langages rationnels. Ce lemme montre qu'étant donné un langage L, il existe un entier n que si L contient un mot de taille supérieure à n, alors L contient tous les mots (en nombre infini) ayant une certaine structure déduite de ce mot. Ce lemme sert essentiellement à montrer que certains langages ne peuvent pas être des langages rationnels.

[modifier] Historique

Dans les années 1940, Warren McCulloch et Walter Pitts ont décrit le système nerveux en modélisant les neurones par des automates simples. Le logicien, Stephen Cole Kleene, a ensuite décrit ces modèles en termes d'ensembles réguliers, danas un article intitulé Représentation des évènements dans les réseaux nerveux et Automates finis. En 1959, Michael Rabin et Dana Scott proposent le premier traitement mathématique et rigoureux de ces concepts dans un article célèbre qui leur vaut le Prix Turing et qui contribue à faire démarrer l'étude de ces langages, dans leur célèbre article Automates finis et leurs problèmes de décision. Ken Thompson a implémenté cette notation dans l'éditeur qed, puis l'éditeur ed sous Unix, et finalement dans grep. Depuis lors, les expressions rationnelles ont été largement utilisées dans les utilitaires tels que lex ainsi que dans les langages de programmation nés sous Unix, tels que expr, awk, Perl, Python... Une bonne partie d'entre eux reposent sur la bibliothèque regex, créée par Henry Spencer.