Théorie_des_expressions_rationnelles

Un article de Wikipedia.y-project.com.

[] Théorie

L'origine et la justification mathématique des expressions rationnelles se situent dans la théorie des automates et des langages formels. Ces champs d'étude couvrent des modèles de calcul (automates) et des façons de décrire et de classifier des langages formels. Un langage formel est ici simplement défini comme un ensemble de chaînes de caractères.

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, notion qu'il a introduite avec une certaine notation. En 1959, Michael Rabin et Dana Scott propose 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. 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.

Les expressions rationnelles correspondent aux grammaires de type 3 de la hiérarchie de Chomsky ; elles peuvent donc être utilisées pour décrire la morphologie d'une langue.

[] Les expressions rationnelles en théorie des langages formels

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

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 <math>\Sigma^*\,</math>) et des opérations sur ces ensembles.

Les constantes suivantes sont définies :

1. ensemble vide (noté <math>\,\varnothing</math>) : désigne l'ensemble vide (aucune chaîne de caractère n'est dans <math>\varnothing\,</math>) ;
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 <math>\Sigma\,</math>, 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 <math>\Sigma^*\,</math>) :

1. concaténation (notée RS) : 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 zéro, une ou plusieurs chaînes de R. Par exemple, {"ab", "c"}* = {?, "ab", "c", "abab", "abc", "cab", "cc", "ababab", ... }.

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

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 <math>\Sigma^*\,</math> 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 déterministes à états finis).

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

[] Mise en oeuvre

• 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 réguliers.

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

DernierMirror  
Le Texte ci-dessus est disponible sous GNU Free Documentation License.
La source est wikipedia http://fr.wikipedia.org/wiki/Théorie des expressions rationnelles