Langage rationnel

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 (ou fermeture 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.

Ce sont aussi :

les langages dont le monoïde syntaxique est fini,
les langages qui admettent une description dans la logique monadique du second ordre avec successeur,
les langages de type 3 dans la hiérarchie de Chomsky: ce sont les langages qui peuvent être engendrés par une grammaire régulière, c'est-à-dire une grammaire linéaire droite (ou linéaire gauche),
les langages reconnus par des machines de Turing qui n'écrivent pas sur leur bande (ce sont aussi les automate boustrophédon (en)) ;
les langages reconnus par des automates alternants (en).

Les langages rationnels ont de très nombreuses applications, à la fois théoriques et pratiques. Ils sont utilisés en informatique (par exemple en compilation, 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 Pattern. Les algorithmes utilisés pour manipuler les langages rationnels possèdent en général une implémentation rapide et efficace.

Sommaire

1 Définition
2 Expressions rationnelles et automates finis
3 Propriétés
4 Lemme d'itération
5 Exemples et contre-exemples
6 Histoire
7 Voir aussi
8 Notes
9 Références

Définition

On considère un ensemble fini $A$ 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 excemple, la chaîne formée de la lettre $a$ , puis de la lettre $b$ , puis encore de la lettre $a$ , se note $a b a$ .

L'ensemble des mots que l'on peut former avec ces lettres de $A$ est noté $A *$ . Toute partie de $A *$ s'appelle un langage.

Opérations rationnelles

Les opérations suivantes, définies sur les langages, sont appelées les opérations rationnelles. Soient $X$ et $Y$ deux parties de $A *$ :

la concaténation ou le produit de $X$ et $Y$ , noté $X Y$ , est l'ensemble de mots $x y$ , où $x$ est dans $X$ et $y$ est dans $Y$ . Par exemple, le produit de ${a b, c}$ et de ${b a, c}$ est ${a b b a, a b c, c b a, c c}$ ;
l'union ensembliste, notée $X\cup Y$ ;
la fermeture de Kleene, notée $X *$ est le plus petit langage qui contient le mot vide $ε$ , le langage $X$ , 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 $X$ . Par exemple, $\{a,ab\}^\star = \{\varepsilon,a,aa,ab,aaa,aab,aba,aaaa,aaab,aaba,abaa,abab,\dots\}$ .

Langages rationnels

L'ensemble des langages rationnels sur l'alphabet $A$ est le plus petit ensemble de langages stable pour les opérations rationnelles, et qui contient le langage vide $\emptyset$ , les langages réduit à une lettre et le langage composé du mot vide ${ε}$ .

Expressions rationnelles

Article détaillé sur l'usage des expression régulières : Expression rationnelle.

Les expressions rationnelles sur l'alphabet $A$ sont des expression obtenues à partir des des constantes 0, 1, et de constantes $a$ , pour les lettres $a$ de $A$ , par des opérations suivantes:

L'opération $+$ ou $|$ (pour représenter l'union)
L'opération $\cdot$ (pour représenter le produit, ce point est d'ailleurs souvent omis)
L'opération $*$ (pour représenter l'étoile).

Chaque expression rationnelle $e$ dénote un langage rationnel. Ce langage, noté $L (e)$ , est défini comme suit:

$L(0)=\emptyset$ , $\ L(1)=\{\varepsilon\}$ , $\ L(a)=\{a\}\,$ pour chaque lettre $a$
$L(e+f)=L(e)\cup L(f)$ , $\ L(e\cdot f)=L(e)L(f)$ , $\ L(e^\star)=L(e)^\star\,$

Deux expressions rationnelles sont équivalentes si elles dénotent le même langage.

Exemple

Les expressions $(a^\star b)^\star a^\star$ et $(a+b)^\star$ sont équivalentes.

Variantes

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

