Langage régulier

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 une classe, 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.

Sommaire 1 Théorie 1.1 En théorie des langages formels 1.2 Mise en œuvre 1.3 Expressions rationnelles et automates finis 1.4 Une autre caractérisation 1.5 Propriétés remarquables 2 Exemples et contre-exemples 3 Historique 4 Notes 5 Références

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 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é, 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^[1].

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^[1].

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.

Exemples et contre-exemples

Les langages suivants sont rationnels :

• L'ensemble des notations décimales de nombres naturels sur l'alphabet: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
• Les langages finis.
• L'ensemble des mots qui contiennent un mot donné.
• L'ensemble des mots qui contiennent un nombre pair de "1".
• L'ensemble des mots qui sont l'écriture en binaire d'un entier congruent à 2 modulo 5.

En revanche, les langages suivants ne sont pas rationnels :

• L'ensemble de mots {aⁿbⁿ : n ≥ 0 }
• Une expression bien parenthésée est obtenue comme étant soit () soit (e) où e est elle-même bien parenthésée. L'ensemble des expressions bien parenthésées ne forme pas un langage rationnel car son intersection avec le langage rationnel (*)* n'est pas rationnelle (c'est le langage précédent à un changement de symboles près).
• L'ensemble des palindromes.

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, dans un article intitulé Représentation des évènements dans les réseaux nerveux et Automates finis.

Dans les années 1950, A. Nerode, J. Myhill, D. A. Huffman et E. F. Moore établissent le lien avec les congruences et l'algorithme de minimisation des automates déterministes. 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.

Notes

Références

• (fr) Olivier Carton, Langages formels, calculabilité et complexité.Vuibert 2008, (ISBN 978-2-7117-2077-4).
• (fr) Jacques Sakarovitch, Eléments de théorie des automates, Vuibert 2003. (ISBN 978-2-7117-4807-5).

Informatique théorique
Théorie du calcul	Calculabilité Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Récursivement énumérable Modèle de calcul Automate fini • Automate cellulaire • Machine de Turing • Thèse de Church Modes de calcul Concurrence • Parallèlisme • Théorie de l'ordonnancement Mesure et échelle de complexité Réduction polynomiale • Problème NP-complet
Logique, syntaxe et sémantique	Logique mathématique Assistant de preuve • Calcul des prédicats • Correspondance de Curry-Howard • Fonction récursive • Lambda-calcul • Théorème d'incomplétude de Gödel • Théorie des types Grammaire formelle et systèmes de réécriture Compilation • Expression rationnelle • Grammaire formelle • Langage rationnel • Théorie des langages Sémantique Sémantique des langages de programmation • Sémantique dénotationnelle • Sémantique axiomatique • Sémantique opérationnelle Spécifier, vérifier et concevoir des programmes Interprétation abstraite • Méthodes formelles • Model checking
Algorithmique, complexité et mathématiques discrètes	Algorithmique Algorithme génétique • Algorithme glouton • Algorithme probabiliste • Complexité algorithmique • Diviser pour régner • Heuristique • Programmation dynamique Problèmes et algorithmes numériques Algorithme du simplexe • Géométrie algorithmique • Algorithme d'Euclide • Test de primalité Problèmes et algorithmes non-numériques Algorithmes de la théorie des graphes • Arbre (informatique) • Liste (informatique) • Table de hachage • Tas (informatique) Théorie des graphes Coloration de graphe • Problèmes de cheminement Recherche opérationnelle Optimisation • Optimisation combinatoire • Théorie de l'ordonnancement Données et codage Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

• Portail de la logique
• Portail de l’informatique