Théorème de Myhill-Nerode

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

É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 le mots, appelée relation de Myhill-Nerode, par la règle : x R_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[modifier | modifier le code]

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 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 x R_L y, alors xa R_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[modifier | modifier le code]

É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[modifier | modifier le code]

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 rest 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^nb^n\mid n\ge1\}, alors deux mots x=a^n et y=a^m, avec n\ne m, sont séparables et séparés par le mot b^n (ou b^m). Ainsi, ce langage n'est pas rationnel.

Extension[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. 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[modifier | modifier le code]

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

L'article original est :

  • Anil Nerode, « Linear Automaton Transformations », Proceedings of the American Mathematical Society, vol. 9, no 4,‎ août 1958, p. 541-544.

Articles connexes[modifier | modifier le code]