On ajoute parfois aussi, aux opérateurs sur les expressions, la fermeture $+$ , donnant l'expression $e +$ . Le langage dénoté est donné par $L (e +) = L (e) +$ , 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éfini les 'expressions rationnelles étendues comme les expressions incluant aussi l'opérateur de complémentation.

Notons enfin que 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 fréquemment ajoutés, avec des propriétés qui les rendent capable 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

Articles détaillés : théorème de Kleene et automate fini.

Le théorème de Kleene affirme que l'ensemble des langages rationnels sur un alphabet $A$ est exactement l'ensemble des langages sur $A$ 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

La hauteur d'étoile d'une expression rationnelle $e$ est le nombre $h (e)$ défini récursivement comme suit:

$h(0)=h(1)=h(a)=0\,$ pour toute lettre $a$
$h(e+f)=h(e\cdot f)=\max\{h(e),h(f)\}$
$h(e^\star)=1+h(e)$ .

En d'autres termes, la hauteur d'étoile d'une expression est le nombre maximum d'étoiles imbriquées. Par exemple, $h((a+b)^\star)=1$ et $\ h((a^\star b)^\star a^\star)=2$ . Ces deux expressions dénotent le même langage, donc la notion de hauteur d'étoile est liée à l'expression.

La hauteur d'étoile d'un langage rationnel $X$ est le minimum des hauteurs d'étoile des expressions dénotant ce langage, c'est-à-dire

$h(X)=\min\{h(e)\mid L(e)=X\}.$

La question de l'existence de langages rationnels de hauteur d'étoile arbitrairement grande a été posée par Eggan et résolue par Françoise Dejean et Marcel-Paul Schützenberger^[2]. Le problème de la hauteur d'étoile (en) est de calculer, de manière efficace, la hauteur d'étoile d'un langage rationnel. Ce problème a résisté longtemps. Il a été résolu la première fois en 1982; le meilleur algorithme, dû à Kirsten, est de 2005 (voir la page anglaise).

Une question qui est toujours ouverte concerne le problème de la hauteur d'étoile généralisée (en): 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) augment bien entendu. Il n'est pas connu 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 étoiles » caractérisés par Marcel-Paul Schützenberger.

Le théorème de Myhill-Nerode

À tout langage $L$ de $A *$ , on associe une relation d'équivalence $\equiv_L$ sur $A *$ définie de la façon suivante :

$u\equiv_L v\,$ si et seulement si pour tout mot

x

A *

, on a $ux\in L \iff vx\in L$

Cette relation est une équivalence régulière à droite car elle est compatible avec la concaténation : si $u\equiv_L v$ alors $ux\equiv_L vx$ .

Le théorème de Myhill-Nerode (en) affirme qu'un langage $L$ est rationnel si et seulement si la relation $\equiv_L$ est d'index 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 $L$ sont en bijection avec les classes d'équivalence de la relation $\equiv_L$ ^[3]. Ce résultat est aussi à la base d'un algorithme efficace de minimisation (en), appelé l'algorithme de Moore.

Propriétés

Les langages rationnels sont fermés, en plus de l'union, du produit et de l'étoile, par complémentation et donc par intersection.

Les langages rationnels sont fermés par image miroir: si $X$ est un langage rationnel, alors $X r$ est rationnel, où $X r$ est l'ensemble des retournés ou images miroir des mots de $X$ .

L'ensemble des préfixes, l'ensemble des suffixes, l'ensemble des facteurs, l'ensemble des sous-mots des mots d'un langage rationnel est un langage rationnel.

Pour tout langage rationnel $X$ et tout mot $u$ , le quotient gauche
$u^{-1}X=\{w\mid uw\in X\}$
est un langage rationnel.

L'image d'un langage rationnel par un morphisme est un langage rationnel.

L'image par un morphisme inverse d'un langage rationnel est un langage rationnel

