Théorème de Myhill-Nerode

En informatique théorique, et notamment en théorie des langages formels et des automates, le théorème de Myhill-Nerode donne une condition nécessaire et suffisante pour qu'un langage formel soit un langage rationnel, c'est-à-dire reconnaissable par un automate fini. Ce théorème porte les noms de John Myhill et Anil Nerode qui l'ont prouvé en 1958 (Nerode 1958).

L'intérêt de cet énoncé est que la condition nécessaire et suffisante porte sur le langage lui-même, et ne fait pas appel à la construction d'un automate. La preuve est par contre constructive, et permet d'obtenir effectivement un automate qui s'avère de plus être minimal.

Énoncé du théorème

Étant donné un langage $L$ et deux mots $x$ et $y$ , on dit qu'un mot $z$ sépare $x$ et $y$ si un et un seul des mots $xz$ et $yz$ est dans le langage $L$ . Deux mots $x$ et $y$ sont inséparables (undistiguishable en anglais) s'il n'existe pas de mot $z$ qui les sépare.

On définit une relation $R_{L}$ sur les mots, appelée relation de Myhill-Nerode, par la règle : $xR_{L}y$ si et seulement si $x$ et $y$ sont inséparables. Il est facile de montrer que la relation $R_{L}$ est une relation d'équivalence sur les mots, et donc partitionne l'ensemble de tous les mots en classes d'équivalences. Le nombre de classes est appelé l'index de la relation. Il peut être fini ou infini.

Théorème de Myhill-Nerode — Un langage $L$ est rationnel si et seulement si la relation $R_{L}$ est d'index fini ; dans ce cas, le nombre d'états du plus petit automate déterministe complet reconnaissant $L$ est égal à l'index de la relation. En particulier, ceci implique qu'il existe un automate déterministe unique avec un nombre minimal d'états.

Démonstration

Soit $L$ un langage rationnel. Il existe un automate fini déterministe complet qui reconnaît $L$ . Pour chaque état $q$ de cet automate, soit $P_{q}$ l’ensemble des mots $w$ qui mènent de l'état initial à $q$ . Si $x$ et $y$ sont deux mots de $P_{q}$ , alors pour tout mot $z$ , les mots $xz$ et $yz$ mènent au même état, qu'il soit acceptant ou non. Ainsi, aucun mot $z$ ne peut séparer $x$ et $y$ , et ils sont donc inséparables. Ceci montre que l'ensemble $P_{q}$ est contenu dans une classe de l'équivalence $R_{L}$ , et comme tout mot est dans un des ensembles $P_{q}$ , l'index de la relation est inférieur ou égal au nombre d'états de l'automate, et donc est fini.

Réciproquement, supposons que la relation de Myhill-Nerode $R_{L}$ est d'index fini. Dans ce cas, on construit un automate fini reconnaissant $L$ comme suit. Les états sont les classes de l'équivalence $R_{L}$ . L'état initial est la classe d'équivalence du mot vide, et la fonction de transition mène, pour un état $p$ et une lettre $a$ , à l'état $q$ qui contient le mot $xa$ , où $x$ est un mot quelconque de $p$ . La définition de l'équivalence $R_{L}$ assure que la fonction de transition est bien définie : si $xR_{L}y$ , alors $xaR_{L}ya$ pour toute lettre $a$ , car si un mot $z$ était un séparateur de $xa$ et $ya$ , alors $az$ séparerait $x$ et $y$ . Un état de l'automate est final s'il contient un mot de $L$ . Comme précédemment, la définition de la relation $R_{L}$ implique alors que tous les éléments de cette classe sont dans $L$ , sinon le mot vide pourrait séparer des mots de cette classe.

Ainsi, l'existence d'un automate fini reconnaissant $L$ implique que la relation $R_{L}$ est d'index fini, et d'index au plus égal au nombre de d'états de l'automate, et la finitude de l'index de $R_{L}$ implique l'existence d'un automate ayant ce nombre d'états.

Relation de Myhill-Nerode et résiduels

Étant donné un langage $L$ de $A^{*}$ et un mot $x$ , le quotient gauche de $L$ par $x$ , ou le résiduel de $L$ par $x$ , est l'ensemble noté $x^{-1}L$ défini par

x^{-1}L=\{z\in A^{*}\mid xz\in L\}

Avec cette notation, deux mots $x$ et $y$ sont inséparables si et seulement si $x^{-1}L=y^{-1}L$ . Les classes de l'équivalence de Myhill-Nerode sont donc en bijection avec les résiduels de $L$ . Il en résulte qu'un langage est rationnel si et seulement si l'ensemble de ses résiduels est fini. C'est sous cette forme que le théorème est énoncé dans le traité d'Eilenberg^[1].

Applications

On peut employer le théorème pour prouver qu'un langage est rationnel en démontrant que la relation $R_{L}$ est d'index fini. Ceci se fait par une exploration systématique des mots à partir du mot vide : pour chaque mot, on cherche une classe déjà existante ou on crée une nouvelle classe. Par exemple, considérons le langage des mots binaires qui représentent des entiers divisibles par 3. Le mot vide (de valeur 0) et le mot 1 sont séparés par le mot vide, le mot 0 sépare le mot vide de 1. On a déjà trois classes correspondant aux nombres de reste 0, 1, et 2 modulo 3. Il reste à vérifier qu'il n'y a pas d'autre classe.

Un usage plus fréquent est la preuve qu'un langage n'est pas rationnel en montrant que l'index de la relation de Myhill-Nerode est infini. Si on prend par exemple le langage bien connu $L=\{a^{n}b^{n}\mid n\geq 1\}$ , alors deux mots $x=a^{n}$ et $y=a^{m}$ , avec $n\neq m$ , sont séparables et séparés par le mot $b^{n}$ (ou $b^{m}$ ). Ainsi, ce langage n'est pas rationnel.

Extension

Le théorème de Myhill-Nerode se généralise aux arbres. Voir automate d'arbres.

Notes et références

Notes

↑ Eilenberg 1974, Théorème 8.1 (The Quotient Criterion), page 55.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Myhill–Nerode theorem » (voir la liste des auteurs).

Littérature

La plupart les livres d'enseignement des langages formels exposent ce théorème.

Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4, présentation en ligne)
Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253).

(en) Samuel Eilenberg, Automata, Languages and Machines, Vol. A, New York, Academic Press, coll. « Pure and Applied Mathematics » (n^o 58), 1974, xvi+451 (ISBN 978-0-12-234001-7)