L'image, par une substitution rationnelle, d'un langage rationnel est un langage rationnel (une substitution $σ$ de $A *$ dans $B *$ est une application de $A *$ dans l'ensemble des parties de $B *$ qui est un morphisme pour la structure de monoïde multiplicatif sur l'ensemble des parties de $B *$ , c'est-à-dire $σ(ε) = {ε}$ et $σ(x y) = σ(x)σ(y)$ , où le produit dans le membre droit est le produit des parties de $B *$ . Une substitution rationnelle est une substitution $σ$ telle qui $σ(a)$ est un langage rationnel sur $B$ pour toute lettre $a$ de $A$ ).

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 $x$ et $y$ est l'ensemble des mots $x_1y_1x_2y_2\cdots x_ny_n$ , où les $x i$ et les $y i$ sont des mots, tels que $x=x_1x_2\dots x_n$ et $y=y_1y_2\dots y_n$ . 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 $X$ est le langage
$P(X)=\{p\in A^\star \mid\exists q\in A^\star : |p|=|q| \text{ et } pq\in X\}$ .
En d'autre termes, on coupe au milieu des mots de $X$ de longueur paire et on garde la première partie. Si $X$ est un langage rationnel, alors $P (X)$ 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.

Lemme d'itération

Le lemme d'itération (en anglais pumping lemma, traduit parfois malheureusement par lemme de pompage) donne une propriété nécessaire des langages rationnels. Il s'énonce informellement comme suit: dans tout mot assez long $w$ d'un langage rationnel $X$ , on peut trouver un facteur $u$ non vide que l'on peut répéter un nombre arbitraire de fois, tout en restant dans le langage $X$ .

C'est en fait une propriété d'un automate reconnaissant le langage $X$ : un mot assez long reconnu par l'automate contient nécessairement un circuit qui l'on peut parcourir un nombre arbitraire de fois, tout en restant reconnu part l'automate

Ce lemme n'est pas une caractérisation des langages rationnels: il existe des langages qui vérifient la propriété d(itération mais qui ne sont pas rationnels.

Exemples et contre-exemples

Les langages suivants sont rationnels :

L'ensemble des notations décimales de entiers 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.

Les langages suivants ne sont pas rationnels :

L'ensemble de mots $\{a^nb^n: n \ge 0 \}$
Les ensembles $\{a^nb^p: n \ge p\ge0 \}$ , $\{a^nb^p: n \ne p\}$
Une expression bien parenthésée est obtenue comme étant soit le mot vide, soit $(e) e'$ où $e$ et $e'$ sont bien parenthésées. L'ensemble des expressions bien parenthésées est aussi appelé le langage de Dyck.
Ce n'est pas un langage rationnel car son intersection avec le langage rationnel $(^\star )^\star$ n'est pas un langage rationnel (c'est le langage précédent à un changement de symboles près).
L'ensemble des palindromes.

Histoire

La théorie débute dans les années 1940^[4]. Warren McCulloch et Walter Pitts ont décrit, en 1943, le système nerveux en modélisant les neurones par des automates simples. Le logicien Stephen Cole Kleene a ensuite prouvé, en 1956, ce que l'on appelle le théorème de Kleene. En 1956, E. F. Moore (en) publie son algorithme de minimisation. En 1958, A. Nerode (en) et J. Myhill (en) publient leur caractérisation. En 1959, Michael Rabin et Dana Scott donnent, dans un célèbre article^[5], un traitement rigoureux de la théorie des automates. Cet exposé pionnier leur vaut le Prix Turing.

Du point de vue pratique, c'est Ken Thompson qui implémente les expressions rationnelles 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 (en).

Voir aussi

Notes

↑ Pour une définition précise des règles de simplification, on peut consulter Sakarovitch (2003)
↑ Dejean et Schützenberger (1966)
↑ voir par exemple Hopcroft Ullman (1979) ou Carton (2008) ou Sakarovitch (2003)
↑ Pour un exposé des premières années de la théorie des automates et des langages rationnels, voir Perrin (1995)
↑ Rabin et Scott (1959)

Références

Dominique Perrin, « Les débuts de la théorie des automates », dans Technique et science informatiques, vol. 14, n^o 4, 1995, p. 409-433 [texte intégral]

Françoise Dejean et Marcel-Paul Schützenberger, « On a Question of Eggan », dans Information and Control, vol. 9, n^o 1, 1966, p. 23-2

(en) J. E. Hopcroft et J. D. Ullman, Introduction to Automata Theory, Languages and Computations, Addison-Wesley, 1979 (ISBN 0-201-02988-X)

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)

(en) Michael O. Rabin et Dana Scott, « Finite automata and their decision problems », dans IBM J. Res. Develop., vol. 3, 1959, p. 114-125

Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (ISBN 978-2-7117-4807-5).
Traduction anglaise avec corrections: Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)

v · d · m

Informatique théorique

Théorie du calcul

Calculabilité	Décidabilité et indécidabilité • Ensemble récursif • Problème de l'arrêt • Ensemble récursivement énumérable
Modèle de calcul	Automate fini •Transducteur fini •Automate sur les mots infinis •Automate à pile •Automate linéairement borné • 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 • Transduction rationnelle • Langage rationnel • Langage algébrique • Langage contextuel • 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 (structure de données) • 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	Combinatoire des mots •Codage • Codage de l'information • Compression de données • Cryptage • Cryptanalyse • Cryptographie • Théorie de l'information

Catégories :

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Langage rationnel de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

Langage Rationnel — Pour les articles homonymes, voir Langage, Régulier et Rationnel. 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… … Wikipédia en Français
Langage régulier — Langage rationnel Pour les articles homonymes, voir Langage, Régulier et Rationnel. Les expressions rationnelles permettent d engendrer une famille de langages appelés, suivant les auteurs, langages rationnels ou langages réguliers. Ce sont les… … Wikipédia en Français
Langage algébrique — En théorie des langages formels, un langage algébrique ou langage non contextuel est un langage qui peut être engendré par une grammaire algébrique. De manière équivalente un langage algébrique est un langage reconnu par automate à pile. Les… … Wikipédia en Français
Langage de Dyck — En informatique théorique, et plus spécialement en théorie des langages, les langages de Dyck sont des langages formels particuliers. Un langage de Dyck est l ensemble des mots bien parenthésés, sur un alphabet formé de parenthèses ouvrantes, et… … Wikipédia en Français
Langage contextuel — En informatique théorique, et spécialement en théorie des langages, un langage contextuel (en anglais context sensitive langauge) est un langage formel engendré par une grammaire contextuelle. C est un langage de type 1 dans la hiérarchie de… … Wikipédia en Français
Rationnel — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Rationnel », sur le Wiktionnaire (dictionnaire universel) L’adjectif rationnel dérive du nom raison.… … Wikipédia en Français
rationnel — rationnel, elle [ rasjɔnɛl ] adj. et n. m. • 1120 « doué de raison » (âme); lat. rationalis I ♦ (→ raison, I) 1 ♦ (XIIIe) Qui appartient à la raison, relève de la raison (I). Activité rationnelle. ⇒ raisonnement. La pensée … Encyclopédie Universelle
Langage Humain — Le langage est la faculté de mettre en œuvre un système de signes linguistiques (qui constituent la langue) permettant la communication et l expression de la pensée, ce qui est privatif des humains, et des sentiments, ce qui est commun aux… … Wikipédia en Français
Langage oral — Langage humain Le langage est la faculté de mettre en œuvre un système de signes linguistiques (qui constituent la langue) permettant la communication et l expression de la pensée, ce qui est privatif des humains, et des sentiments, ce qui est… … Wikipédia en Français
Langage quotidien — Langage humain Le langage est la faculté de mettre en œuvre un système de signes linguistiques (qui constituent la langue) permettant la communication et l expression de la pensée, ce qui est privatif des humains, et des sentiments, ce qui est… … Wikipédia en Français

Dictionnaires et Encyclopédies sur 'Academic'

Langage rationnel

Sommaire